Скорость для повторения нескольких раз по генератору по сравнению со списком

Question

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

Мое понимание (операцией я имею в виду любое выражение, определяющее элемент):

• список требует п операции для инициализации
• , но затем каждый цикл по списку только захват элемент из памяти
• , таким образом, м петли по списку требуют только n операции
• генератор не требует каких-либо операции для инициализации
• однако, цикл над генератором работает операции в лета
• , таким образом, один цикл над генератором требует п операции
• но м петли над генератором требуют NXM операции
  

И я проверил мои ожидания, используя следующий код:

from timeit import timeit 

def pow2_list(n): 
    """Return a list with powers of 2""" 

    results = [] 

    for i in range(n): 
     results.append(2**i) 

    return results 

def pow2_gen(n): 
    """Generator of powers of 2""" 

    for i in range(n): 
     yield 2**i 

def loop(iterator, n=1000): 
    """Loop n times over iterable object""" 

    for _ in range(n): 
     for _ in iterator: 
      pass 

l = pow2_list(1000) # point to a list 
g = pow2_gen(1000) # point to a generator 


time_list = \ 
    timeit("loop(l)", setup="from __main__ import loop, l", number=10) 

time_gen = \ 
    timeit("loop(g)", setup="from __main__ import loop, g", number=10) 

print("Loops over list took: ", time_list) 
print("Loops over generator took: ", time_gen) 

И результаты удивили меня ...

Loops over list took: 0.20484769299946493 
Loops over generator took: 0.0019217690005461918 

Каким-то образом с помощью генератора появляется гораздо быстрее, чем списки, даже когда цикл более 1000 раз. И в этом случае мы говорим о двух порядках! Зачем?

EDIT:

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

>>> x = range(10) 
>>> sum(x) 
45 
>>> sum(x) 
45 

Но это было наивным (диапазон не является генератором ...).

Что касается возможного дублирующегося комментария: моя проблема связана с несколькими циклами по генератору, что не объясняется в другом потоке.

Answer 1

Ваш генератор на самом деле только один цикл. После создания с pow2_gen, g хранит генератор; в первый раз через loop этот генератор потребляется и испускает StopIteration. В других случаях через loop, next(g) (или g.next() в Python 2) просто продолжает бросать StopIteration, поэтому в действии g представляет собой пустую последовательность.

Чтобы сделать сравнение более справедливым, вам нужно будет повторно создать генератор при каждом цикле.

Еще одна трудность с тем, как вы подходили к этому, заключается в том, что вы вызываете append, чтобы создать свой список, что, вероятно, является самым медленным способом построения списка. Чаще всего списки создаются с использованием списков.

Следующий код позволяет нам подобрать время более аккуратно. create_list и create_gen создают списки и генераторы, соответственно, используя выражения списка и выражения генератора. time_loop походит на ваш метод loop, в то время как time_apply - это версия loop, которая каждый раз заново создает итерируемый цикл.

def create_list(n=1000): 
    return [2**i for i in range(n)] 

def create_gen(n=1000): 
    return (2**i for i in range(n)) 

def time_loop(iterator, n=1000): 
    for t in range(n): 
     for v in iterator: 
      pass 

def time_apply(create_fn, fn_arg, n=1000): 
    for t in range(n): 
     iterator = create_fn(fn_arg) 
     time_loop(iterator, 1) 

print('time_loop(create_list): %.3f' % timeit("time_loop(create_list(1000))", 
               setup="from __main__ import *", 
               number=10)) 

print('time_loop(create_gen): %.3f' % timeit("time_loop(create_gen(1000))", 
              setup="from __main__ import *", 
              number=10)) 

print('time_apply(create_list): %.3f' % timeit("time_apply(create_list, 1000)", 
               setup="from __main__ import *", 
               number=10)) 

print('time_apply(create_gen): %.3f' % timeit("time_apply(create_gen, 1000)", 
               setup="from __main__ import *", 
               number=10)) 

Результаты на моей коробке предположить, что построение списка (time_apply(create_list)) аналогичен по времени (или, может быть, даже быстрее, чем) построение генератора (time_apply(create_gen)).

time_loop(create_list): 0.244 
time_loop(create_gen): 0.028 
time_apply(create_list): 21.190 
time_apply(create_gen): 21.555 

Вы можете увидеть тот же эффект, вы документированный в вашем вопросе, который является то, что time_loop(create_gen) является порядок быстрее, чем time_loop(create_list). Опять же, это потому, что созданный генератор только повторяется один раз, а не множество циклов над списком.

Как вы предполагаете, построение списка один раз и повторение его много раз (time_loop(create_list)) происходит быстрее, чем повторение по генератору много раз (time_apply(create_gen)) в этом конкретном сценарии.

Компромисс между списком и генератором будет сильно зависеть от того, насколько большой итератор вы создаете. С 1000 пунктов, я бы ожидал, что списки будут довольно быстрыми. С 100 000 предметов все может выглядеть по-другому.

print('create big list: %.3f' % timeit("l = create_list(100000)", 
             setup="from __main__ import *", 
             number=10)) 

print('create big gen: %.3f' % timeit("g = create_gen(100000)", 
             setup="from __main__ import *", 
             number=10)) 

Здесь я получаю:

create big list: 209.748 
create big gen: 0.023 

Python использует между 700 и 800 МБ памяти, строящей большой список; генератор почти ничего не использует. Распределение памяти и очистка мусора являются дорогостоящими в Python и, как ожидается, делают ваш код медленным; Генераторы - это очень простой способ избежать обманывания оперативной памяти вашего компьютера и может иметь большое значение для времени выполнения.

Answer 2

Ваш тест не работает, потому что ваш генератор исчерпан на первом проходе loop(). Это одно из преимуществ списков над генераторами, вы можете перебирать их несколько раз (за счет хранения полного списка в памяти).

Вот иллюстрация этого. Я использую выражение генератора и список понимание (который более оптимизированный, чем при использовании append в for цикле), но концепция та же:

>>> gen = (i for i in range(3)) 
>>> for n in range(2): 
...  for i in gen: 
...   print(i) 
... 
0 # 1st print 
1 
2 # after one loop the iterator is exhausted 
>>> 
>>> lst = [x for x in range(3)] 
>>> for n in range(2): 
...  for i in lst: 
...   print(i) 
... 
0 # 1st print 
1 
2 
0 # 2nd print 
1 
2 
>>> 

Для эквивалентного испытания вы должны восстановить генератор после каждой итерации внешний контур:

>>> for n in range(2): 
...  gen = (i for i in range(3)) 
...  for i in gen: 
...   print(i) 
... 
0 # 1st print 
1 
2 
0 # 2nd print 
1 
2 
>>> 

Answer 3

У вас возникла проблема с вашим тестом. А именно, генератор не может использоваться повторно. После исчерпания его нельзя использовать снова, и нужно создать новый. например.

l = [0, 1, 2, 4, 5] 
g = iter(l) # creates an iterator (a type of generator) over the list 

sum_list0 = sum(l) 
sum_list1 = sum(1) 
assert sum_list0 == sum_list1 # all working normally 

sum_gen0 = sum(g) # consumes generator 
sum_gen1 = sum(g) # sum of empty generator is 0 
assert sum_gen0 == sum_list1 # result is correct 
assert sum_gen1 == sum_list1, "second result was incorrect" # because generator was exhausted 

Для теста на работу необходимо воссоздать генератор заново в заявлении вы передаете timeit.

from timeit import timeit 

n = 1000 
repeats = 10000 

list_powers = [2**i for i in range(n)] 
def gen_powers(): 
    for i in range(n): 
     yield 2**i 

time_list = timeit("min(list_powers)", globals=globals(), number=repeats) 
time_gen = timeit("min(gen_powers())", globals=globals(), number=repeats) 

print("Loops over list took: ", time_list) 
print("Loops over generator took: ", time_gen) 

дает:

Loops over list took: 0.24689035064701784 
Loops over generator took: 13.551637053904571 

Теперь генератор на два порядка медленнее, чем в списке. Этого следует ожидать, так как размер последовательности мал по сравнению с количеством итераций над последовательностью. Если n велико, то создание списка становится медленнее. Это связано с тем, как списки расширяются при добавлении новых элементов, а конечный размер не передается в список при его создании. Увеличение количества итераций ускорит список по сравнению с генератором, так как количество работы, которое требуется генератору, увеличивается, а для списка оно остается постоянным. Так как n составляет всего 1000 (малый), а repeats доминирует над n, то генератор работает медленнее.