誰(shuí)說(shuō)Python慢來(lái)著？不用Python，這個(gè)問(wèn)題難倒了無(wú)數(shù)的程序員

（點(diǎn)擊上方快速關(guān)注并設(shè)置為星標(biāo)，一起學(xué)Python）

作者 | 天元浪子       責(zé)編 | 歐陽(yáng)姝黎

出品 | CSDN博客

圍棋是全世界最古老的棋種（沒(méi)有之一），也是古代哲學(xué)思想和中國(guó)傳統(tǒng)文化的物質(zhì)載體。小小紋枰，不過(guò)一尺見(jiàn)方，竟蘊(yùn)藏著萬(wàn)千氣象，著實(shí)令人為之著迷。少年時(shí)代的我，曾經(jīng)有一段時(shí)間醉心于圍棋。

標(biāo)準(zhǔn)的圍棋盤由橫豎各19道線組成網(wǎng)格，共有361個(gè)交叉點(diǎn)，每個(gè)交叉點(diǎn)上有白子、黑子和無(wú)子等三種可能的狀態(tài)。那么問(wèn)題來(lái)了：圍棋總共有多少種不同的局面呢？

稍微思考一下，所有的程序員都會(huì)給出正確的答案：3^{361}（3的361次方）。可是，這究竟是一個(gè)多大的數(shù)字呢？算一下就知道了。

Python程序員隨手寫了一行代碼，敲個(gè)回車，計(jì)算就結(jié)束了。

>>> pow(3,361)17408965065903192790718823807056436794660272495026354119482811870680105167618464984116279288988714938612096988816320780613754987181355093129514803369660572893075468180597603

C/C++程序員看完P(guān)ython程序員的操作，不以為然，心里想，別看你寫起來(lái)簡(jiǎn)單，速度肯定沒(méi)我快。講效率，還得看我C/C++的。

long result = 1int ifor(i=0; i<361; i++) {  result *= 3;}

寫到這里，C/C++程序員忽然意識(shí)到，long int恐怕不夠用，即使long long int也只有8個(gè)字節(jié)，最大只能到2^{64}-1計(jì)算3^{361}肯定會(huì)溢出的。比long long更大的整型沒(méi)有了，要是臨時(shí)定義一個(gè)結(jié)構(gòu)保存超大整數(shù)，再為超大整數(shù)的計(jì)算寫一堆函數(shù)，恐怕一時(shí)半會(huì)兒搞不定。這可如何是好？要不用改用double float試試？趕緊上網(wǎng)查了一下，double可以表示-1.79E+308 ~ +1.79E+308之間的任意數(shù)，可是3^{361}3在這個(gè)范圍內(nèi)嗎？

這時(shí)，C/C++程序員心里有點(diǎn)慌了。幸好有點(diǎn)數(shù)學(xué)功底，簡(jiǎn)單計(jì)算一下:

3^{361}大約有173位長(zhǎng)，總算還在double覆蓋的范圍之內(nèi)。也不用循環(huán)了，直接使用數(shù)學(xué)庫(kù)中的pow函數(shù)吧。

#include <stdio.h>#include <math.h>
int main(void) {    double result = pow(3,361);    printf("%Lf\n", result);
    return 0;}

最后，C/C++程序員給出了一個(gè)浮點(diǎn)類型的答案。雖然精度略有損失，但也不算離譜。我用的是CodeBlocks，顯示耗時(shí)28毫秒，這里面應(yīng)當(dāng)包括了編譯連接的時(shí)間，否則C不至于慢到這個(gè)程度。

17408965065903191000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000.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用起來(lái)很方便，計(jì)算3^{361}毫無(wú)壓力，只是不能兼容普通整型的那些運(yùn)算符號(hào)，所有的運(yùn)算都需要顯式地調(diào)用函數(shù)，比如，這里的乘法就得調(diào)用multiply函數(shù)。

以上場(chǎng)景，純屬臆測(cè)，絕無(wú)褒貶任何編程語(yǔ)言之意，請(qǐng)各位明察。實(shí)際上，Python的超大整數(shù)計(jì)算也是C語(yǔ)言實(shí)現(xiàn)的，只不過(guò)采用了非常精妙的方案，最終經(jīng)過(guò)各種優(yōu)化，性能遠(yuǎn)超我們自己寫出來(lái)的C代碼。

Python的超大整數(shù)計(jì)算方案，精妙在哪兒呢？?jī)H舉存儲(chǔ)一例：普通的Python整型采用4個(gè)字節(jié)存儲(chǔ)，當(dāng)處理超大整數(shù)時(shí)，每4個(gè)字節(jié)一個(gè)存儲(chǔ)單元，單元之間采用2^{30}

即1073741824進(jìn)制，一個(gè)單元滿1073741824即向上一單元進(jìn)位。

Python超大整數(shù)的存儲(chǔ)實(shí)現(xiàn)

上圖是超大整數(shù)1152921506754330627采用1073741824進(jìn)制的存儲(chǔ)示意圖，占用了三個(gè)存儲(chǔ)單元共計(jì)12個(gè)字節(jié)，每個(gè)單元仍然是普通的整型——這就是Python的超大整型和普通整型完全兼容的秘密。在這一點(diǎn)上，Python可以說(shuō)完勝Java的BigInteger。不過(guò)Java還有個(gè)BigDecimal，可以無(wú)損地處理任意精度的浮點(diǎn)數(shù)，為Java扳回一局。

采用1073741824進(jìn)制的Python的超大整數(shù)計(jì)算方案的效率如何呢？還是以計(jì)算3^{361}為例，看Python代碼需要多長(zhǎng)時(shí)間。

>>> import time>>> def power(x, base=2):  t0 = time.time()  result = pow(base, x)  print('耗時(shí)%.06f秒'%(time.time()-t0))  return result
>>> power(361, base=3)耗時(shí)0.000000秒17408965065903192790718823807056436794660272495026354119482811870680105167618464984116279288988714938612096988816320780613754987181355093129514803369660572893075468180597603

太神奇了！居然連1微秒都不到？我有點(diǎn)懷疑這個(gè)結(jié)論，繼續(xù)測(cè)試更大的數(shù)字，2的1000次方。

>>> power(1000)耗時(shí)0.000000秒10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046474983581941267398767559165543946077062914571196477686542167660429831652624386837205668069376

計(jì)算2^{1000}所花時(shí)間同樣少于1微秒，但是顯示計(jì)算結(jié)果花費(fèi)了較長(zhǎng)時(shí)間。我把代碼修改了一下，不再顯示計(jì)算結(jié)果，只考察計(jì)算時(shí)間。

>>> def power(x, base=2):  t0 = time.time()  result = pow(base, x)  print('耗時(shí)%.06f秒'%(time.time()-t0))  #return result
  >>> power(10000) # 2的1萬(wàn)次方耗時(shí)0.000000秒>>> power(100000) # 2的10萬(wàn)次方耗時(shí)0.000000秒>>> power(1000000) # 2的100萬(wàn)次方耗時(shí)0.005016秒>>> power(10000000) # 2的1千萬(wàn)次方耗時(shí)0.048000秒>>> power(100000000) # 2的1億次方耗時(shí)0.620648秒>>> power(1000000000) # 2的10億次方耗時(shí)7.448035秒>>> power(10000000000) # 2的100億次方耗時(shí)77.881435秒

計(jì)算2的1萬(wàn)次方和2的10萬(wàn)次，所花時(shí)間仍然不足1微秒。直到計(jì)算2的100萬(wàn)次方時(shí)，方才顯示耗時(shí)5毫秒。當(dāng)算完2的100億次方之后，我沒(méi)有繼續(xù)下去——2的100億次方，這個(gè)數(shù)字實(shí)在是太過(guò)恐怖，我已經(jīng)無(wú)法想象它的大小了。要知道，地球上全部物質(zhì)的原子數(shù)量，也不過(guò)是1.28E47這個(gè)量級(jí)，大約是2的157次方。

那么，Python能夠計(jì)算的最大整數(shù)到底有多大呢？我沒(méi)有明確的概念，不過(guò)我在驗(yàn)證費(fèi)馬小定理的逆命題時(shí)，出現(xiàn)過(guò)一次超大整數(shù)計(jì)算錯(cuò)誤。

a = 2t = 2305843009213693951s = 1152921504606846975Traceback (most recent call last):  File "huge.py", line 56, in <module>    miller_rabin(x) # M61  File "huge.py", line 42, in miller_rabin    print((pow(a, t*pow(2,s)) - 1)%huge_num)MemoryError

當(dāng)我試圖計(jì)算pow(a, t*pow(2,s)時(shí)，發(fā)生了內(nèi)存錯(cuò)誤。這里a等于2，s大于115億億，t大于230億億。顯然，這個(gè)結(jié)果遠(yuǎn)遠(yuǎn)大于2的100億次方。

（完）