在Python中优化生成和列表
在Python中优化生成和列表
提问于 2018-06-07 02:53:23
我正在尝试使用Python来完成以下任务:给定一组整数，生成S + S，这组整数可以表示为s1的s1 + s2，s2 S的成员(不一定是distinct)。
我使用了以下代码：
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+分钟)。
问:是什么让这一切变得缓慢？我的猜测是，询问sum是否已经是列表中的成员需要一些时间，但我是Python和编程的新手，所以我不确定。我也在寻找关于如何快速完成生产S + S的任务的建议。
回答 1
Stack Overflow用户
回答已采纳
发布于 2018-06-07 02:58:25
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比较)。相比之下，O(n^2)是set的解决方案。它不需要检查特定的和是否已经在set中，从而实现了这一点。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/50727616
复制相关文章
相似问题