python - ¿Por qué este bucle es más rápido que la comprensión de un diccionario para crear un diccionario?

python-3.x performance

Question

No provengo de una formación en informática / informática, pero me encanta codificar en Python y generalmente puedo entender por qué las cosas son más rápidas. Tengo mucha curiosidad por saber por qué este bucle for se ejecuta más rápido que la comprensión del diccionario. ¿Alguna idea?

Problema: Dado un diccionario con estas claves y valores, devuelva un diccionario con los valores como claves y las claves como valores. (desafío: haz esto en una línea)

y el código

a = {''a'':''hi'',''b'':''hey'',''c'':''yo''}
b = {}
for i,j in a.items():
b[j]=i
%% timeit 932 ns ± 37.2 ns per loop
b = {v: k for k, v in a.items()}
%% timeit 1.08 µs ± 16.4 ns per loop

Answer 1

Estás probando con una entrada demasiado pequeña; mientras que la comprensión de un diccionario no tiene tanta ventaja de rendimiento en comparación con un bucle for en comparación con una comprensión de lista, para los problemas de tamaño realistas puede latir for bucles, especialmente cuando se trata de un nombre global.

Su entrada consiste en solo 3 pares clave-valor. Al probar con 1000 elementos, vemos que los tiempos son muy cercanos en su lugar:

>>> import timeit
>>> from random import choice, randint; from string import ascii_lowercase as letters
>>> looped = ''''''/
... b = {}
... for i,j in a.items():
... b[j]=i
... ''''''
>>> dictcomp = ''''''b = {v: k for k, v in a.items()}''''''
>>> def rs(): return ''''.join([choice(letters) for _ in range(randint(3, 15))])
...
>>> a = {rs(): rs() for _ in range(1000)}
>>> len(a)
1000
>>> count, total = timeit.Timer(looped, ''from __main__ import a'').autorange()
>>> (total / count) * 1000000 # microseconds per run
66.62004760000855
>>> count, total = timeit.Timer(dictcomp, ''from __main__ import a'').autorange()
>>> (total / count) * 1000000 # microseconds per run
64.5464928005822

La diferencia está ahí, el comp dict es más rápido pero solo a esta escala. Con 100 veces más pares clave-valor, la diferencia es un poco más grande:

>>> a = {rs(): rs() for _ in range(100000)}
>>> len(a)
98476
>>> count, total = timeit.Timer(looped, ''from __main__ import a'').autorange()
>>> total / count * 1000 # milliseconds, different scale!
15.48140200029593
>>> count, total = timeit.Timer(dictcomp, ''from __main__ import a'').autorange()
>>> total / count * 1000 # milliseconds, different scale!
13.674790799996117

lo que no es una gran diferencia cuando se considera que ambos procesaron casi 100k pares clave-valor. Aún así, el bucle for es claramente más lento .

Entonces, ¿por qué la diferencia de velocidad con 3 elementos? Debido a que una comprensión (diccionario, conjunto, comprensión de listas o una expresión generadora) se implementa como una nueva función , y el hecho de llamar a esa función tiene un costo base que el ciclo simple no tiene que pagar.

Aquí está el desmontaje del código de bytes para ambas alternativas; tenga en cuenta los MAKE_FUNCTION CALL_FUNCTION MAKE_FUNCTION y CALL_FUNCTION en el bytecode de nivel superior para la comprensión del dict, hay una sección separada para lo que luego hace esa función, y en realidad hay muy pocas diferencias entre los dos enfoques aquí:

>>> import dis
>>> dis.dis(looped)
1 0 BUILD_MAP 0
2 STORE_NAME 0 (b)
2 4 SETUP_LOOP 28 (to 34)
6 LOAD_NAME 1 (a)
8 LOAD_METHOD 2 (items)
10 CALL_METHOD 0
12 GET_ITER
>> 14 FOR_ITER 16 (to 32)
16 UNPACK_SEQUENCE 2
18 STORE_NAME 3 (i)
20 STORE_NAME 4 (j)
3 22 LOAD_NAME 3 (i)
24 LOAD_NAME 0 (b)
26 LOAD_NAME 4 (j)
28 STORE_SUBSCR
30 JUMP_ABSOLUTE 14
>> 32 POP_BLOCK
>> 34 LOAD_CONST 0 (None)
36 RETURN_VALUE
>>> dis.dis(dictcomp)
1 0 LOAD_CONST 0 (<code object <dictcomp> at 0x11d6ade40, file "<dis>", line 1>)
2 LOAD_CONST 1 (''<dictcomp>'')
4 MAKE_FUNCTION 0
6 LOAD_NAME 0 (a)
8 LOAD_METHOD 1 (items)
10 CALL_METHOD 0
12 GET_ITER
14 CALL_FUNCTION 1
16 STORE_NAME 2 (b)
18 LOAD_CONST 2 (None)
20 RETURN_VALUE
Disassembly of <code object <dictcomp> at 0x11d6ade40, file "<dis>", line 1>:
1 0 BUILD_MAP 0
2 LOAD_FAST 0 (.0)
>> 4 FOR_ITER 14 (to 20)
6 UNPACK_SEQUENCE 2
8 STORE_FAST 1 (k)
10 STORE_FAST 2 (v)
12 LOAD_FAST 1 (k)
14 LOAD_FAST 2 (v)
16 MAP_ADD 2
18 JUMP_ABSOLUTE 4
>> 20 RETURN_VALUE

Las diferencias de material: el código en bucle utiliza LOAD_NAME para b cada iteración, y STORE_SUBSCR para almacenar el par clave-valor en dict cargado. La comprensión del diccionario utiliza MAP_ADD para lograr lo mismo que STORE_SUBSCR pero no tiene que cargar ese nombre b cada vez.

Pero con solo 3 iteraciones , el combo MAKE_FUNCTION / CALL_FUNCTION tiene que ejecutar la comprensión de dict es el verdadero arrastre en el rendimiento:

>>> make_and_call = ''(lambda i: None)(None)''
>>> dis.dis(make_and_call)
1 0 LOAD_CONST 0 (<code object <lambda> at 0x11d6ab270, file "<dis>", line 1>)
2 LOAD_CONST 1 (''<lambda>'')
4 MAKE_FUNCTION 0
6 LOAD_CONST 2 (None)
8 CALL_FUNCTION 1
10 RETURN_VALUE
Disassembly of <code object <lambda> at 0x11d6ab270, file "<dis>", line 1>:
1 0 LOAD_CONST 0 (None)
2 RETURN_VALUE
>>> count, total = timeit.Timer(make_and_call).autorange()
>>> total / count * 1000000
0.12945385499915574

Más de 0.1 μs para crear un objeto de función con un argumento y llamarlo (con un LOAD_CONST adicional para el valor None que pasamos). Y eso es solo la diferencia entre los tiempos en bucle y de comprensión para 3 pares clave-valor.

Puedes comparar esto con la sorpresa de que un hombre con una pala puede cavar un pequeño agujero más rápido que una retroexcavadora. La retroexcavadora ciertamente puede cavar rápido, ¡pero un hombre con una pala puede comenzar más rápido si usted necesita que la retroexcavadora se ponga en marcha y se coloque primero!

Más allá de unos pocos pares clave-valor (cavando un agujero más grande), la función crear y el costo de llamadas se desvanece en la nada. En este punto, la comprensión del dict y el bucle explícito básicamente hacen lo mismo:

• toma el siguiente par clave-valor, saca los de la pila
• llame al dict.__setitem__ hook mediante una operación de bytecode con los dos elementos principales en la pila (ya sea STORE_SUBSCR o MAP_ADD . Esto no cuenta como una ''llamada de función'', ya que todo se maneja internamente en el bucle del intérprete.

Esto es diferente de una comprensión de lista, donde la versión de bucle plano tendría que usar list.append() , que involucra una búsqueda de atributos, y una función llama a cada iteración de bucle . La ventaja de la velocidad de comprensión de lista viene de esta diferencia; Ver lista de comprensión de Python caro

Lo que agrega un dictado de dictado es que el nombre del diccionario de destino solo debe buscarse una vez, al vincular b con el objeto del diccionario final. Si el diccionario de destino es una variable global en lugar de una variable local, la comprensión gana, incuestionablemente:

>>> a = {rs(): rs() for _ in range(1000)}
>>> len(a)
1000
>>> namespace = {}
>>> count, total = timeit.Timer(looped, ''from __main__ import a; global b'', globals=namespace).autorange()
>>> (total / count) * 1000000
76.72348440100905
>>> count, total = timeit.Timer(dictcomp, ''from __main__ import a; global b'', globals=namespace).autorange()
>>> (total / count) * 1000000
64.72114819916897
>>> len(namespace[''b''])
1000

Así que solo usa un dict de comprensión. La diferencia con <30 elementos a procesar es demasiado pequeña para preocuparse, y en el momento en que genera un elemento global o tiene más elementos, la comprensión del dictado de todos modos gana.

Answer 2

Esta pregunta, en algunos sentidos, es bastante similar a ¿Por qué es una comprensión de lista mucho más rápida que agregarla a una lista? que he respondido hace mucho tiempo. Sin embargo, la razón por la que este comportamiento le sorprende es, obviamente, porque su diccionario es demasiado pequeño para superar el costo de crear un nuevo marco de función y empujarlo / jalarlo en la pila. Para entender que mejor vamos debajo de la piel de los fragmentos de remolque que tiene:

In [1]: a = {''a'':''hi'',''b'':''hey'',''c'':''yo''}
...:
...: def reg_loop(a):
...: b = {}
...: for i,j in a.items():
...: b[j]=i
...:
In [2]: def dict_comp(a):
...: b = {v: k for k, v in a.items()}
...:
In [3]:
In [3]: %timeit reg_loop(a)
529 ns ± 7.89 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
In [4]:
In [4]: %timeit dict_comp(a)
656 ns ± 5.39 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
In [5]:
In [5]: import dis
In [6]: dis.dis(reg_loop)
4 0 BUILD_MAP 0
2 STORE_FAST 1 (b)
5 4 SETUP_LOOP 28 (to 34)
6 LOAD_FAST 0 (a)
8 LOAD_METHOD 0 (items)
10 CALL_METHOD 0
12 GET_ITER
>> 14 FOR_ITER 16 (to 32)
16 UNPACK_SEQUENCE 2
18 STORE_FAST 2 (i)
20 STORE_FAST 3 (j)
6 22 LOAD_FAST 2 (i)
24 LOAD_FAST 1 (b)
26 LOAD_FAST 3 (j)
28 STORE_SUBSCR
30 JUMP_ABSOLUTE 14
>> 32 POP_BLOCK
>> 34 LOAD_CONST 0 (None)
36 RETURN_VALUE
In [7]:
In [7]: dis.dis(dict_comp)
2 0 LOAD_CONST 1 (<code object <dictcomp> at 0x7fbada1adf60, file "<ipython-input-2-aac022159794>", line 2>)
2 LOAD_CONST 2 (''dict_comp.<locals>.<dictcomp>'')
4 MAKE_FUNCTION 0
6 LOAD_FAST 0 (a)
8 LOAD_METHOD 0 (items)
10 CALL_METHOD 0
12 GET_ITER
14 CALL_FUNCTION 1
16 STORE_FAST 1 (b)
18 LOAD_CONST 0 (None)
20 RETURN_VALUE

En el segundo código desensamblado (comprensión de MAKE_FUNCTION ) tiene un MAKE_FUNCTION operación MAKE_FUNCTION que, como también se indica en la documentación, empuja un nuevo objeto de función en la pila. y luego CALL_FUNCTION que llama a un objeto que se puede CALL_FUNCTION con argumentos posicionales. y entonces:

saca de la pila todos los argumentos y el objeto que se puede llamar, llama al objeto que se puede llamar con esos argumentos y empuja el valor de retorno devuelto por el objeto que se puede llamar.

Todas estas operaciones tienen sus costos, pero cuando el diccionario se haga más grande, el costo de asignar los elementos clave-valor al diccionario será más grande que crear una función bajo el capó. En otras palabras, el costo de llamar al método __setitem__ del diccionario desde un cierto punto excederá el costo de crear y suspender un objeto de diccionario sobre la marcha.

Además, tenga en cuenta que ciertamente hay muchas otras operaciones (OP_CODES en este caso) que desempeñan un papel crucial en este juego que creo que vale la pena investigar y considerando cuál lo viviré como una práctica;