Velocidad de cálculo de poderes (en python)

Question

Tengo curiosidad de por qué es mucho más rápido multiplicar que tomar poderes en python (aunque por lo que he leído esto bien puede ser cierto en muchos otros idiomas también). Por ejemplo, es mucho más rápido que hacer

x*x 

que

x**2 

supongo que el operador ** es más general y también puede hacer frente a potencias fraccionarias. Pero si es por eso que es mucho más lento, ¿por qué no realiza una comprobación de un exponente int y luego simplemente realiza la multiplicación?

Editar: Aquí hay un código de ejemplo he intentado ...

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 

Ahora, pow2 es sólo un ejemplo rápido y claramente no está optimizado!
Pero aun así me parece que usando n = 2 yr = 1,000,000, entonces pow1 toma ~ 2500ms y pow2 toma ~ 1700ms.
Admito que para valores grandes de n, entonces pow1 se vuelve mucho más rápido que pow2. Pero eso no es demasiado sorprendente.

Answer 1

La multiplicación básicamente ingenua es O (n) con un factor constante muy bajo. Tomando el poder es O (log n) con un factor constante más alto (Hay casos especiales que necesitan ser probados ... exponentes fraccionarios, exponentes negativos, etc.). Editar: solo para ser claro, eso es O (n) donde n es el exponente.

Por supuesto, el enfoque ingenuo será más rápido para la n pequeña, en realidad solo está implementando un pequeño subconjunto de matemática exponencial por lo que su factor constante es insignificante.

Answer 2

¿qué tal x x x x x? ¿es aún más rápido que x ** 5?

como int exponentes se hace más grande, tomando poderes podría ser más rápido que la multiplicación. pero el número en el que se produce el cruce real depende de varias condiciones, por lo que en mi opinión, es por eso que la optimización no se realizó (o no se pudo hacer) en el nivel de idioma/biblioteca. Pero los usuarios todavía pueden optimizar para algunos casos especiales :)

Answer 3

Agregar un cheque es un gasto, también. ¿Siempre quieres ese control allí? Un lenguaje compilado podría hacer que la comprobación de un exponente constante para ver si es un número entero relativamente pequeño porque no hay costo en tiempo de ejecución, solo un costo en tiempo de compilación. Un lenguaje interpretado podría no hacer ese control.

Depende de la implementación en particular a menos que ese tipo de detalle esté especificado por el idioma.

Python no sabe qué distribución de exponentes va a alimentar. Si va a ser un 99% de valores no enteros, ¿quiere que el código compruebe un entero cada vez, haciendo que el tiempo de ejecución sea incluso más lento?

Answer 4

Sospecho que nadie esperaba que esto fuera tan importante. Por lo general, si desea hacer cálculos serios, hágalos en Fortran o C o C++ o algo así (y quizás los llame desde Python).

Tratar todo como exp (n * log (x)) funciona bien en casos donde n no es integral o es bastante grande, pero es relativamente ineficiente para enteros pequeños. Verificar si n es un número entero lo suficientemente pequeño lleva tiempo y agrega complicaciones.

Si el cheque vale la pena depende de los exponentes esperados, de lo importante que es obtener el mejor rendimiento aquí, y el costo de la complejidad adicional. Aparentemente, Guido y el resto de la pandilla de Python decidieron que el cheque no valía la pena.

Si lo desea, puede escribir su propia función de multiplicación repetida.

Answer 5

Hacer esto en la comprobación del exponente ralentizará los casos en los que no es una potencia simple de dos muy poco, por lo que no es necesariamente una ganancia. Sin embargo, en los casos en que el exponente se conoce de antemano (por ejemplo, se utiliza el literal 2), el bytecode generado podría optimizarse con una simple optimización de mirilla. Es de suponer que simplemente no se ha considerado que valga la pena hacerlo (es un caso bastante específico).

Aquí hay una prueba rápida de concepto que hace tal optimización (utilizable como decorador). Nota: necesitará el módulo byteplay para ejecutarlo.

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) 

que da a los tiempos:

Unoptimised : 6.42024898529 
Optimised : 4.52667593956 

[Editar] En realidad, pensar en ello un poco más, hay una muy buena razón para que esto no se hace optimisaton. No hay garantía de que alguien no cree una clase definida por el usuario que anule los métodos __mul__ y __pow__ y haga algo diferente para cada uno. La única manera de hacerlo de manera segura es si puede garantizar que el objeto en la parte superior de la pila tenga el mismo resultado "x **2" y "x*x", pero eso es mucho más difícil. P.ej. en mi ejemplo es imposible, ya que cualquier objeto podría pasarse a la función cuadrada.

Answer 6

Una aplicación de b^p con exponenciación binaria

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