Python的內存錯誤而迭代一個大範圍

Question

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

我得到一個MemoryError而循環到一系列的2**32。有沒有什麼辦法可以在不耗盡內存的情況下進行迭代？

Answer 1

這是當您嘗試創建一個包含第2^32個非負整數的列表（我使用Python 2.7.11在Windows 10系統上）會發生什麼：

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

可以預期的是，如果問題是有這樣的大量的內存同時項目，解決方案可能是在通過發電機同時處理一個項目......但它不是：

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

該文檔的xrange()內置函數解釋了爲什麼這個錯誤發生：

CPython的實現細節：的xrange（）是爲了簡單和快速。爲了實現這一點，實現可能會施加限制。 Python的C實現將所有參數限制爲本地C long（「short」Python整數），並且還要求元素的數量適合本地C long。

的問題是，2^32不能被作爲輸入參數，因爲數大於最大「短」整數在Python更大傳遞給xrange。試試這個說服自己：

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

你可以使用嵌套的for循環，如果你需要重複（2^34倍以下的例子）超過2^31倍進行計算：

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

上面的代碼是一個相當天真的解決方法。一個而循環似乎是一個更合適的解決方案：

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

Answer 2

對於蠻力方法中，嘗試：

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

上面將是更有效的，因爲它使用xrange到懶惰地生成的數字，並且還採用了發電機的表達與sum()，以避免產生立即丟棄的臨時數據。

但是，這仍然需要一些時間，因爲2**32是一個很大的數字。解決這個問題的聰明的方法是使用一個公式，通過@DeepSpace的建議：

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

Answer 3

1. range在內存中創建一個列表。使用xrange來獲得一個發生器對象，它一次給你一個數字。

2. 有更好的方法可以將1到n之間的一系列數字求和，例如(n(n+1))/2。