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.