Filtrado de comprensión de lista - "la trampa set ()"
Una operación bastante común es filtrar unalist
basado en otrolist
. La gente rápidamente encuentra que esto:
[x for x in list_1 if x in list_2]
es lento para entradas grandes - es O (n * m). Puaj ¿Cómo aceleramos esto? Utilizar unaset
Para realizar búsquedas de filtrado O (1):
s = set(list_2)
[x for x in list_1 if x in s]
Esto da buen comportamiento general O (n). Sin embargo, a menudo veo incluso codificadores veteranos caer enLa trampa™:
[x for x in list_1 if x in set(list_2)]
Ack! Esto es de nuevo O (n * m) desde que se compila Pythonset(list_2)
cada Tiempo, no solo una vez.
Pensé que ese era el final de la historia: Python no puede optimizarlo para construir solo elset
una vez. Solo se consciente de la trampa. Tengo que vivir con eso. Hmm
#python 3.3.2+
list_2 = list(range(20)) #small for demonstration purposes
s = set(list_2)
list_1 = list(range(100000))
def f():
return [x for x in list_1 if x in s]
def g():
return [x for x in list_1 if x in set(list_2)]
def h():
return [x for x in list_1 if x in {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19}]
%timeit f()
100 loops, best of 3: 7.31 ms per loop
%timeit g()
10 loops, best of 3: 77.4 ms per loop
%timeit h()
100 loops, best of 3: 6.66 ms per loop
Huh, python (3.3)puede optimizar un conjunto literal. Es incluso más rápido quef()
en este caso, presumiblemente porque llega a reemplazar unLOAD_GLOBAL
con unLOAD_FAST
.
#python 2.7.5+
%timeit h()
10 loops, best of 3: 72.5 ms per loop
Python 2 notablemente no hace esta optimización. He intentado investigar más a fondo qué está haciendo python3 pero desafortunadamentedis.dis
No puede sondear las entrañas de las expresiones de comprensión. Básicamente todo lo interesante se convierte en.MAKE_FUNCTION
.
Así que ahora me pregunto: ¿por qué python 3.x optimiza el literal establecido para que se compile solo una vez, pero noset(list_2)
?