python - 优化在 Python 中生成总和列表

Question

我正在尝试使用 Python 完成以下任务:给定一组整数 S，生成 S + S，该整数集可表示为 s1 + s2 用于 s1，s2 的 S 成员(不一定不同)。

我正在使用以下代码:

def sumList(l):
    # generates a list of numbers which are sums of two elements of l
    sumL = []
    howlong = len(l)
    for i in range(howlong):
        for j in range(i+1):
            if not l[i]+l[j] in sumL:
                sumL.append(l[i]+l[j])
    return sumL

这对于足够短的列表来说效果很好，但是当处理一个较长的列表(比如 0 到 20000 之间的 5000 个元素)时，速度会非常慢(20 分钟以上)。

问题:是什么让它变慢了？我的猜测是询问总和是否已经是列表的成员需要一些时间，但我是 Python 和编程的新手，所以我不确定。我也在寻找有关如何快速执行生成 S + S 任务的建议。

Answer 1

Python 有一个内置的类型 set，它的查找速度非常快。您不能在集合中存储重复项或不可散列的对象，但由于您需要一组整数，它非常适合您的需要。在下面，我也使用 itertools.product生成对。

from itertools import product

def sums(l):
    return {x+y for x, y in product(l, repeat=2)}

print(sums([1, 2, 3, 4]))
# {2, 3, 4, 5, 6, 7, 8}

至于为什么您现有的解决方案如此缓慢，您可能需要查找术语“算法复杂性”。基本上，这是一种根据算法对许多输入的扩展程度将算法分类为一般组的方法。您的算法是一个O(n^3) 算法(它将进行n^3 比较)。相比之下，set 的解决方案是O(n^2)。它通过放弃检查特定金额是否已经在 set 中的需要来实现这一点。