Velocidad de los poderes de cálculo (en python)

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

x*x 

que

 x**2 

Supongo que el operador ** es más general y también puede tratar con poderes fraccionarios. Pero si es por eso que es mucho más lento, ¿por qué no realiza una verificación de un exponente int y luego simplemente hace la multiplicación?

Editar: Aquí hay un código de ejemplo que probé …

 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 solo un ejemplo rápido y claramente no está optimizado!
Pero aun así, encuentro que utilizando n = 2 y r = 1,000,000, 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.

Básicamente, la multiplicación ingenua es O (n) con un factor constante muy bajo. Tomar el poder es O (log n) con un factor constante más alto (hay casos especiales que deben probarse … exponentes fraccionarios, exponentes negativos, etc.). Edición: solo para ser claros, eso es O (n) donde n es el exponente.

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

Agregar un cheque también es un gasto. ¿Siempre quieres ese cheque allí? Un lenguaje comstackdo podría hacer la verificació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 comstackción. Un lenguaje interpretado podría no hacer esa comprobación.

Depende de la implementación particular a menos que el lenguaje especifique ese tipo de detalle.

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

Hacer esto en la comprobación de exponentes ralentizará los casos en los que no es una simple potencia de dos muy ligeramente, por lo que no es necesariamente una victoria. Sin embargo, en los casos en que el exponente se conoce de antemano (por ejemplo, se usa el literal 2), el código de bytes generado podría optimizarse con una simple optimización de mirilla. Es de suponer que esto simplemente no se ha considerado valioso (es un caso bastante específico).

Aquí hay una rápida prueba de concepto que hace tal optimización (utilizable como decorador). Nota: necesitarás 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) 

Lo que da los tiempos:

 Unoptimised : 6.42024898529 Optimised : 4.52667593956 

[Editar] En realidad, pensándolo un poco más, hay una muy buena razón por la que no se realiza esta optimización. No hay garantía de que alguien no cree una clase definida por el usuario que __pow__ métodos __mul__ y __pow__ y haga algo diferente para cada uno. La única forma de hacerlo de manera segura es si puede garantizar que el objeto en la parte superior de la stack sea uno que tenga el mismo resultado “x **2 ” y ” x*x “, pero resolverlo 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.

Una implementació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 

Sospecho que nadie esperaba que esto fuera tan importante. Normalmente, si quieres hacer cálculos serios, los haces en Fortran o C o C ++ o algo así (y quizás los llames desde Python).

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

Si la verificación vale la pena, depende de los exponentes esperados, cuán importante es obtener el mejor rendimiento aquí y el costo de la complejidad adicional. Aparentemente, Guido y el rest 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.

¿qué tal x x x x x? ¿Sigue siendo más rápido que x ** 5?

a medida que los exponentes int se hacen más grandes, tomar poderes puede 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 🙂