用一个变量来测试很多常量是很常见的
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)
为什么查找集合文字不是常数时间？
请您参考如下方法:
嗯，这里有几件事。
set([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])super 慢，因为它可能首先构建列表。我想，3.7+ 中有一些优化，但无论如何。因此，设置文字速度更快。- “检查第一个成员甚至有点慢”——关于集合的事情——它不是神奇的
O(1)。集合成员检查是散列+取模+散列的比较+冲突/删除的回退。没有所谓的“第一个成员”。 - 元组在小数据上的表现优于集合——因为集合利用了很多机制。它是
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)
所以你可以在这里清楚地看到什么是线性与常数。
