计算能力的速度（在python中）

问题描述：

我很好奇它为什么它乘法的速度比在python中获取能力要快得多（尽管从我读过的这个很可能在其他许多语言中也是如此）。例如它的速度更快做计算能力的速度（在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需要约2500毫秒，pow2需要约1700毫秒。
我承认，对于大的n值，pow1确实比pow2快得多。但这并不令人感到意外。

如果你改变你的循环由1/1000秒，而不是通过1S去，会发生什么？ – Nosredna 2009-06-19 20:42:11

是的，在这种情况下，**比我疯狂的循环更快！好吧，我想我只需要处理这样一个事实，即对于小型指数来说，乘法和不使用**会更快。 – Christwo 2009-06-19 21:13:21

我已经对此进行了博客（http://numericalrecipes.wordpress.com/2009/06/05/binary-exponentiation/），但通过平方搜索指数（http://en.wikipedia.org/wiki/ Exponentiation_by_squaring）也可以让您更好地了解如何有效计算整数指数的权力，以及为什么它们对于小指数（ Jaime 2009-06-19 23:32:47

答

基本上天真的乘法是一个非常低的常数因子O（n）。采取的权力是O（log n）具有较高的常数因子（有些特殊情况需要测试......分数指数，负指数等）。编辑：只需要清楚，那就是O（n），其中n是指数。

当然，对于小n来说，幼稚的方法会更快，你只是真的实现了指数数学的一个小子集，所以你的常数因子可以忽略不计。

答

x怎么样x x x x x？它比x ** 5还快吗？

随着int指数变大，采取权力可能会比乘法更快。但实际交叉发生的数量取决于各种条件，所以在我看来，这就是为什么在语言/库级别没有完成（或不能完成）优化的原因。但用户仍然可以针对一些特殊情况进行优化:)

答

添加支票也是一项开支。你总是希望那里的支票？编译语言可以检查一个常量指数，看它是否是一个相对较小的整数，因为没有运行时成本，只是编译时成本。解释型语言可能不会进行检查。

这取决于特定的实现，除非该语言指定了这种细节。

Python不知道你要给它分配什么指数。如果它将是99％的非整数值，你是否希望代码每次检查一个整数，使运行时更慢？

答

我怀疑没有人会期待这一切都是那么重要。通常情况下，如果你想做严肃的计算，你可以用Fortran或者C或者C++或者类似的东西来做（也许可以从Python中调用它们）。

在n不是整数或非常大的情况下，处理所有exp（n * log（x）），但对于小整数来说效率相对较低。检查n是否足够小会花费时间，并增加复杂性。

支票是否值得，取决于期望的指数，在这里获得最佳表现的重要性以及额外复杂性的成本。显然，Guido和Python团伙的其他成员决定检查不值得。

如果你喜欢，你可以编写自己的重复乘法函数。

答

在指数检查中这样做会减慢并非两个简单的两次幂的情况，所以不一定是赢。但是，在指数已知的情况下（例如使用文字2），可以通过简单的窥孔优化来优化生成的字节码。据推测，这根本不值得做（这是一个相当具体的案例）。

下面是做这样的优化（可用作装饰）的概念的快速证明。注意：您需要byteplay模块来运行它。

import byteplay, timeit 

def optimise(func): 
    c = byteplay.Code.from_code(func.func_code) 
    prev=None 
    for i, (op, arg) in enumerate(c.code): 
     if op == byteplay.BINARY_POWER: 
      if c.code[i-1] == (byteplay.LOAD_CONST, 2): 
       c.code[i-1] = (byteplay.DUP_TOP, None) 
       c.code[i] = (byteplay.BINARY_MULTIPLY, None) 
    func.func_code = c.to_code() 
    return func 

def square(x): 
    return x**2 

print "Unoptimised :", timeit.Timer('square(10)','from __main__ import square').timeit(10000000) 
square = optimise(square) 
print "Optimised :", timeit.Timer('square(10)','from __main__ import square').timeit(10000000)

这给计时：

Unoptimised : 6.42024898529 
Optimised : 4.52667593956

[编辑] 其实，想多一点，有一个很好的理由，为什么这optimisaton没有这样做。无法保证有人不会创建覆盖__mul__和__pow__方法的用户定义的类，并为每个方法执行不同的操作。要安全地做到这一点，唯一的方法是如果可以保证堆栈顶部的对象具有相同结果“x **2”和“x*x”，但是解决这个问题要困难得多。例如。在我的例子中是不可能的，因为任何对象都可以传递给平方函数。

答

b^P的执行二进制幂

def power(b, p): 
    """ 
    Calculates b^p 
    Complexity O(log p) 
    b -> double 
    p -> integer 
    res -> double 
    """ 
    res = 1 

    while p: 
     if p & 0x1: res *= b 
     b *= b 
     p >>= 1 

    return res

计算能力的速度（在python中）

相关推荐