python - tabla - taxonomia de bloom niveles

¿Enumera la comprensión frente a los resultados de tiempo extraños de la expresión del generador?

Question

Estaba respondiendo esta question , preferí la expresión del generador aquí y usé esto, que pensé que sería más rápido ya que el generador no necesita crear primero la lista completa:

>>> lis=[[''a'',''b'',''c''],[''d'',''e'',''f'']]
>>> ''d'' in (y for x in lis for y in x)
True

Y Levon utilizó la lista de comprensión en su solution ,

>>> lis = [[''a'',''b'',''c''],[''d'',''e'',''f'']]
>>> ''d'' in [j for i in mylist for j in i]
True

Pero cuando hice los resultados de tiempo para estos LC fue más rápido que el generador:

~$ python -m timeit -s "lis=[[''a'',''b'',''c''],[''d'',''e'',''f'']]" "''d'' in (y for x in lis for y in x)"
100000 loops, best of 3: 2.36 usec per loop
~$ python -m timeit -s "lis=[[''a'',''b'',''c''],[''d'',''e'',''f'']]" "''d'' in [y for x in lis for y in x]"
100000 loops, best of 3: 1.51 usec per loop

luego aumenté el tamaño de la lista y la sincronicé de nuevo:

lis=[[''a'',''b'',''c''],[''d'',''e'',''f''],[1,2,3],[4,5,6],[7,8,9],[10,11,12],[13,14,15],[16,17,18]]

Esta vez para buscar ''d'' generador ''d'' fue más rápido que LC, pero cuando busqué un elemento intermedio (11) y el último elemento, LC nuevamente supera la expresión del generador, y no puedo entender por qué?

~$ python -m timeit -s "lis=[[''a'',''b'',''c''],[''d'',''e'',''f''],[1,2,3],[4,5,6],[7,8,9],[10,11,12],[13,14,15],[16,17,18]]" "''d'' in (y for x in lis for y in x)"
100000 loops, best of 3: 2.96 usec per loop
~$ python -m timeit -s "lis=[[''a'',''b'',''c''],[''d'',''e'',''f''],[1,2,3],[4,5,6],[7,8,9],[10,11,12],[13,14,15],[16,17,18]]" "''d'' in [y for x in lis for y in x]"
100000 loops, best of 3: 7.4 usec per loop
~$ python -m timeit -s "lis=[[''a'',''b'',''c''],[''d'',''e'',''f''],[1,2,3],[4,5,6],[7,8,9],[10,11,12],[13,14,15],[16,17,18]]" "11 in [y for x in lis for y in x]"
100000 loops, best of 3: 5.61 usec per loop
~$ python -m timeit -s "lis=[[''a'',''b'',''c''],[''d'',''e'',''f''],[1,2,3],[4,5,6],[7,8,9],[10,11,12],[13,14,15],[16,17,18]]" "11 in (y for x in lis for y in x)"
100000 loops, best of 3: 9.76 usec per loop
~$ python -m timeit -s "lis=[[''a'',''b'',''c''],[''d'',''e'',''f''],[1,2,3],[4,5,6],[7,8,9],[10,11,12],[13,14,15],[16,17,18]]" "18 in (y for x in lis for y in x)"
100000 loops, best of 3: 8.94 usec per loop
~$ python -m timeit -s "lis=[[''a'',''b'',''c''],[''d'',''e'',''f''],[1,2,3],[4,5,6],[7,8,9],[10,11,12],[13,14,15],[16,17,18]]" "18 in [y for x in lis for y in x]"
100000 loops, best of 3: 7.13 usec per loop

Answer 1

Ampliando la respuesta de Paulo , las expresiones del generador son a menudo más lentas que las listas de comprensión debido a la sobrecarga de las llamadas a funciones. En este caso, el comportamiento de cortocircuito de las compensaciones que disminuyen si el artículo se encuentra bastante temprano, pero de lo contrario, el patrón se mantiene.

Ejecuté un script simple a través del generador de perfiles para un análisis más detallado. Aquí está el guión:

lis=[[''a'',''b'',''c''],[''d'',''e'',''f''],[1,2,3],[4,5,6],
[7,8,9],[10,11,12],[13,14,15],[16,17,18]]
def ge_d():
return ''d'' in (y for x in lis for y in x)
def lc_d():
return ''d'' in [y for x in lis for y in x]
def ge_11():
return 11 in (y for x in lis for y in x)
def lc_11():
return 11 in [y for x in lis for y in x]
def ge_18():
return 18 in (y for x in lis for y in x)
def lc_18():
return 18 in [y for x in lis for y in x]
for i in xrange(100000):
ge_d()
lc_d()
ge_11()
lc_11()
ge_18()
lc_18()

Aquí están los resultados relevantes, reordenados para hacer los patrones más claros.

 5400002 function calls in 2.830 seconds
Ordered by: standard name
ncalls tottime percall cumtime percall filename:lineno(function)
100000 0.158 0.000 0.251 0.000 fop.py:3(ge_d)
500000 0.092 0.000 0.092 0.000 fop.py:4(<genexpr>)
100000 0.285 0.000 0.285 0.000 fop.py:5(lc_d)
100000 0.356 0.000 0.634 0.000 fop.py:8(ge_11)
1800000 0.278 0.000 0.278 0.000 fop.py:9(<genexpr>)
100000 0.333 0.000 0.333 0.000 fop.py:10(lc_11)
100000 0.435 0.000 0.806 0.000 fop.py:13(ge_18)
2500000 0.371 0.000 0.371 0.000 fop.py:14(<genexpr>)
100000 0.344 0.000 0.344 0.000 fop.py:15(lc_18)

Crear una expresión de generador equivale a crear una función de generador y llamarla . Eso explica una llamada a <genexpr> . Luego, en el primer caso, el next se llama 4 veces, hasta que se alcanza d , para un total de 5 llamadas (multiplicado por 100000 iteraciones = ncalls = 500000). En el segundo caso, se llama 17 veces, para un total de 18 llamadas; y en el tercero, 24 veces, para un total de 25 llamadas.

El genex supera la comprensión de la lista en el primer caso, pero las llamadas extra a la next cuenta representan la mayor parte de la diferencia entre la velocidad de comprensión de la lista y la velocidad de la expresión del generador en el segundo y tercer casos.

>>> .634 - .278 - .333
0.023
>>> .806 - .371 - .344
0.091

No estoy seguro de lo que representa el tiempo restante; parece que las expresiones del generador serían un poco más lentas incluso sin las llamadas a funciones adicionales. Supongo que esto confirma la afirmación de inspectorG4dget que "crear una comprensión de generador tiene más sobrecarga nativa que una comprensión de lista". Pero en cualquier caso, esto muestra claramente que las expresiones del generador son más lentas principalmente por las llamadas a la next .

Añadiré que cuando los cortocircuitos no ayudan, las listas de comprensión son aún más rápidas, incluso para listas muy grandes. Por ejemplo:

>>> counter = itertools.count()
>>> lol = [[counter.next(), counter.next(), counter.next()]
for _ in range(1000000)]
>>> 2999999 in (i for sublist in lol for i in sublist)
True
>>> 3000000 in (i for sublist in lol for i in sublist)
False
>>> %timeit 2999999 in [i for sublist in lol for i in sublist]
1 loops, best of 3: 312 ms per loop
>>> %timeit 2999999 in (i for sublist in lol for i in sublist)
1 loops, best of 3: 351 ms per loop
>>> %timeit any([2999999 in sublist for sublist in lol])
10 loops, best of 3: 161 ms per loop
>>> %timeit any(2999999 in sublist for sublist in lol)
10 loops, best of 3: 163 ms per loop
>>> %timeit for i in [2999999 in sublist for sublist in lol]: pass
1 loops, best of 3: 171 ms per loop
>>> %timeit for i in (2999999 in sublist for sublist in lol): pass
1 loops, best of 3: 183 ms per loop

Como puede ver, cuando el cortocircuito es irrelevante, las listas de comprensión son consistentemente más rápidas incluso para una lista de listas de un millón de elementos. Obviamente para los usos reales de in a estas escalas, los generadores serán más rápidos debido a cortocircuitos. Pero para otros tipos de tareas iterativas que son verdaderamente lineales en la cantidad de elementos, las listas de comprensión son mucho más rápidas. Esto es especialmente cierto si necesita realizar múltiples pruebas en una lista; puede iterar sobre una lista de comprensión ya compilada muy rápidamente :

>>> incache = [2999999 in sublist for sublist in lol]
>>> get_list = lambda: incache
>>> get_gen = lambda: (2999999 in sublist for sublist in lol)
>>> %timeit for i in get_list(): pass
100 loops, best of 3: 18.6 ms per loop
>>> %timeit for i in get_gen(): pass
1 loops, best of 3: 187 ms per loop

En este caso, ¡la comprensión de la lista es un orden de magnitud más rápida!

Por supuesto, esto solo permanece así hasta que te quedes sin memoria. Lo cual me lleva a mi último punto. Hay dos razones principales para usar un generador: aprovechar los cortocircuitos y ahorrar memoria. Para segmentos / iterables muy grandes, los generadores son la forma obvia de ir, porque ahorran memoria. Pero si el cortocircuito no es una opción, casi nunca eliges generadores sobre listas para velocidad . Los elegiste para ahorrar memoria, y siempre es una compensación.

Answer 2

Completamente depende de los datos.

Los generadores tienen un tiempo de configuración fijo que se debe amortizar sobre cuántos elementos se llaman; Las listas de comprensión son más rápidas inicialmente, pero disminuirán sustancialmente a medida que se utilice más memoria con conjuntos de datos más grandes.

Recuerde que a medida que las listas cPython se expanden, la lista se redimensiona en un patrón de crecimiento de 4, 8, 16, 25, 35, 46, 58, 72, 88, .... Para una mayor comprensión de la lista, Python puede estar asignando hasta 4 veces más memoria que el tamaño de sus datos. Una vez que golpeas la máquina virtual --- realmente sloowww! Pero, como se dijo, las listas de comprensión son más rápidas que los generadores para pequeños conjuntos de datos.

Considere el caso 1 , una lista de listas 2x26:

LoL=[[c1,c2] for c1,c2 in zip(string.ascii_lowercase,string.ascii_uppercase)]
def lc_d(item=''d''):
return item in [i for sub in LoL for i in sub]
def ge_d(item=''d''):
return item in (y for x in LoL for y in x)
def any_lc_d(item=''d''):
return any(item in x for x in LoL)
def any_gc_d(item=''d''):
return any([item in x for x in LoL])
def lc_z(item=''z''):
return item in [i for sub in LoL for i in sub]
def ge_z(item=''z''):
return item in (y for x in LoL for y in x)
def any_lc_z(item=''z''):
return any(item in x for x in LoL)
def any_gc_z(item=''z''):
return any([item in x for x in LoL])
cmpthese.cmpthese([lc_d,ge_d,any_gc_d,any_gc_z,any_lc_d,any_lc_z, lc_z, ge_z])

Resultados en estos tiempos:

 rate/sec ge_z lc_z lc_d any_lc_z any_gc_z any_gc_d ge_d any_lc_d
ge_z 124,652 -- -10.1% -16.6% -44.3% -46.5% -48.5% -76.9% -80.7%
lc_z 138,678 11.3% -- -7.2% -38.0% -40.4% -42.7% -74.3% -78.6%
lc_d 149,407 19.9% 7.7% -- -33.3% -35.8% -38.2% -72.3% -76.9%
any_lc_z 223,845 79.6% 61.4% 49.8% -- -3.9% -7.5% -58.5% -65.4%
any_gc_z 232,847 86.8% 67.9% 55.8% 4.0% -- -3.7% -56.9% -64.0%
any_gc_d 241,890 94.1% 74.4% 61.9% 8.1% 3.9% -- -55.2% -62.6%
ge_d 539,654 332.9% 289.1% 261.2% 141.1% 131.8% 123.1% -- -16.6%
any_lc_d 647,089 419.1% 366.6% 333.1% 189.1% 177.9% 167.5% 19.9% --

Ahora considere el caso 2 , que muestra una gran disparidad entre un LC y gen. En este caso, estamos buscando un elemento en una lista de listas de 100 x 97 x 97 tipo de estructura:

LoL=[[str(a),str(b),str(c)]
for a in range(100) for b in range(97) for c in range(97)]
def lc_10(item=''10''):
return item in [i for sub in LoL for i in sub]
def ge_10(item=''10''):
return item in (y for x in LoL for y in x)
def any_lc_10(item=''10''):
return any([item in x for x in LoL])
def any_gc_10(item=''10''):
return any(item in x for x in LoL)
def lc_99(item=''99''):
return item in [i for sub in LoL for i in sub]
def ge_99(item=''99''):
return item in (y for x in LoL for y in x)
def any_lc_99(item=''99''):
return any(item in x for x in LoL)
def any_gc_99(item=''99''):
return any([item in x for x in LoL])
cmpthese.cmpthese([lc_10,ge_10,any_lc_10,any_gc_10,lc_99,ge_99,any_lc_99,any_gc_99],c=10,micro=True)

Resultados en estos tiempos:

 rate/sec usec/pass ge_99 lc_99 lc_10 any_lc_99 any_gc_99 any_lc_10 ge_10 any_gc_10
ge_99 3 354545.903 -- -20.6% -30.6% -60.8% -61.7% -63.5% -100.0% -100.0%
lc_99 4 281678.295 25.9% -- -12.6% -50.6% -51.8% -54.1% -100.0% -100.0%
lc_10 4 246073.484 44.1% 14.5% -- -43.5% -44.8% -47.4% -100.0% -100.0%
any_lc_99 7 139067.292 154.9% 102.5% 76.9% -- -2.4% -7.0% -100.0% -100.0%
any_gc_99 7 135748.100 161.2% 107.5% 81.3% 2.4% -- -4.7% -100.0% -100.0%
any_lc_10 8 129331.803 174.1% 117.8% 90.3% 7.5% 5.0% -- -100.0% -100.0%
ge_10 175,494 5.698 6221964.0% 4943182.0% 4318339.3% 2440446.0% 2382196.2% 2269594.1% -- -38.5%
any_gc_10 285,327 3.505 10116044.9% 8036936.7% 7021036.1% 3967862.6% 3873157.1% 3690083.0% 62.6% --

Como puede ver, depende y es una compensación ...

Answer 3

Contrariamente a la creencia popular, la lista de comprensiones es bastante buena para rangos moderados. El protocolo Iterator implica llamadas para iterator.next (), y las llamadas a funciones en Python son costosas.

Por supuesto, en algún momento la compensación de memoria / CPU de los generadores comenzará a pagar, pero para conjuntos pequeños la lista de comprensiones es muy eficiente.