为什么不“在”操作设置文字O（1）？

问题描述 投票：1回答：5

这是很常见的做测试了很多常量对一个变量

if x in ('foo', 'bar', 'baz'):

而不是

if x == 'foo' or x == 'bar' or x == 'baz':

我见过很多“而不是使用{'foo', 'bar', 'baz'}为O（1）性能，('foo', 'bar', 'baz')”，这是有道理的，但测试显示非常奇怪的结果。

%timeit 1 in {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
27.6 ns ± 2.35 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)

%timeit 10 in {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
136 ns ± 4.04 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)

%timeit 0 in {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
186 ns ± 26.5 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)

为什么是集文字查找不固定的时间？

python set tuples literals membership
5个回答
1
投票

设置查找是平均的O（1）的操作。它不应该始终如一地改变所设定您检查，除了随机在一定程度上的什么元素表现为一些值可能与其他值的哈希冲突，因此需要较长时间才能被发现。你看到来查找你的小套不同的值的时间差几乎肯定是巧合，还是噪音，你误认为数据。

请注意，你不只是定时组成员在您的测试。你还建立了一套新的每一次，这通常是O（N）操作（其中N是值的设定数）。在一些特殊情况下，一组文字可以在O（1）时间作为Python的编译器的优化与一个不可变set对象，它事先已计算为常数，以取代可变frozenset对象创建的。只有发生在情况下编译器预计将重新创建对象一大堆倍，它可以告诉设定的对象任何引用泄漏的代码其运行的区域。例如，在一个或理解发电机表达的if子句中使用的集合可以得到恒定的治疗：

[foo(x) for x in some_iterable if x in {0, 1, 2, 3, 4, 5, 6, 7, 9}]

在最新版本的CPython的，设定的文字，这里将永远是指恒定frozenset并不需要重新创建从x产生每个some_iterable值。但是你可能不应该依赖这种行为，因为其他Python解释和的CPython的甚至其他版本可能无法执行相同的优化。

这不能说明你是在为你计时看到的不过。我猜想，有一个在你的环境中的一些人为解释的问题，或者它可能只是在设置的最小值恰好没有任何哈希冲突而最后一个（巧合）有几个随机的机会。如果您在组测试其他值，你可能会得到一个小范围的不同定时。但该范围不会趋向于变化不大与集合元素的数量，应该是对组的大小每一个相当类似的（可能有小的差异，但比的N倍小得多）。

尝试更加具体的测试（与分解出集创作），就像这样：

import timeit, random

big_set = set(range(1000000))

for x in random.sample(range(1000000), 10):
    print('looking up', x, 'took', timeit.timeit(lambda: x in big_set), 'seconds')
2
投票

那么，两件事情在这里。

  1. set([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])是超慢，因为它可能会先建立名单。我猜想，有一个在3.7+一些优化，但无论如何。集文字就是因为这样更快。
  2. “检查的第一个成员，甚至有点慢” - 关于套的东西 - 这不是奇迹般地O(1)。设定构件检查散列+模+散列+回退用于碰撞/缺失进行比较。有“第一成员”没有这样的事。
  3. 元组优于小数据集 - 因为套利用了大量的机械。这是O(1)，但不变的是比在一定范围内O(N)的价值更高。个人用，喜欢你的代码，10 ** 6长，你会看到其中的差别
  4. 定时文字是怪异的想法，通常比较快成员资格检查充分利用已经建立的容器： t = tuple(range(10**6)) s = set(range(10**6)) %timeit 999999 in t 11.9 ms ± 92 µs per loop (mean ± std. dev. of 7 runs, 100 loops each) %timeit 999999 in s 52 ns ± 0.538 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)

在测试渐进复杂侧面说明 - 你应该经常检查增长的幅度，原始数据意味着什么。即

x = 1; t = tuple(range(10**x)); s = set(range(10**x))
%timeit (-1) in t
168 ns ± 22.9 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)
%timeit (-1) in s
38.3 ns ± 0.46 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)

x = 2; t = tuple(range(10**x)); s = set(range(10**x))
%timeit (-1) in t
1.1 µs ± 17.1 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
%timeit (-1) in s
37.7 ns ± 0.101 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)

x = 4; t = tuple(range(10**x)); s = set(range(10**x))
%timeit (-1) in t
107 µs ± 860 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)
%timeit (-1) in s
39 ns ± 1.66 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)

x = 6; t = tuple(range(10**x)); s = set(range(10**x))
%timeit (-1) in t
10.8 ms ± 114 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
%timeit (-1) in s
38 ns ± 0.333 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)

这样你就可以清楚地看到什么是线性VS不断在这里。

2
投票

您正在测试的设置和搜索的同时建设。让我们再次尝试实验，但只有构建a一次。首先，这里有一个元组：

$ python -m timeit -s 'a = (0, 1, 2, 3, 4, 5, 6, 7, 8, 9)' -- '0 in a'
10000000 loops, best of 5: 22.6 nsec per loop

在搜索的最后一个元素是比较慢：

$ python -m timeit -s 'a = (0, 1, 2, 3, 4, 5, 6, 7, 8, 9)' -- '9 in a'
2000000 loops, best of 5: 136 nsec per loop

正如寻找失踪值：

$ python -m timeit -s 'a = (0, 1, 2, 3, 4, 5, 6, 7, 8, 9)' -- '-1 in a'
2000000 loops, best of 5: 132 nsec per loop

set.__contains__要好得多，一旦对象被构造：

$ python -m timeit -s 'a = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}' -- '0 in a'
10000000 loops, best of 5: 26.3 nsec per loop

正如预期的那样，顺序并不重要：

$ python -m timeit -s 'a = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}' -- '9 in a'
10000000 loops, best of 5: 26.1 nsec per loop

同样没有检查遗漏值：

$ python -m timeit -s 'a = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}' -- '-1 in a'
10000000 loops, best of 5: 26.4 nsec per loop
1
投票

我不明白您的结果：

python -m timeit "(-1) in {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}"
10000000 loops, best of 3: 0.0238 usec per loop

python -m timeit "0 in {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}"
10000000 loops, best of 3: 0.0235 usec per loop

python -m timeit "9 in {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}"
10000000 loops, best of 3: 0.0208 usec per loop

至于你关于在set()创建和{}的创作，你可以看到在字节码的差分问题：

设置文字：

from dis import dis
print(dis("9 in {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}"))

输出：

          0 LOAD_CONST               0 (9)
          2 LOAD_CONST              10 (frozenset({0, 1, 2, 3, 4, 5, 6, 7, 8, 9}))
          4 COMPARE_OP               6 (in)
          6 RETURN_VALUE

使用功能：

print(dis("9 in set([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])"))

输出：

          0 LOAD_CONST               0 (9)
          2 LOAD_NAME                0 (set)
          4 LOAD_CONST               1 (0)
          6 LOAD_CONST               2 (1)
          8 LOAD_CONST               3 (2)
         10 LOAD_CONST               4 (3)
         12 LOAD_CONST               5 (4)
         14 LOAD_CONST               6 (5)
         16 LOAD_CONST               7 (6)
         18 LOAD_CONST               8 (7)
         20 LOAD_CONST               9 (8)
         22 LOAD_CONST               0 (9)
         24 BUILD_LIST              10
         26 CALL_FUNCTION            1
         28 COMPARE_OP               6 (in)
         30 RETURN_VALUE

双方建立set，但是Python是马上就能识别文字设置为文本（和优化，以建立一个frozenset因为它知道有没有需要任何添加和删除），而它需要建立一个列表，加载set功能，然后调用列表上的功能。然而这种差异只是在创建集合。它不会影响in操作。

0
投票

你似乎混淆了的算法复杂性的意义 - 你有没有测试的特征。复杂性描述为输入尺寸趋向于无穷大的渐近时间要求。

您的测试是只有一个输入尺寸：10个元素。你测试的最好和最坏的情况。然而，向对算法的复杂性的工作，你需要提取的时间初始化步骤，然后在各种输入大小的比较性能：也许是10的幂，范围从10到10 ** 12。

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.