为什么不为 "in" 操作设置文字 O(1)？

Question

通过执行

，针对一个变量测试大量常量是很常见的

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

而不是

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

我已经看到很多 "use {'foo', 'bar', 'baz'} instead of ('foo', 'bar', 'baz') for O(1) performance," 是有道理的，但测试显示出非常奇怪的结果。

%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)

为什么查找集合文字不是常数时间？

Answer 1

您似乎对算法复杂性的含义感到困惑 -- 您尚未测试该特性。 复杂度描述了输入大小趋于无穷大时的渐近时间要求。

您的测试仅针对一种输入大小：10 个元素。你做测试最好和最坏的情况。然而，为了解决算法的复杂性，您需要从时序中提取初始化步骤，然后比较各种输入大小的性能：可能是 10 的幂，范围从 10 到 10**12。

Answer 2

嗯，这里有几件事。

set([0, 1, 2, 3, 4, 5, 6, 7, 8, 9]) 超级慢，因为它可能首先构建列表。我想，3.7+ 中有一些优化，但无论如何。因此设置文字更快。
"checking for the first member is even a bit slower" – 关于集合的事情 – 它并不神奇 O(1)。集合成员检查是散列 + 取模 + 散列比较 + collision/deletion 的回退。没有 "first member".
元组在小数据上的表现优于集合——因为集合利用了很多机制。它是 O(1)，但常数在某些范围内高于 O(N) 的值。使用 10**6-length 分析您的代码，您会看到差异

用文字计时是个奇怪的想法，通常快速成员检查利用已经创建的容器：

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)

所以你可以在这里清楚地看到什么是线性与常数。

Answer 3

您正在测试集合 的构造和 搜索。让我们再次尝试实验，但只构建一次 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

Answer 4

我没有得到你的结果：

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，因为它知道不需要任何添加和removal），同时需要构建列表，加载set函数，然后调用列表上的函数。然而，这种差异仅存在于集合创建中。它不会影响 in 操作。

Answer 5

集合查找平均来说是一个 O(1) 操作。它不应该随着您检查的集合的哪个元素而持续改变性能，除非在一定程度上随机改变，因为某些值可能与其他值发生散列冲突，因此需要更长的时间才能找到。您在小集合中查找不同值时看到的时间差异几乎肯定是巧合，或者您误认为数据的噪声。

请注意，您不仅仅是在测试中设置成员资格。您还每次都创建一个新集合，这通常是一个 O(N) 操作（其中 N 是集合中值的数量）。在某些特殊情况下，可能会在 O(1) 时间内创建集合文字，因为 Python 编译器进行优化以用不可变的 frozenset 对象替换可变的 set 对象，它已预先计算为常数。这只会发生在编译器希望多次重新创建对象的情况下，并且它可以判断没有对集合对象的引用可以泄漏到其运行代码区域之外。例如，在推导式或生成器表达式的 if 子句中使用的集合可能会得到常量处理：

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

在 CPython 的最新版本中，此处的集合文字将始终引用一个常量 frozenset，不需要为从 [ 产生的每个 x 值重新创建它=17=]。但是您可能不应该依赖这种行为，因为其他 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')

为什么不为 "in" 操作设置文字 O(1)？

Why aren't set literals O(1) for "in" operations?

python

set

tuples

literals

membership