5

我需要在 Python 中执行此操作。有一个给定的列表 l，可能包含超过 5000 个整数元素。数字总和有限制，20000 或可能很高。输出应该是从列表中选择的 2 个数字的所有可能总和，例如，

l=[1,2,3,4,5,6,7,8,9]
output 
1+1,1+2,1+3,1+4,1+5,1+6...........
2+2,2+3,2+4.......
.........
.......

2,3,4,5,6... like that

我正在使用此代码，暂时执行此操作，但速度很慢

l=listgen()
p=[]
for i in range(0,len(l)):
    for j in range(i,len(l)):
        k=l[i]+l[j]
        if k not in p:
            p.append(k)
p.sort
print(p)

listgen()是生成输入列表的函数。

4

6 回答 6

10

一些老式的优化可能会为您提供比具有多个 for 循环的列表推导更容易理解的更快代码：

def sums(lst, limit):    # prevent global lookups by using a function
    res = set()          # set membership testing is much faster than lists
    res_add = res.add    # cache add method
    for i, first in enumerate(lst):   # get index and item at the same time
        for second in lst[i:]:        # one copy operation saves n index ops.
            res_add(first + second)   # prevent creation/lookup of extra local temporary
    return sorted([x for x in res if x < limit])

print sums(listgen(), 20000)

作为额外的奖励，此版本将与 psyco、cython 等进行完美优化。

更新： 当将此与其他建议进行比较时（将 listgen 替换为 range(5000)，我得到：

mine:        1.30 secs
WolframH:    2.65 secs
lazyr:       1.54 secs (estimate based on OPs timings -- I don't have Python 2.7 handy)
于 2012-08-03T09:33:03.937 回答
3

编辑： Thebjorn 说他有最有效的解决方案，我自己的测试也同意，尽管我的表现有所提高。他的代码也较少依赖于 python 版本，并且似乎经过深思熟虑并在优化方面进行了解释。你应该接受他的回答（并给他投票）。

使用itertools.combinations_with_replacement（在 python 2.7 中添加），并制作p一个set.

def sums(lst, limit):
    from itertools import combinations_with_replacement
    p = set(x + y for x, y in combinations_with_replacement(listgen(), 2))
    return sorted([x for x in p if x < limit])

由于这一行，您的代码很慢：

if k not in p: # O(N) lookup time in lists vs average case O(1) in sets

如果你只是对你的代码做一些小的改动，那么p它set就会产生很大的不同：

L = listgen()
p = set()
for i in range(0, len(L)):
    for j in range(i, len(L)):
        p.add(L[i] + L[j])
print(sorted(p))

顺便说一句，你的例子中的这一行

p.sort

没有效果。您必须调用一个方法来实际执行它，如下所示：

p.sort()
于 2012-08-03T09:13:21.523 回答
2

编辑：包括限制（不在 OP 的代码中）。

a = set(x + y for x in l for y in l)
print(sorted(x for x in a if x < limit))

这也降低了算法的复杂性（由于列表中的成员资格测试，您的算法可能是 O(n^4)）。

于 2012-08-03T09:15:27.190 回答
1

如果输入列表是排序的，当你达到限制时，你可以跳出内循环。另外，做p一套。

lst=listgen()
lst.sort()
p=set()
for i in range(0,len(lst)):
    for j in range(i,len(lst)):
        k=lst[i]+lst[j]
        if k > limit:
            break
        p.add(k)
p = sorted(p)
print(p)
于 2012-08-03T09:29:53.663 回答
1

您可以为此使用“NumPy”。这无疑为您提供了所需的性能：

import numpy as np

data = np.arange(5000)
limit = 20000
result = np.zeros(0,dtype='i4')
for i in data:
    result = np.concatenate((result,data[i]+data[i:]))
    if len(result) >= limit: break
result = result[:limit]

编辑： 我刚刚意识到限制是总和而不是元素的数量。然后代码应为：

EDIT2： 发现进一步的逻辑错误。我更正的建议是：

for idx, x in np.ndenumerate(data):
    result = np.concatenate((result,x+data[idx[0]:]))
    if x + data[-1] >= limit: break
result = result[result <= limit]
于 2012-08-03T09:40:27.583 回答
0

如果列表可以包含重复的元素，那么首先摆脱它们可能是一个明智的主意，例如将列表转换为集合。

于 2012-08-03T09:17:41.347 回答