Python Speicherfehler, während Sie eine große Auswahl iterieren

Question

sum = 0 
x = 2**32 
for i in range(x): 
    sum=sum+i; 
print sum 

Ich erhalte eine MemoryError während einer Reihe von 2**32 Looping. Gibt es eine Möglichkeit, die Iteration auszuführen, ohne den Arbeitsspeicher zu verlieren?

Answer 1

Dies ist, was passiert, wenn Sie eine Liste zu erstellen versuchen, die ersten 2^32 nicht negativen ganzen Zahlen (Ich verwende Python 2.7.11 auf einem Windows 10-System) enthält:

>>> for i in range(2**32): pass 
... 
Traceback (most recent call last): 
    File "<stdin>", line 1, in <module> 
OverflowError: range() result has too many items 

man könnte erwarten, dass, wenn das Problem in Speicher, wie eine große Anzahl von Elementen gleichzeitig haben, könnte die Lösung sein, dass durch einen Generator zu einem Zeitpunkt ein Element der Handhabung ... aber es ist nicht:

>>> for i in xrange(2**32): pass 
... 
Traceback (most recent call last): 
    File "<stdin>", line 1, in <module> 
OverflowError: Python int too large to convert to C long 

Die Dokumentation von xrange() eingebaute Funktion erklärt, warum dieser Fehler auftritt:

CPython Implementierung Detail: xrange() soll einfach und schnell sein. Implementierungen können Einschränkungen auferlegen, um dies zu erreichen. Die C-Implementierung von Python beschränkt alle Argumente auf native C-Longs ("kurze" Python-Integer) und erfordert außerdem, dass die Anzahl der Elemente in ein natives C-Long passt.

Das Problem ist, dass 2^32 kann nicht als Eingangsargument zu xrange weitergegeben werden, weil diese Zahl größer ist als die maximale „short“ integer in Python ist. Versuchen Sie, diese selbst zu überzeugen:

>>> import sys 
>>> sys.maxint  # 2^31-1 
2147483647 
>>> sys.maxint + 1 # 2^31 is automatically converted to "long" int 
2147483648L 
>>> 2**31 
2147483648L 

Sie für verschachtelten Schleifen verwenden können, wenn Sie wiederholt ausführen müssen, eine Berechnung mehr als 2^31 mal (2^34 mal im folgenden Beispiel):

>>> loops = 0 
>>> for i in xrange(2**4): 
... for j in xrange(2**30): 
...  # do stuff 
...  loops += 1 
... 
>>> loops 
17179869184L 
>>> 2**34 
17179869184L 

Der obige Code ist eine ziemlich naive Problemumgehung.Eine während Schleife scheint eine viel angemessenere Lösung zu sein:

>>> loops = 0 
>>> while loops < 2**34: 
... # do stuff 
... loops += 1 
... 
>>> loops 
17179869184L 

Answer 2

Für einen Brute-Force-Ansatz, versuchen Sie dies:

x = sum(i for i in xrange(2**32)) 

Die oben effizienter sein wird, wie es xrange die Zahlen träge zu generieren verwendet, und es nutzt auch einen Generator Ausdruck mit sum() Erzeugungs zu vermeiden temporäre Daten, die sofort verworfen werden.

Aber das wird noch einige Zeit dauern, da 2**32 eine große Zahl ist. Die intelligente Art und Weise, dieses Problem zu lösen, ist eine Formel zu verwenden, wie @DeepSpace vorgeschlagen:

n = 2**32 - 1 
x = (n * (n + 1))/2 

Answer 3

1. range erstellt eine Liste im Speicher. Verwenden Sie xrange, um ein Generatorobjekt zu erhalten, das Ihnen eine Nummer auf einmal gibt.

2. Es gibt bessere Möglichkeiten, einen Zahlenbereich von 1 bis n zu summieren, zum Beispiel (n(n+1))/2.