Bu bellek hatasını önlemek için bir yol var mı?

Question

Şu anda Project Euler'daki problemler üzerinde çalışıyorum ve şu ana kadar bir sorun için bu kod ile geldim. Bunu çalıştırdığınızda

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 

Ben MemoryError içine çalıştırın.

geri izleme: Ben Google'dan ama boşuna almak mümkün oldum ne çöp toplama devre dışı bırakarak bunu önlemek için çalıştık

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

. Buna yanlış yoldan mı yaklaşıyorum? Kafamda, bunu yapmanın en doğal yolu gibi hissettiriyor ve bu noktada bir kayıp yaşıyorum.

YAN NOT: PyPy 2.0 Beta2'yi (Python 2.7.4) kullanıyorum çünkü kullandığım diğer tüm python uygulamalarından çok daha hızlı ve Scipy/Numpy başımın üstündeymiş gibi. programlamaya başlıyor ve mühendislik ya da güçlü bir matematik altyapım yok.

Answer 1

Kevin yorumlarda bahsettiği gibi, algoritmanız yanlış olabilir, ancak yine de kodunuz optimize edilmemiştir.

çok büyük listelerini kullanırken,, yield kavramlarını ve generator açıklayan ünlü, büyük Stackoverflow cevap var generators kullanımı yaygındır - Sorun senin pairs = combinations(anums, 2) bir generator oluşturmak olmamasıdır What does the "yield" keyword do in Python?

ancak daha fazla bellek tüketen büyük bir nesne oluşturur.

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

Şimdi yerine büyük bir nesne oluşturur pairs = combinations(anums, 2) arasında: sadece bir kez koleksiyonu üzerinde yineleme beri

Ben tembel değerlerini değerlendirebilir, bu işlevi olması kodunuzu değiştirdi. Kullanım: yerine lambda kullanmanın

pairs = generator_sol(anums, 2) 

Sonra ben başka generator kullanır: daha uygundur xrange de

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

başka ipucu, daha iyi bir görünüm, bir liste oluşturmak doens't ancak birçok durumda (burada olduğu gibi) daha verimli olan bir xrange object.

Answer 2

Sorun, anemlerin büyük olmasıdır - yaklaşık 28000 eleman. çiftler 28000 * 28000 * 8 bayt = 6GB olmalıdır. Eğer bir numpy.int16 dizi olarak anums döküm olabilir numpy Eğer kullanılırsa bu durumda sonuç çiftleri 1.5GB olacak - daha yönetilebilir:

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

Eğer generators kullanmak beni düşününüz!. Bu değiştirmeyi deneyin:

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

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

için Ofiris çözümü de Tamam ama yanlış olduğunda itertools.combinations listesini döndürür anlamına gelmektedir. Eğer proje euler problemlerini çözmeye devam edecekseniz, itertools documentation'a bir göz atın.