有没有办法避免这种内存错误？

Question

我目前正在解决Project Euler上的问题,到目前为止,我已经提出了这个问题的代码.

from itertools import combinations
import time

def findanums(n):
    l = []
    for i in range(1, n + 1):
        s = []
        for j in range(1, i):
            if i % j == 0:
                s.append(j)
        if sum(s) > i:
            l.append(i)
    return l

start = time.time() #start time

limit = 28123

anums = findanums(limit + 1) #abundant numbers (1..limit)
print "done finding abundants", time.time() - start

pairs = combinations(anums, 2)
print "done finding combinations", time.time() - start

sums = map(lambda x: x[0]+x[1], pairs)
print "done finding all possible sums", time.time() - start

print "start main loop"
answer = 0
for i in range(1,limit+1):
    if i not in sums:
        answer += i
print "ANSWER:",answer

当我运行这个时,我遇到了一个MemoryError.

追溯:

File "test.py", line 20, in <module>
    sums = map(lambda x: x[0]+x[1], pairs)

我试图通过从谷歌获得的垃圾收集来禁止它,但无济于事.我是以错误的方式接近这个吗？在我的脑海中,这感觉就像最自然的方式,而且我现在处于亏损状态.

侧面注意:我正在使用PyPy 2.0 Beta2(Python 2.7.4),因为它比我使用过的任何其他python实现都要快得多,并且Scipy/Numpy在我的脑海中,因为我还在开始编程和我没有工程学或强大的数学背景.

Answer 1

正如凯文在评论中提到的，你的算法可能是错误的，但无论如何你的代码没有优化。

当使用非常大的列表时，通常使用generators，有一个著名的、很棒的 Stackoverflow 答案解释了yield和的概念generator- What does the "yield" keywords do in Python?

问题是您pairs = combinations(anums, 2)不会生成 a generator，而是生成一个消耗更多内存的大对象。

我更改了您的代码以具有此功能，因为您仅迭代集合一次，所以您可以延迟计算值：

def generator_sol(anums1, s):
      for comb in itertools.combinations(anums1, s):
        yield comb

现在取而代之的pairs = combinations(anums, 2)是生成一个大对象。使用：

pairs = generator_sol(anums, 2)

然后，lambda我将使用另一个而不是使用generator：

sums_sol = (x[0]+x[1] for x in pairs)

另一个提示，您最好看看xrange哪个更合适，它不会生成列表，而是xrange object在许多情况下（例如这里）更有效。