C'è un modo per evitare questo errore di memoria?

Question

Attualmente sto lavorando sui problemi di Project Euler, e finora ho trovato questo codice per un problema.

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 

Quando eseguo questo mi imbatto in un MemoryError.

Il traceback:

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

Ho cercato di impedirlo disabilitando la raccolta dei rifiuti da quello che ho potuto ottenere da Google, ma senza alcun risultato. Mi sto avvicinando a questo nel modo sbagliato? Nella mia testa questo mi sembra il modo più naturale per farlo e sono in perdita a questo punto.

SIDE NOTA: Sto usando PyPy 2.0 Beta2 (Python 2.7.4) perché è molto più veloce di qualsiasi altra implementazione Python che ho usato, e Scipy/Numpy sono sopra la mia testa dato che sono ancora solo inizio a programmare e non ho un background di ingegneria o matematica forte.

Answer 1

Come Kevin menziona nei commenti, il tuo algoritmo potrebbe essere sbagliato, ma in ogni caso il tuo codice non è ottimizzato.

Quando si utilizza molto grandi liste, è comune utilizzare generators, c'è un famoso, grande risposta StackOverflow spiegare i concetti di yield e generator-What does the "yield" keyword do in Python?

Il problema è che il vostro pairs = combinations(anums, 2) non genera un generator , ma genera un oggetto grande che consuma molta più memoria.

ho cambiato il codice per avere questa funzione, dal momento che l'iterazione sulla raccolta solo una volta, pigri è possibile valutare i valori:

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

Ora, invece di pairs = combinations(anums, 2) che genera un oggetto di grandi dimensioni. Usa:

pairs = generator_sol(anums, 2) 

Poi, invece di utilizzare il lambda userei un'altra generator:

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

Un altro suggerimento, è meglio guardare xrange, che è più adatto, si doens't generare un elenco ma un xrange object che è più efficiente in molti casi (come qui).

Answer 2

Il problema è che le anum sono grandi - lunghe circa 28.000 elementi. quindi le coppie devono essere 28000 * 28000 * 8 byte = 6 GB. Se è stato utilizzato NumPy potresti lanciare anums come un array numpy.int16, nel qual caso le coppie risultato sarebbe 1.5GB - più gestibile:

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

Mi permetto di suggerire di utilizzare generators. Prova a cambiare questo:

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

a

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

soluzione Ofiris è anche ok, ma implica che itertools.combinations restituisce un elenco quando è sbagliato. Se continuerai a risolvere i problemi del progetto euler, dai uno sguardo allo itertools documentation.