一、最樸素的方法和pow比較
python中求兩個a的b次方,常見的方法有:pow(a,b),a**b。那麼這兩個是否有差別,而且他們底層是怎麼實作的呢?
最容易想到的方法就是:循環b次,每次都乘以a。但是究竟底層是不是這樣實作的呢?
下面先從時間上來判斷他們之間的關系。
首先來看看,pow和**有沒有差別:
import time
start = time.time()
print(2 ** 1000000)
end0 = time.time()
print('**:', end0 - start)
print(pow(2, 1000000))
end1 = time.time()
print('pow:', end1 - end0)
上面的結果輸出如下:
2的100萬次方,兩者所用時間是基本一樣的,是以他們應該本質上應該使用了相同的算法
下面再來看看用for循環模拟的結果
import time
start = time.time()
print(2 ** 1000000)
end0 = time.time()
print('**:', end0 - start)
print(pow(2, 1000000))
end1 = time.time()
print('pow:', end1 - end0)
r = 1
for i in range(1000000):
r *= 2
end2 = time.time()
print('for:', end2 - end1)
上面的輸入結果如下:
非常恐怖的對比,pow和**都隻用了1.5秒,而for循環用來20秒!,是以可以肯定的是,pow底層絕對不是用循環去求解的
pow底層實作
我們分析一下為什麼直接循環相乘效率會這麼低,我們其實不難發現裡面有大量的重複運算,比如我們算出22後面,還不斷重複着計算22的結果,是以我們隻要儲存這些中間必要的計算結果後你不斷重複利用就可以大大減少運算量。舉個例子,比如我們現在在計算2的9次方,我們可以這樣子計算,先算出22然後不斷利用這個結果:
(22)(22)(22)(22)2 即44442 隻要計算5次
同理可以再利用上面的44 可以的16162
具體實作程式如下:
def fun(a, b):
r = 1
while b > 1:
if b & 1 == 1: #與運算一般可以用于取某位數,這裡就是取最後一位。
r *= a
a *= a
b = b >> 1 #這裡等價于b//=2
return r * a
接下我們來看看,究竟pow函數底層是不是這樣實作的
import time
start = time.time()
print(2 ** 1000000)
end0 = time.time()
print('**:', end0 - start)
print(pow(2, 1000000))
end1 = time.time()
print('pow:', end1 - end0)
r = 1
for i in range(1000000):
r *= 2
end2 = time.time()
print('for:', end2 - end1)
print(fun(2, 1000000))
print('fun:', time.time() - end2)
從上面可以看出來,pow函數運作的時間基本和自定義的函數一緻,甚至自定制的還更快!
解析完畢!