python pow函数的底层实现原理介绍
一、最朴素的方法和pow比较
python中求两个a的b次方,常见的方法有:pow(a,b),a**b。那么这两个是否有区别,而且他们底层是怎么实现的呢?
最容易想到的方法就是:循环b次,每次都乘以a。但是究竟底层是不是这样实现的呢?
下面先从时间上来判断他们之间的关系。
首先来看看,pow和**有没有区别:
importtime 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循环模拟的结果
importtime 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 foriinrange(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
具体实现程序如下:
deffun(a,b): r=1 whileb>1: ifb&1==1:#与运算一般可以用于取某位数,这里就是取最后一位。 r*=a a*=a b=b>>1#这里等价于b//=2 returnr*a
接下我们来看看,究竟pow函数底层是不是这样实现的
importtime 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 foriinrange(1000000): r*=2 end2=time.time() print('for:',end2-end1) print(fun(2,1000000)) print('fun:',time.time()-end2)
从上面可以看出来,pow函数运行的时间基本和自定义的函数一致,甚至自定制的还更快!
解析完毕!
补充:Python3的pow函数用法及效率
Python3自带pow函数:
1.pow(a,b)表示求a的b次方a^b
2.pow(a,b,c)表示求a的b次方取余ca^b%c
然后用pow函数求出来的a^b%c时间上可以与“快速幂取模算法”相媲美!
以上为个人经验,希望能给大家一个参考,也希望大家多多支持毛票票。如有错误或未考虑完全的地方,望不吝赐教。
声明:本文内容来源于网络,版权归原作者所有,内容由互联网用户自发贡献自行上传,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任。如果您发现有涉嫌版权的内容,欢迎发送邮件至:czq8825#qq.com(发邮件时,请将#更换为@)进行举报,并提供相关证据,一经查实,本站将立刻删除涉嫌侵权内容。