Python: ¿qué tan rápido?

Question

El período de Mersenne Twister utilizado en el módulo random es (me dicen) 2 ** 19937 - 1. Como un número binario, eso es 19937 '1 en una fila (si no me equivoco). Python lo convierte en decimal muy rápido:

$ python -m timeit '2**19937' 
10000000 loops, best of 3: 0.0271 usec per loop 

$ python -m timeit -s 'result = 0' 'result += 2**19937' 
100000 loops, best of 3: 2.09 usec per loop 

Supongo que la segunda versión es la que requiere conversión?

Y no es solo binario. Esto también es rápido. (En lugar de mostrar los números, se muestra la longitud del punto decimal convierte en una cadena):

>>> import math 
>>> N = 1000 
>>> s = str((int(N*math.e))**(int(N*math.pi))) 
>>> len(s) 
10787 
>>> N = 5000 
>>> s = str((int(N*math.e))**(int(N*math.pi))) 
>>> len(s) 
64921 

Tiempo:

python -m timeit -s 'import math' -s 'N=1000' 's = str((int(N*math.e))**(int(N*math.pi)))' 
10 loops, best of 3: 51.2 msec per loop 

La pregunta es: ¿cómo es esto en realidad hecho?

¿Soy ingenuo para quedar impresionado? Encuentro que la visión de la cáscara de Python genera aproximadamente 5000 lugares en un instante realmente espectacular.

Editar:

tiempos adicionales sugeridas por @dalke y @truppo

$ python -m timeit 'x=2' 'x**19937' 
1000 loops, best of 3: 230 usec per loop 
$ python -m timeit 'x=2' 'int(x**19937)' 
1000 loops, best of 3: 232 usec per loop 
$ python -m timeit 'x=2' 'str(x**19937)' 
100 loops, best of 3: 16.6 msec per loop 

$ python -m timeit -s 'result = 0' 'x = 2' 'result += x**19937' 
1000 loops, best of 3: 237 usec per loop 
$ python -m timeit -s 'result = 0' 'x = 2' 'result += x**19937' 'int(result)' 
1000 loops, best of 3: 238 usec per loop 
$ python -m timeit -s 'result = 0' 'x = 2' 'result += x**19937' 'str(result)' 
100 loops, best of 3: 16.6 msec per loop 

por lo que parece a mí como result = 0; result += 2**19937 probablemente hace forzar la conversión.

Answer 1

Python lo convierte en decimal bastante rápido.

No conozco Python, pero no, no tiene que hacer eso. 2^19937 no necesitan cálculos, es simplemente un cambio binario ("< <") con 19937, por lo que es muy rápido. Solo si imprime en decimal, la conversión real es necesaria y eso es mucho más lento.

EDITAR: La exponenciación puede ser lo mismo que desplazar (= mover el punto) si la base del número es idéntica a la base del exponente.

10^-1 = 0.1 10^0 = 1
10^1 = 10
10^2 = 100
10^3 = 1000
10^n = 1 (n ceros)

ves que la exponenciación de 10 con el exponente n simplemente cambia el número. Ahora las computadoras usan principalmente la base interna 2 (bits), por lo que calcular 2^19937 es establecer un bit en la posición 19937 (contando las posiciones de los bits desde cero).
Como información adicional: La conversión a decimal normalmente se implementa mediante un algoritmo de conquistar-dividir que divide sucesivamente el número por potencias de diez. Como ve, la conversión real es más lenta en un factor de medio millón.

El segundo ejemplo es más interesante: como está calculando m^n con enteros grandes m, n la forma más rápida es multiplicarla en sucesión y almacenar los resultados temporales.

Ejemplo: 10^345

a = 10^2
b = a a = 10^4
c = b b = 10^16
d = c * c = 10^256

resultado = d c c c c c c c c b b * 10

(se puede optimizar aún más: ver Knuth, Seminumerical Algoritmos)

lo que sólo necesita multiplicaciones largas y que se puede calcular bastante eficacia.

EDITAR: La implementación exacta de la multiplicación depende: Además de la multiplicación escolar normal, la multiplicación de Karatsuba, Tom-Cooke y Schoenhagen-Strasse (FFT) es utilizada.

Answer 2

Odio llover en su desfile, pero la razón por la que es tan rápido es porque el módulo matemático en realidad no está implementado en Python.

Python admite cargar bibliotecas compartidas que exportan API de Python, pero se implementan en otros idiomas. math.so, que proporciona el módulo que obtienes de import math, pasa a ser uno de esos (y también lo es _random.so).

Answer 3

que saben poco o nada acerca de cómo esto es en realidad implementados en Python, pero teniendo en cuenta que esta es básicamente la multiplicación primitivo y logaritmos, no estoy terriblemente sorprendido de que es razonablemente rápido incluso en muy grandes cantidades.

Existen bibliotecas matemáticas de precisión arbitraria como GMP que implementan una amplia variedad de operaciones de una manera muy efectiva, optimizadas en el ensamblaje, solo para este propósito.

Answer 4

Al compilar a código de bytes, expresiones constantes como 2**19937 será optimizada a una sola constante:

>>> def foo(): return 2**10 
... 
>>> import dis 
>>> dis.dis(foo) 
    1   0 LOAD_CONST    3 (1024) 
       3 RETURN_VALUE   
>>> 

considerar en cambio:

[~] python -m timeit 'x=2' 'x**19937' 
1000 loops, best of 3: 210 usec per loop