Вопрос по python, list-comprehension, generator-expression, list, timeit – Понимание списка и странное время выражения выражения генератора?

32

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

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

Но когда я сделал время, результаты для этих 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 Я тоже буду настроен на ответы :) Levon
возможно из-за кеширования ... и генератора ... возможно, нужно больше вызовов (далее, yield, сохранить состояние и т. д.). и генераторы действительно эффективны в памяти. это точно. User007
почему не простоany(d in x for x in lis)? John La Rooy
Не в вопросе, который вы упомянули вышеstackoverflow.com/a/11964232/174728 John La Rooy
@gnibblerany() медленнее, чем само выражение генератора, посмотрите этоsolution Ashwini Chaudhary

Ваш Ответ

3   ответа
28

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

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

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 звонков.

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

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

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

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

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

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

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

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

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

13

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

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

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

Рассматриватьcase 1, список списков 2х26:

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

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

Спасибо, теперь это имеет больше смысла для меня.
генератор также не исчерпывает весь список, но он медленный. Ashwini Chaudhary
@Ashwini Chaudhary: генератор работает медленно по сравнению с LC с небольшими объемами данных. Посмотрите на сравнительные скорости в случае 2 и либо генератор, либоany Конструкция с помощью генератора пинает прикладом ЛК. Генераторы работают быстро, но им приходится преодолевать более длительное время настройки.
@senderle: Очень хорошие моменты, и я исправил их в своем посте.
9

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

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

Кроме того, создание понимания генератора имеет больше нативных накладных расходов, чем понимание списка

Похожие вопросы