python - color - plotly title
¿Por qué es 2*x*x más rápido que 2*(x*x) en Python 3.x, para enteros? (4)
La siguiente multiplicación de enteros de Python 3.x toma en promedio entre 1.66s y 1.77s:
import time
start_time = time.time()
num = 0
for x in range(0, 10000000):
# num += 2 * (x * x)
num += 2 * x * x
print("--- %s seconds ---" % (time.time() - start_time))
si sustituyo 2 * x * x por 2 *(x * x) , se tarda entre 2.04 y 2.25 . ¿Cómo?
Por otro lado, es lo contrario en Java: 2 * (x * x) es más rápido en Java. Enlace de prueba de Java: ¿Por qué es 2 * (i * i) más rápido que 2 * i * i en Java?
Ejecuté cada versión del programa 10 veces, aquí están los resultados.
2 * x * x | 2 * (x * x)
---------------------------------------
1.7717654705047607 | 2.0789272785186768
1.735931396484375 | 2.1166207790374756
1.7093875408172607 | 2.024367570877075
1.7004504203796387 | 2.047525405883789
1.6676218509674072 | 2.254328966140747
1.699510097503662 | 2.0949244499206543
1.6889283657073975 | 2.0841963291168213
1.7243537902832031 | 2.1290600299835205
1.712965488433838 | 2.1942825317382812
1.7622807025909424 | 2.1200053691864014
En primer lugar, tenga en cuenta que no vemos lo mismo en Python 2.x:
>>> timeit("for i in range(1000): 2*i*i")
51.00784397125244
>>> timeit("for i in range(1000): 2*(i*i)")
50.48330092430115
Así que esto nos lleva a creer que esto se debe a cómo los enteros cambiaron en Python 3: específicamente, Python 3 usa long (enteros arbitrariamente grandes) en todas partes.
Para los enteros lo suficientemente pequeños (incluidos los que estamos considerando aquí), CPython en realidad solo usa el algoritmo de multiplicación dígito a dígito de la escuela de grado O (MN) (para enteros más grandes cambia al algoritmo de Karatsuba ). Puedes ver esto tú mismo en la source .
El número de dígitos en x*x es aproximadamente el doble que 2*x x (ya que log (x 2 ) = 2 log (x)). Tenga en cuenta que un "dígito" en este contexto no es un dígito de base 10, sino un valor de 30 bits (que se tratan como dígitos únicos en la implementación de CPython). Por lo tanto, 2 es un valor de un solo dígito, y x y 2*x son valores de un solo dígito para todas las iteraciones del bucle, pero x*x es de dos dígitos para x >= 2**15 . Por lo tanto, para x >= 2**15 , 2*x*x solo requiere multiplicaciones de un solo dígito, mientras que 2*(x*x) requiere una única por una y una simple por dos dígitos multiplicación (ya que x*x tiene 2 dígitos de 30 bits).
Aquí hay una forma directa de ver esto (Python 3):
>>> timeit("a*b", "a,b = 2, 123456**2", number=100000000)
5.796971936999967
>>> timeit("a*b", "a,b = 2*123456, 123456", number=100000000)
4.3559221399999615
Nuevamente, compare esto con Python 2, que no usa enteros de longitud arbitraria en todas partes:
>>> timeit("a*b", "a,b = 2, 123456**2", number=100000000)
3.0912468433380127
>>> timeit("a*b", "a,b = 2*123456, 123456", number=100000000)
3.1120400428771973
(Una nota interesante: si miras la fuente, verás que el algoritmo en realidad tiene un caso especial para cuadrar números (lo que estamos haciendo aquí), pero aún así esto no es suficiente para superar el hecho de que 2*(x*x) solo requiere procesar más dígitos.)
La representación interna de enteros de Python es especial, utiliza ranuras de 30 bits:
In [6]: sys.getsizeof(2**30-1)
Out[6]: 28 # one slot + heading
In [7]: sys.getsizeof(2**30)
Out[7]: 32 # two slots
Entonces todo sucede como si Python contara en la base B = 2**30 = 1 073 741 824 ~1 billion .
Para un humano que quiere calcular 2 * 4 * 4, de dos maneras:
- (2 * 4) * 4 = 8 * 4 = 32 = 30 + 2 es inmediato si conoce sus tablas adicionales.
- 2 * (4 * 4) = 2 * 16 = 2 * 10 + 2 * 6 = (2 * 10 + 10) + 2 = 30 + 2 ya que tenemos que cancelar la operación.
Python tiene el mismo problema. Si x es un número tal que 2x < B < x² , sea x² = aB+b , con a,b <B . x² se almacena en 2 ranuras, que observo (a|b) . Los cálculos conducen a (sin la gestión lleva aquí):
(x*x)*2 => (a|b)*2 => (2*a|2*b)
(2*x)*x => (2x)*x =>(2a|2b)
en el primer caso, la operación 2* se realiza dos veces, contra solo una en el primer caso. Eso explica la diferencia.
Por lo que puedo decir, se reduce a un poco más de acceso a la memoria en la versión usando 2 * (x * x) . Imprimí el bytecode desmontado y parece probar que:
Parte relevante de 2 * x * x :
7 28 LOAD_FAST 1 (num)
30 LOAD_CONST 3 (2)
32 LOAD_FAST 2 (x)
34 BINARY_MULTIPLY
36 LOAD_FAST 2 (x)
38 BINARY_MULTIPLY
40 INPLACE_ADD
42 STORE_FAST 1 (num)
44 JUMP_ABSOLUTE 24
Parte relevante de 2 * (x * x) :
7 28 LOAD_FAST 1 (num)
30 LOAD_CONST 3 (2)
32 LOAD_FAST 2 (x)
34 LOAD_FAST 2 (x)
36 BINARY_MULTIPLY <=== 1st multiply x*x in a temp value
38 BINARY_MULTIPLY <=== then multiply result with 2
40 INPLACE_ADD
42 STORE_FAST 1 (num)
44 JUMP_ABSOLUTE 24
Si su punto de referencia es correcto (no se verificó), puede deberse al hecho de que los enteros de Python pueden ser dos cosas diferentes: enteros nativos cuando son pequeños (con un cálculo rápido) y enteros grandes cuando aumentan de tamaño (más lento cálculo). La primera sintaxis mantiene el tamaño más pequeño después de la primera operación, mientras que la segunda sintaxis puede llevar a dos operaciones con enteros grandes.