python - 嵌套循环或 'in' ，哪个更快？

Question

我是一名 Python 新手，正在研究一些基本的编码挑战，希望有人能解释以下哪些代码片段运行得更快。重点是查看列表中是否存在加起来为 100 的整数对:

list = [1,2,3,99,5]
for i in list:
    for j in list:
       if i + j == 100:
          return True 

或者:

list = [1,2,3,99,5]
for i in list: 
    diff = 100 - i 
    if diff in list:
        return True

Answer 1

基准

这个自制的随机基准测试表明，使用 in 的解决方案在大多数情况下速度明显更快。我没有调查，但我确实遇到了一些运行，其中使用嵌套 for 循环的解决方案在调整样本大小时稍微快一些。

import time, random

def time_it(f, rep=100000):
    sample = [[random.randint(0, 100) for _ in range(20)] for _ in range(rep // 100)]

    start = time.time()
    for i in range(rep):
        f(sample[i % len(sample)])
    return (time.time() - start)

def nested_for(lst):
    for i in lst:
        for j in lst:
            if i + j == 100:
                return True

def nested_in(lst):
    for i in lst:
        diff = 100 - i
        if diff in lst:
            return True

print('for:', time_it(nested_for))
print('in:', time_it(nested_in))

输出

for: 0.7093353271484375
in: 0.24253296852111816

在每次迭代中删除 j 的分配可能会消除 in 解决方案中的大量开销。

改进

尽管请注意，这两个解决方案都是O(n²)。您可以通过使用集合来实现O(n)。由于 set 对其项进行哈希处理，因此查找时间为 O(1)。

def contains_diff(lst):
    elements = set(lst)
    return any(100 - i in elements for i in elements)

print(contains_diff([1, 2, 3, 99])) # True
print(contains_diff([1, 2, 3])) # False

有趣的是，如果您对上述内容进行基准测试，它通常会比 in 解决方案慢。这是因为在随机列表中快速找到 100 总和的概率相对较高。如果您让想要查找的差异不断增长，那么构建 set 的开销将通过 set 查找的速度迅速得到补偿。

旁注

作为旁注，您不应使用 list 作为变量名称，因为它会覆盖内置 list。