Выражение списка по сравнению с выражением выражения.

Я отвечал на этот question, я предпочел здесь выражение генератора и использовал это, что, по моему мнению, было бы быстрее, поскольку генератору не нужно было создавать целое сначала:

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

И Левон использовал понимание списка в своем решении,

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

Но когда я сделал timit результаты для этих LC был быстрее, чем генератор:

~$ 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

то я увеличил размер списка и снова запустил его:

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' генератор был быстрее LC, но когда я искал средний элемент (11) и последний элемент, тогда LC снова бьет выражение генератора, и я не могу понять, почему?

~$ 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

Ответ 1

Расширяясь на Paulo, генераторные выражения часто медленнее, чем понимание списков из-за накладных расходов на вызовы функций. В этом случае поведение короткого замыкания in компенсирует медленность, если элемент найден довольно рано, но в противном случае шаблон сохраняется.

Я провел простой script через профилировщик для более детального анализа. Здесь script:

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

Вот соответствующие результаты, упорядоченные, чтобы сделать шаблоны более четкими.

         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)

Создание выражения генератора эквивалентно созданию функции генератора и ее вызову. Это объясняет один вызов <genexpr>. Затем в первом случае next вызывается 4 раза, до достижения d, всего 5 вызовов (раз 100000 итераций = ncalls = 500000). Во втором случае это называется 17 раз, в общей сложности 18 звонков; а в третьем - 24 раза, в общей сложности 25 звонков.

В первом случае ген превосходит понимание списка, но дополнительные вызовы next учитывают большую часть разницы между скоростью понимания списка и скоростью выражения генератора во втором и третьем случаях.

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

Я не уверен, что объясняет оставшееся время; кажется, что генераторные выражения будут медленнее, даже без дополнительных вызовов функций. Я полагаю, это подтверждает утверждение inspectorG4dget о том, что "создание понимания генератора имеет больше накладных расходов, чем понимание списка". Но в любом случае это довольно ясно показывает, что генераторные выражения медленнее в основном из-за вызовов на next.

Я добавлю, что, когда короткое замыкание не помогает, список понятий все еще быстрее, даже для очень больших списков. Например:

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

Как вы можете видеть, когда короткое замыкание не имеет значения, списки понятий последовательно ускоряются даже для списка списков с миллиметрами. Очевидно, что для реальных применений in в этих масштабах генераторы будут быстрее из-за короткого замыкания. Но для других видов итеративных задач, которые по-настоящему линейны по количеству элементов, понимание списков происходит почти всегда быстрее. Это особенно актуально, если вам нужно выполнить несколько тестов в списке; вы можете очень быстро перебирать уже построенное понимание списка:

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

В этом случае понимание списка на порядок быстрее!

Конечно, это остается правдой только до тех пор, пока у вас не закончится память. Это подводит меня к моему окончательному моменту. Существует две основные причины использования генератора: использовать короткое замыкание и экономить память. Для очень больших seqences/iterables генераторы - это очевидный путь, потому что они сохраняют память. Но если короткое замыкание не является вариантом, вы почти никогда не выбираете генераторы над списками для скорости. Вы выбрали их для сохранения памяти, и это всегда компромисс.

Ответ 2

Полностью зависит от данных.

Генераторы имеют фиксированное время установки, которое должно быть амортизировано по количеству вызовов; Первоначальные переходы быстрее изначально, но будут замедляться по мере увеличения использования памяти с большими наборами данных.

Вспомним, что по мере расширения списков cPython список изменяется в размере 4, 8, 16, 25, 35, 46, 58, 72, 88,.... Для большего понимания списков Python может выделять до 4 раз больше памяти, чем размер ваших данных. Как только вы нажмете на виртуальную машину --- на самом деле! Но, как уже было сказано, переписные списки быстрее, чем генераторы для небольших наборов данных.

Рассмотрим case 1, список списков 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])

Результаты этих таймингов:

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

Теперь рассмотрим case 2, которые показывают широкое несоответствие между LC и gen. В этом случае мы ищем один элемент в списке списков списков списков типов 100 x 97 x 97:

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)

Результаты в эти моменты:

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

Как вы можете видеть - это зависит, и это компромисс...

Ответ 3

Вопреки распространенному мнению, понимание списка довольно хорошо для умеренных диапазонов. Протокол Iterator подразумевает вызовы для iterator.next(), а вызовы функций в Python дороги.

Конечно, в какой-то момент компилятор памяти /cpu генераторов начнет платить, но для небольших наборов списки очень эффективны.