为什么不为“in”操作设置文本O(1)?

嗯,这里有几件事。

1. set([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])
2. “检查第一个成员的速度甚至慢了一点”关于设置的事情并不神奇 O(1)
3. 元组在小数据上的性能优于集合,因为集合利用了大量的机制。它是 ,但常数高于的值 O(N)

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)

所以你们可以清楚地看到线性和常数的关系。

和 搜索。让我们再做一次实验,但只做一次 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

集合查找平均是一个O(1)操作。除了在一定程度上随机地改变性能外,它不应该始终随检查集合的哪个元素而改变性能,因为某些值可能与其他值发生哈希冲突,因此需要更长的时间才能找到。在小集合中查找不同值时所看到的时间差几乎肯定是巧合,或者是误认为是数据的噪声。

请注意,在测试中,您不仅仅是计时集成员。每次都要创建一个新的集合,这通常是一个O(N)操作(其中N是集合中的值数)。在某些特殊情况下,当Python编译器进行优化以替换可变文本时,可以在O(1)时间内创建一个集合文本 set frozenset if 理解式或生成式表达式的子句可能会得到恒定的处理:

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

在CPython的最新版本中,此处的set文本将始终引用常量 这不需要为每个 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')

我没有得到你的结果:

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能够立即将文本集识别为文本(并进行优化以构建冻结集,因为它知道不需要任何添加和删除),同时需要构建列表,加载 函数,然后调用列表中的函数。然而,这种差异只存在于集合创建中。这不会影响到整个过程 in

你似乎对算法复杂性的含义感到困惑——你还没有测试过这个特性。 复杂性

做 测试最佳和最坏情况。然而,为了解决算法复杂性问题,您需要从计时中提取初始化步骤,然后比较各种输入大小的性能:可能是10的幂,范围从10到10**12。