计算幂的速度(在python中) [英] Speed of calculating powers (in python)

问题描述

我很好奇为什么在 python 中乘法比取幂快得多(尽管从我读到的内容来看，这在许多其他语言中也可能是正确的).例如做起来要快得多

I'm curious as to why it's so much faster to multiply than to take powers in python (though from what I've read this may well be true in many other languages too). For example it's much faster to do

x*x

比

x**2

我认为 ** 运算符更通用，也可以处理分数幂.但是，如果这就是它慢得多的原因，为什么它不检查 int 指数然后只进行乘法运算?

I suppose the ** operator is more general and can also deal with fractional powers. But if that's why it's so much slower, why doesn't it perform a check for an int exponent and then just do the multiplication?

这是我尝试过的一些示例代码...

Here's some example code I tried...

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 需要约 2500 毫秒，而 pow2 需要约 1700 毫秒.
我承认对于较大的 n 值，pow1 确实比 pow2 快得多.但这并不奇怪.

Now, pow2 is just a quick example and is clearly not optimised!
But even so I find that using n = 2 and r = 1,000,000, then pow1 takes ~ 2500ms and pow2 takes ~ 1700ms.
I admit that for large values of n, then pow1 does get much quicker than pow2. But that's not too surprising.

推荐答案

基本上简单的乘法是 O(n) 和非常低的常数因子.取幂为 O(log n) ，具有更高的常数因子(有一些特殊情况需要测试...分数指数、负指数等).为了清楚起见，这是 O(n)，其中 n 是指数.

Basically naive multiplication is O(n) with a very low constant factor. Taking the power is O(log n) with a higher constant factor (There are special cases that need to be tested... fractional exponents, negative exponents, etc) . just to be clear, that's O(n) where n is the exponent.

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

Of course the naive approach will be faster for small n, you're only really implementing a small subset of exponential math so your constant factor is negligible.

这篇关于计算幂的速度(在python中)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！