有办法避免这种内存错误吗? [英] Is there a way to avoid this memory error?

问题描述

我目前正在解决Euler项目上的问题，到目前为止，我已经提出了解决此问题的代码.

I'm currently working through the problems on Project Euler, and so far I've come up with this code for a problem.

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.

When I run this I run into a MemoryError.

回溯:

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

我试图通过禁用垃圾收集来阻止垃圾收集，但我没有从谷歌那里获得垃圾收集.我是否以错误的方式来处理?在我的脑海中，这感觉是最自然的方式，而此时我感到茫然.

I've tried to prevent it by disabling garbage collection from what I've been able to get from Google but to no avail. Am I approaching this the wrong way? In my head this feels like the most natural way to do it and I'm at a loss at this point.

侧注:我正在使用PyPy 2.0 Beta2(Python 2.7.4)，因为它比我使用的任何其他python实现都要快得多，而且Scipy/Numpy令我头疼，因为我仍然才刚刚开始编程，我没有工程学或扎实的数学背景.

SIDE NOTE: I'm using PyPy 2.0 Beta2(Python 2.7.4) because it is so much faster than any other python implementation I've used, and Scipy/Numpy are over my head as I'm still just beginning to program and I don't have an engineering or strong math background.

推荐答案

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

As Kevin mention in the comments, your algorithm might be wrong, but anyway your code is not optimized.

当使用非常大的列表时，通常使用generators，有个著名的Stackoverflow出色答案，解释了yield和generator的概念-

When using very big lists, it is common to use generators, there is a famous, great Stackoverflow answer explaining the concepts of yield and generator - What does the "yield" keyword do in Python?

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

The problem is that your pairs = combinations(anums, 2) doesn't generate a generator, but generates a large object which is much more memory consuming.

我将您的代码更改为具有此功能，因为您只对集合进行了一次迭代，所以您可以懒惰地评估值:

I changed your code to have this function, since you iterating over the collection only once, you can lazy evaluate the values:

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

现在而不是pairs = combinations(anums, 2)会生成一个大对象. 使用:

Now instead of pairs = combinations(anums, 2) which generates a large object. Use:

pairs = generator_sol(anums, 2)

然后，我将使用另一个generator:

Then, instead of using the lambda I would use another generator:

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

另一个提示，您最好查看 xrange 合适的是，它不会生成列表，而是生成一个xrange object，在许多情况下(例如此处)，效率更高.

Another tip, you better look at xrange which is more suitable, it doens't generate a list but an xrange object which is more efficient in many cases (such as here).

这篇关于有办法避免这种内存错误吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！