python - 键入 s 与键入不键入 s 速度

Question

我有这个代码:

s = set([5,6,7,8])

if key in s:
    return True

if key not in s:
    return False

在我看来，从理论上讲，它不应该在时间上有所不同，但我可能在幕后遗漏了一些东西。

在处理时间或可读性方面是否有任何理由选择其中一种？

也许这是一个例子:

"Premature optimization is the root of all evil"?

<小时/>

简短回答:不，没有区别。是的，可能是过早的优化。

<小时/>

好的，我运行了这个测试:

import random
s = set([5,6,7,8])
for _ in range(5000000):
    s.add(random.randint(-100000,100000000))

def test_in():
    count = 0
    for _ in range(50000):
        if random.randint(-100000,100000000) in s:
            count += 1
    print(count)

def test_not_in():
    count = 0
    for _ in range(50000):
        if random.randint(-100000,100000000) not in s:
            count += 1
    print(count)

当我对输出进行计时时:

%timeit test_in()
10 loops, best of 3: 83.4 ms per loop

%timeit test_not_in()
10 loops, best of 3: 78.7 ms per loop

但是，这种微小的差异似乎是计算组件的症状。平均有 47500 个“not in”，但只有 2500 个“ins”。如果我更改两个测试以通过，例如:

def test_in():
    for _ in range(50000):
        if random.randint(-100000,100000000) in s:
            pass

结果几乎相同

%timeit test_in()
10 loops, best of 3: 77.4 ms per loop

%timeit test_not_in()
10 loops, best of 3: 78.7 ms per loop

在这种情况下，我的直觉失败了。我原以为说它不在集合中可能会增加一些额外的处理时间。当我进一步考虑 HashMap 的作用时，很明显事实并非如此。

Answer 1

您不应该看到差异。集合中的查找时间是恒定的。您对条目进行哈希处理，然后在 HashMap 中查找它。所有键都会同时检查，并且 in 和 not in 应该具有可比性。