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

Question

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

10

我目前正在解决欧拉计划中的问题，到目前为止，我已经为一个问题想出了这段代码。

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)

我试图通过禁用垃圾回收来防止这种情况发生，但从Google上得到的信息中我还没有成功。我这样做是错的吗？在我的脑海中，这似乎是最自然的方法，但我现在感到很困惑。

另外一提：我正在使用PyPy 2.0 Beta2（Python 2.7.4），因为它比我使用过的任何其他Python实现都要快得多，而Scipy / Numpy超出了我的能力范围，因为我还只是一个初学者，而且我没有工程或强大的数学背景。

- Jesse Neff

1

64位，8 GB内存，尽管PyPy是32位的，如果这也有所不同。 - Jesse Neff

2

你似乎在某个地方有一个错误。如果在findanums运行之后打印len(anums)，它会显示28123，这意味着从1到28123的每个数字都是过剩数。我认为这不正确。 - Kevin

Python 64位版本也支持吗？ - Ofiris

改为 for j in range(1, i) @Ofiris - Jesse Neff

@JesseNeff，也要使用xrange，这可以在我的机器上节省10秒钟的时间。 - Ofiris

显示剩余3条评论

3个回答

2

我建议你使用生成器。尝试将以下代码进行更改：

sums = map(lambda x: x[0]+x[1], pairs)

to

sums = (a+b for (a,b) in pairs)

Ofiris的解决方案也可以，但是它意味着itertools.combinations返回一个列表，这是错误的。如果您打算继续解决Project Euler问题，请查看itertools文档。

- Alex

“combinations” 返回列表时，它是错误的，这句话的意思是什么？ - Jesse Neff

1

我说组合返回一个“列表”，这是不正确的，但无论如何已经修复了。 - Ofiris

1

组合是一个生成器，所以你不需要担心pairs = combinations(anums, 2)会消耗大量内存。而且这是非常好的实践 :) - Alex

@Alex，我也想到了，正是元组求和的映射导致了内存错误。 - Jesse Neff

1

问题在于anums很大——约为28000个元素长。所以pairs必须是28000*28000*8字节=6GB。如果您使用numpy，可以将anums转换为numpy.int16数组，这样结果对会更易处理，只有1.5GB大小：

import numpy as np
#cast
anums = np.array([anums],dtype=np.int16)
#compute the sum of all the pairs via outer product
pairs = (anums + anums.T).ravel()

- Patrick Mineault

1

正如我在帖子中所说，我还是个新手，numpy的魔力目前还超出了我的理解范围，因为我仍在学习普通的Python库。但是我非常感谢这个答案，因为它让我尝到了一旦我学会足够使用numpy/scipy后我能做些什么！ - Jesse Neff

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Ofiris · Accepted Answer

正如Kevin在评论中提到的那样，您的算法可能是错误的，但是无论如何，您的代码都没有经过优化。

在使用非常大的列表时，通常会使用generators，有一篇著名的Stackoverflow答案解释了yield和generator的概念-Python中的“yield”关键字是什么？

问题在于您的pairs = combinations(anums, 2)没有生成一个generator，而是生成了一个更消耗内存的大对象。

我更改了您的代码以使用此函数，因为您只需要迭代一次集合，因此可以延迟计算值：

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

现在不再使用生成大对象的pairs = combinations(anums, 2)，请使用：

pairs = generator_sol(anums, 2)

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

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

另一个提示，你最好看一下xrange，它更加适合，它不会生成列表，而是生成一个xrange对象，在许多情况下（比如这里）更加高效。