小编典典

计算能力的速度(在Python中)

algorithm

我很好奇为什么乘以比在python中取幂要快得多(尽管据我所读,这在许多其他语言中也可能是正确的)。例如,这样做快得多

x*x

x**2

我认为**运算符比较笼统,也可以处理小数幂。但是,如果这就是为什么它这么慢,为什么不执行int指数检查,然后执行乘法运算呢?

编辑: 这是我尝试过的一些示例代码…

def pow1(r, n):
  for i in range(r):
    p = i**n

def pow2(r, n):
  for i in range(r):
    p = 1
    for j in range(n):
      p *= i

现在,pow2只是一个简单的例子,显然没有进行优化!
但是即使如此,我仍然发现使用n = 2且r = 1,000,000时,pow1约需2500ms,pow2需约1700ms。
我承认对于较大的n值,pow1的确比pow2快得多。但这并不奇怪。


阅读 298

收藏
2020-07-28

共1个答案

小编典典

基本上,天真的乘法是常数因子非常低的O(n)。取幂是具有较高常数因子的O(log
n)(在某些特殊情况下需要测试…分数指数,负指数等)。编辑:只是要清楚,这是O(n)其中n是指数。

当然,对于小n,天真方法会更快,您实际上只是实现了一小部分指数数学,因此您的常数因子可以忽略不计。

2020-07-28