accelerate - python timing code

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 podría ser cierto en muchos otros idiomas también). 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 comprobación de un exponente int y luego simplemente realiza 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 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

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

a medida que los exponentes int se hacen más grandes, tomar poderes podría ser más rápido que la multiplicación. pero el número en el que se produce el cruce efectivo depende de varias condiciones, por lo que en mi opinión, esa es la razón por la cual la optimización no se realizó (o no se pudo hacer) en el nivel de idioma / biblioteca. Pero los usuarios aún pueden optimizar para algunos casos especiales :)

Answer 2

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 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 3

Hacer esto en la comprobación del exponente ralentizará los casos en los que no es una potencia simple de dos muy levemente, por lo que no es necesariamente una victoria. 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á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 cual da los tiempos:

Unoptimised : 6.42024898529
Optimised   : 4.52667593956

[Editar] En realidad, al pensarlo un poco más, hay una muy buena razón por la cual esta optimización no está hecha. 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 puedes garantizar que el objeto en la parte superior de la pila tenga el mismo resultado "x **2 " y " x*x ", pero solucionarlo 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 4

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 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 5

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 la importancia de obtener el mejor rendimiento aquí y del 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 6

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