Python - 嵌套循环与“in”运算符导致运行时间几乎翻倍

Question

我来自 C++/Java 背景，并完成了下面“TwoNumberSum”算法的简单实现。我首先使用传统的嵌套循环以更 C/Java 的方式实现它，然后使用 'in' 运算符。我期望两者都在类似的时间内执行，因为 'in' 理想情况下也应该遍历列表，这应该会导致嵌套循环，因此在某处执行时间相似，但令我惊讶的是，第一个算法花费的时间是第二个的两倍。有人能解释一下是什么导致了运行时如此巨大的差距吗？

我在执行代码段时得到以下结果。

算法 1 的执行时间：1.023191

算法2的执行时间：0.46218059999999994

from timeit import timeit

# First Algorithm using simple lists/arrays
code1 = """
def TwoNumberSum(list, sum):

    for i in range(0, len(list)-1):
        for j in range(i+1, len(list)):
            if list[i] + list[j] == sum:
                return [list[i], list[j]]
    return []


TwoNumberSum([3, 5, -4, 8, 11, 1, -1, 6], 10)
"""
# Second Algorith similar to first using 'in' operator
code2 = """
def TwoNumberSum(list, sum):

    for i in range(0, len(list)-1):
        if sum-list[i] in list[i+1:-1]:
            return [list[i], sum-list[i]]
    return []

TwoNumberSum([3, 5, -4, 8, 11, 1, -1, 6], 10)
"""

print(f"Execution Time of Algo 1: {timeit(code1, number=100000)}")
print(f"Execution Time of Algo 2: {timeit(code2, number=100000)}")

Answer 1

Python 是一种解释型语言，其中的for循环非常慢。您可能希望它in以for循环的形式实现，并且确实如此，但它是在本地实现的（通常用 C 语言），而不是在 Python 中实现。Python 中有很多类似的函数，否则整个语言会非常慢（至少在最常见的解释器实现上，即 CPython）。

如果您关心 Python 的性能，则需要尽一切努力避免多次执行的 Python 循环。这是为什么 NumPy 存在并且大部分是用 C 编写的原因的很大一部分（因为如果使用for循环，对向量和数组的操作将永远持续下去）。

您还可以使用 C（或 C++，或其他可以公开 C 可调用函数的语言）编写自己的 Python 模块，如果您需要加速自定义循环，这将非常有用。

添加以解决用户“堆溢出”的评论：

如果输入列表很长，您需要线性时间解决方案。这是一个：

def TwoNumberSum(nums, target):
    seen = set()
    for num in nums:
        complement = target - num
        if complement in seen:
            return num, complement
        seen.add(num)

对于问题中给出的简短示例列表，这实际上更慢，但对于更长的列表会更快。但是它仍然包含forPython中的循环，这意味着它不会很快。解决这个问题的一个简单方法是使用 Numba，它会自动将 Python 的一个子集转换为机器代码：

import numba
TwoNumbaSum = numba.njit(TwoNumberSum)

Numba 需要 NumPy 数组而不是列表，所以这样称呼它：

TwoNumbaSum(np.asarray([3, 5, -4, 8, 11, 1, -1, 6]), 10)

就是这样，现在您有了一个for在 Python 中没有循环的线性时间解决方案，并且您不必编写 C 或 C++ 代码（它们运行速度一样快，但需要更多的开发工作）。