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

Question

用一个变量来测试很多常量是很常见的

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

而不是

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

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

%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

嗯，这里有几件事。

1. set([0, 1, 2, 3, 4, 5, 6, 7, 8, 9]) super 慢，因为它可能首先构建列表。我想，3.7+ 中有一些优化，但无论如何。因此，设置文字速度更快。
2. “检查第一个成员甚至有点慢”——关于集合的事情——它不是神奇的 O(1)。集合成员检查是散列+取模+散列的比较+冲突/删除的回退。没有所谓的“第一个成员”。
3. 元组在小数据上的表现优于集合——因为集合利用了很多机制。它是 O(1)，但常数在某些范围内高于 O(N) 的值。使用 10**6-length 分析您的代码，您会看到不同之处

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)

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