Czy istnieje sposób na uniknięcie tego błędu pamięci?

Question

Obecnie pracuję nad problemami w Projekcie Euler i do tej pory wymyśliłem ten kod dla problemu.

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 

Gdy uruchomię to biegnę do MemoryError.

traceback:

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

Próbowałem zapobiec poprzez wyłączenie zbierania śmieci z tego, co udało mi się dostać od Google, ale bezskutecznie. Czy podchodzę do tego w niewłaściwy sposób? W mojej głowie wydaje mi się to najbardziej naturalnym sposobem na zrobienie tego, a ja w tej chwili jestem bezradny.

SIDE UWAGA: Używam PyPy 2.0 Beta2 (Python 2.7.4), ponieważ jest znacznie szybszy niż jakakolwiek inna implementacja Pythona, której używałem, a Scipy/Numpy są nad moją głową, ponieważ wciąż jestem po prostu zaczynają programować i nie mam inżynierii ani silnego tła matematycznego.

Answer 1

Jak wspomina Kevin w komentarzach, Twój algorytm może być nieprawidłowy, ale w każdym razie twój kod nie jest zoptymalizowany.

Przy zastosowaniu bardzo dużych list, to jest powszechne w użyciu generators, znajduje się słynny, wielki odpowiedź Stackoverflow wyjaśnianiu pojęć yield i generator - What does the "yield" keyword do in Python?

Problemem jest to, że pairs = combinations(anums, 2) nie generuje generator , ale generuje duży obiekt, który zajmuje znacznie więcej pamięci.

zmieniłem swój kod aby mieć tę funkcję, ponieważ iteracji po kolekcji tylko raz, można leniwy oceny wartości:

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

Teraz zamiast pairs = combinations(anums, 2) która generuje duży obiekt. Zastosowanie:

pairs = generator_sol(anums, 2) 

Następnie, zamiast używania lambda użyłbym innego generator:

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

Kolejna wskazówka, lepiej przyjrzeć xrange który jest bardziej odpowiedni, doens't wygenerować listę ale xrange object, który jest bardziej wydajny w wielu przypadkach (np. tutaj).

Answer 2

Kwestia polega na tym, że anums jest duży - ma około 28 000 elementów. więc pary muszą mieć 28000 * 28000 * 8 bajtów = 6 GB. Jeśli użyto numpy można rzucić anums jako tablica numpy.int16, w którym to przypadku pary wynik byłby 1,5GB - łatwiejsze:

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

Pozwolę sobie zasugerować, aby korzystać generators. Spróbuj zmienić to:

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

do

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

rozwiązanie Ofiris jest również ok, ale zakłada, że ​​itertools.combinations zwróci listę kiedy to się stało. Jeśli masz zamiar nadal rozwiązywać problemy związane z projektami, spójrz na numer itertools documentation.