3

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

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

算法一的执行时间：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)}")
4

1 回答 1

5

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++ 代码（运行速度一样快，但需要更多的开发工作）。

于 2020-02-16T09:16:35.657 回答