10

我目前正在解决 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 已经超出了我的想象，因为我还刚刚开始编程和我没有工程学或强大的数学背景。

4

3 回答 3

4

正如凯文在评论中提到的那样，您的算法可能是错误的，但无论如何您的代码并未优化。

当使用非常大的列表时，通常使用generators，有一个著名的、很棒的 Stackoverflow 答案解释了yield和的概念generator—— “yield”关键字在 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)which 生成一个大对象。利用：

pairs = generator_sol(anums, 2)

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

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

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

于 2013-04-18T20:30:06.060 回答
2

让我建议你使用generators。尝试改变这个：

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

至

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

Ofiris 解决方案也可以，但意味着itertools.combinations在错误时返回一个列表。如果您要继续解决项目欧拉问题，请查看itertools 文档。

于 2013-04-18T20:40:21.453 回答
1

问题是 anums 很大——大约有 28000 个元素长。所以对必须是 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()
于 2013-04-18T20:37:02.360 回答