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

Question

estaba respondiendo este question, prefería la expresión generador de aquí y utilizado este, por lo que pensé que sería más rápido que el generador no tiene que crear toda la lista en primer lugar:

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

Y Levon solía lista por 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 lo hice timeIt los resultados de estos LC era 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 

entonces aumentó el tamaño de la lista, y con fecha 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]] 

este tiempo para buscar 'd' generador era más rápido que el LC, pero cuando busqué un elemento central (11) y el último elemento a continuación, LC nuevo 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 llamadas a funciones. En este caso, el comportamiento de cortocircuito de in compensa esa lentitud si el elemento 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á la secuencia de comandos:

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() 

Éstos son los resultados relevantes, reordenados para hacer más clara de los patrones.

  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) 

Creación de un generador de expresión es equivalente a creating a generator function and calling it. Eso representa una llamada al <genexpr>. Luego, en el primer caso, 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 a next representan la mayor parte de la diferencia entre la velocidad de comprensión de la lista y la velocidad de expresión del generador en el segundo y tercer casos.

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

No estoy seguro de qué 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 de 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 en su mayoría debido a llamadas a next.

Añadiré que cuando los cortocircuitos no ayudan, las comprensiones de la lista son todavía más rápido, 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 se puede ver, cuando el cortocircuito es irrelevante, listas por comprensión son consistentemente más rápido incluso para un millón de ítems-larga lista de listas. Obviamente para los usos reales de in a estas escalas, los generadores serán más rápidos debido a un cortocircuito. Pero para otros tipos de tareas iterativas que son verdaderamente lineales en la cantidad de elementos, las comprensiones de listas son más o menos siempre más rápido. Esto es especialmente cierto si necesita realizar múltiples pruebas en una lista; Se puede recorrer más de una lista por comprensión ya incorporado 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 lista de comprensión es un orden de magnitud más rápido!

Por supuesto, esto solo permanece así hasta que se quede 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, usted casi nunca elige generadores sobre listas para velocidad.Los elegiste para ahorrar memoria, y siempre es una compensación.

Answer 2

Contrariamente a la creencia popular, las listas de comprensión son bastante buenas para los 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 los conjuntos pequeños las comprensiones de la lista son muy eficientes.

Answer 3

Totalmente 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 se expanden las listas de cPython, la lista cambia de tamaño en el 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 caso 1, una lista 2x26 de listas:

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]) 

Los 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%  -- 

---

Consideremos ahora el caso 2, que muestran gran disparidad entre un LC y gen. En este caso, estamos buscando un elemento en un 100 x 97 x 97 lista de listas 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) 

Los 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 se puede ver - se depende y es una compensación ...