誰說Python慢來著？不用Python，這個問題難倒了無數的程序員
圍棋是全世界最古老的棋種（沒有之一），也是古代哲學思想和中國傳統文化的物質載體。小小紋枰，不過一尺見方，竟蘊藏著萬千氣象，著實令人為之著迷。少年時代的我，曾經有一段時間醉心于圍棋。
標準的圍棋盤由橫豎各19道線組成網格，共有361個交叉點，每個交叉點上有白子、黑子和無子等三種可能的狀態。那么問題來了：圍棋總共有多少種不同的局面呢？
稍微思考一下，所有的程序員都會給出正確的答案：
3
361
3^{361}
3361（3的361次方）。可是，這究竟是一個多大的數字呢？算一下就知道了。
Python程序員隨手寫了一行代碼，敲個回車，計算就結束了。
>>> pow(3,361) 174089650659031927907188238070 564367946602724950263541194828 118706801051676184649841162792 889887149386120969888163207806 137549871813550931295148033696 60572893075468180597603
C/C++程序員看完Python程序員的操作，不以為然，心里想，別看你寫起來簡單，速度肯定沒我快。講效率，還得看我C/C++的。
long result = 1 int i for(i=0; i<361; i++) { result *= 3; }
寫到這里，C/C++程序員忽然意識到，long int恐怕不夠用，即使long long int也只有8個字節，最大只能到
2
64
?
1
2^{64}-1
264?1，計算
3
361
3^{361}
3361肯定會溢出的。比long long更大的整型沒有了，要是臨時定義一個結構保存超大整數，再為超大整數的計算寫一堆函數，恐怕一時半會兒搞不定。這可如何是好？要不用改用double float試試？趕緊上網查了一下，double可以表示-1.79E+308 ~ +1.79E+308之間的任意數，可是
3
361
3^{361}
3361在這個范圍內嗎？
這時，C/C++程序員心里有點慌了。幸好有點數學功底，簡單計算一下:
l
o
g
10
3
361
=
361
×
l
o
g
10
3
≈
172.24077295379814
log_{10}{3^{361}}=361\times log_{10}3\approx172.24077295379814
log10 3361=361×log10 3≈172.24077295379814
3
361
3^{361}
3361大約有173位長，總算還在double覆蓋的范圍之內。也不用循環了，直接使用數學庫中的pow函數吧。
#include
最后，C/C++程序員給出了一個浮點類型的答案。雖然精度略有損失，但也不算離譜。我用的是CodeBlocks，顯示耗時28毫秒，這里面應當包括了編譯連接的時間，否則C不至于慢到這個程度。
174089650659031910000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 00000000000000000000000.000000 Process returned 0 (0x0) Execution time : 0.028 s
看完C/C++程序員的這番折騰，Java程序員擦擦額頭的冷汗，心中暗自慶幸：多虧我大Java有BigInteger這樣的神器，不然真要出丑了。
import java.math.BigInteger; BigInteger result = new BigInteger("1"); for(int i=1; i<=361; i++) { result.multiply(new BigInteger("3"))); }
BigInteger用起來很方便，計算
3
361
3^{361}
3361毫無壓力，只是不能兼容普通整型的那些運算符號，所有的運算都需要顯式地調用函數，比如，這里的乘法就得調用multiply函數。
以上場景，純屬臆測，絕無褒貶任何編程語言之意，請各位明察。實際上，Python的超大整數計算也是C語言實現的，只不過采用了非常精妙的方案，最終經過各種優化，性能遠超我們自己寫出來的C代碼。
Python的超大整數計算方案，精妙在哪兒呢？僅舉存儲一例：普通的Python整型采用4個字節存儲，當處理超大整數時，每4個字節一個存儲單元，單元之間采用
2
30
2^{30}
230即1073741824進制，一個單元滿1073741824即向上一單元進位。
采用1073741824進制的Python的超大整數計算方案的效率如何呢？還是以計算
3
361
3^{361}
3361為例，看Python代碼需要多長時間。
>>> import time >>> def power(x, base=2): t0 = time.time() result = pow(base, x) print('耗時%.06f秒'%(time.time()-t0)) return result >>> power(361, base=3) 耗時0.000000秒 174089650659031927907188238070 564367946602724950263541194828 118706801051676184649841162792 889887149386120969888163207806 137549871813550931295148033696 60572893075468180597603
太神奇了！居然連1微秒都不到？我有點懷疑這個結論，繼續測試更大的數字，2的1000次方。
>>> power(1000) 耗時0.000000秒 107150860718626732094842504906 000181056140481170553360744375 038837035105112493612249319837 881569585812759467291755314682 518714528569231404359845775746 985748039345677748242309854210 746050623711418779541821530464 749835819412673987675591655439 460770629145711964776865421676 604298316526243868372056680693 76
計算
2
1000
2^{1000}
21000所花時間同樣少于1微秒，但是顯示計算結果花費了較長時間。我把代碼修改了一下，不再顯示計算結果，只考察計算時間。
>>> def power(x, base=2): t0 = time.time() result = pow(base, x) print('耗時%.06f秒'%(time.time()-t0)) #return result >>> power(10000) # 2的1萬次方 耗時0.000000秒 >>> power(100000) # 2的10萬次方 耗時0.000000秒 >>> power(1000000) # 2的100萬次方 耗時0.005016秒 >>> power(10000000) # 2的1千萬次方 耗時0.048000秒 >>> power(100000000) # 2的1億次方 耗時0.620648秒 >>> power(1000000000) # 2的10億次方 耗時7.448035秒 >>> power(10000000000) # 2的100億次方 耗時77.881435秒
計算2的1萬次方和2的10萬次，所花時間仍然不足1微秒。直到計算2的100萬次方時，方才顯示耗時5毫秒。當算完2的100億次方之后，我沒有繼續下去——2的100億次方，這個數字實在是太過恐怖，我已經無法想象它的大小了。要知道，地球上全部物質的原子數量，也不過是1.28E47這個量級，大約是2的157次方。
那么，Python能夠計算的最大整數到底有多大呢？我沒有明確的概念，不過我在驗證費馬小定理的逆命題時，出現過一次超大整數計算錯誤。
a = 2 t = 2305843009213693951 s = 1152921504606846975 Traceback (most recent call last): File "huge.py", line 56, in
當我試圖計算pow(a, t*pow(2,s)時，發生了內存錯誤。這里a等于2，s大于115億億，t大于230億億。顯然，這個結果遠遠大于2的100億次方。
Python 開發者
版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。
版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。
相關文章
