このメモリエラーを回避する方法はありますか？

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

コメントにKevinが言及しているように、アルゴリズムが間違っている可能性がありますが、とにかくコードが最適化されていません。

非常に大きなリストを使用している場合、yieldの概念とgenerator説明有名な、素晴らしいstackoverflowの答えがありgeneratorsを使用するのが一般的である - 問題は、あなたのpairs = combinations(anums, 2)がgeneratorを生成しないということであるWhat does the "yield" keyword do in Python?

は、より多くのメモリを消費する大きなオブジェクトを生成します。

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でもう一つのヒント、あなたよりよい一見、それはリストを生成doens't xrange objectは多くの場合でより効率的です（ここなど）。

Answer 2

問題は、桁が大きく、約28000要素長いことです。ペアは28000 * 28000 * 8バイト= 6GBでなければなりません。あなたは、numpy.int16配列としてanumsを唱えられるnumpyのあなたが使用している場合、その場合には、結果のペアは、1.5ギガバイトだろう - より管理：

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() 

Answer 3

あなたはgeneratorsを使用することを私は提案してみましょう。これを変更してみてください：

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

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

にOfirisソリューションもOKですが、それは間違っているとき itertools.combinationsリストを返すことを意味します。あなたがプロジェクトのユーラー問題を解決し続けるつもりなら、 itertools documentationを見てください。