19 | Углубленное понимание итераторов и генераторов

Когда вы впервые познакомились с Python, вы могли написать утверждения типа for i in [2, 3, 5, 7, 11, 13]: print(i). Оператор for in интуитивно понятен и нагляден, он гораздо лаконичнее и понятнее, чем операторы типа for (int i = 0; i < n; i ) printf(“%d\\n”, a[i]) в C и Java.

Однако задумывались ли вы когда-нибудь о том, что именно происходит, когда Python обрабатывает оператор for in? Какие объекты могут быть перечислены с помощью for in?

В этом уроке мы углубимся в базовую реализацию контейнерных типов Python и узнаем о том, что называется итераторами и генераторами.

Контейнеры, итерабельные объекты и итераторы, которые вы должны были использовать

Концепцию контейнера легко понять. Как мы уже говорили, все в Python – это объект, абстракция объекта – класс, а коллекция объектов – контейнер.

Списки ( list: [0, 1, 2]), кортежи ( tuple: (0, 1, 2)), словари ( dict: {0:0, 1:1, 2:2}) и множества ( set: set([0, 1, 2])) – это все контейнеры. Что касается контейнеров, вы можете легко представить их как единицы, состоящие из нескольких элементов, а разница между различными контейнерами заключается в реализации внутренней структуры данных. Тогда для разных сценариев можно выбирать контейнеры с разной временной и пространственной сложностью.

Все контейнеры итерируемы. Здесь итерация – это не то же самое, что перечисление. Итерацию можно представить себе так: когда вы идете покупать яблоки, продавец не говорит вам, сколько яблок у него в наличии. Поэтому каждый раз вам нужно говорить продавцу, что вы хотите яблоко, а затем продавец предпринимает действия: либо дает вам яблоко, либо говорит, что яблоки распроданы. Вам не нужно знать, как продавец расставляет яблоки на складе.

Строго говоря, итератор предоставляет метод next. После вызова этого метода вы либо получаете следующий объект контейнера, либо получаете ошибку StopIteration (яблоки распроданы). Вам не нужно указывать индекс элемента, как в списке, потому что такие контейнеры, как словари и множества, не имеют индексации. Например, если словарь реализован с помощью хэш-таблицы, вам достаточно знать, что функция next может получить все элементы один за другим без дублирования или пропуска.

Объект iterable возвращает итератор через функцию iter(), а затем обход может быть осуществлен через функцию next(). Оператор for-in неявно скрывает этот процесс, поэтому вам нужно лишь приблизительно знать, что он делает.

Давайте посмотрим на следующий код, который в основном показывает, как определить, является ли объект итерируемым. Конечно, есть и другой способ сделать это – isinstance(obj, Iterable).

def is_iterable(param):
     try:
         iter(param)
         return True
     except TypeError:
         return False
 
 params = [
     1234,
     '1234',
     [1, 2, 3, 4],
     set([1, 2, 3, 4]),
     {1:1, 2:2, 3:3, 4:4},
     (1, 2, 3, 4)
 ]

for param in params:
     print('{} is iterable? {}'.format(param, is_iterable(param)))
 
 ########## Output ##########
 
 1234 is iterable? False
 1234 is iterable? True
 [1, 2, 3, 4] is iterable? True
 {1, 2, 3, 4} is iterable? True
 {1: 1, 2: 2, 3: 3, 4: 4} is iterable? True
 (1, 2, 3, 4) is iterable? True

С помощью этого кода можно увидеть, что среди заданных типов все типы данных, кроме числа 1234, являются итерируемыми.

Что такое генератор?

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

Запомните одну вещь: генераторы – это ленивые версии итераторов.

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

import os
 import psutil
 
 # Display the memory usage of the current Python program
 def show_memory_info(hint):
     pid = os.getpid()
     p = psutil.Process(pid)

  info = p.memory_full_info()
     memory = info.uss / 1024. / 1024
     print('{} memory used: {} MB'.format(hint, memory))

def test_iterator():
     show_memory_info('initing iterator')
     list_1 = [i for i in range(100000000)]
     show_memory_info('after iterator initiated')
     print(sum(list_1))
     show_memory_info('after sum called')
 
 def test_generator():
     show_memory_info('initing generator')
     list_2 = (i for i in range(100000000))
     show_memory_info('after generator initiated')
     print(sum(list_2))
     show_memory_info('after sum called')
 
 %time test_iterator()
 %time test_generator()
 
 ########## Output ##########
 
 initing iterator memory used: 48.9765625 MB
 after iterator initiated memory used: 3920.30078125 MB
 4999999950000000
 after sum called memory used: 3920.3046875 MB
 Wall time: 17 s
 initing generator memory used: 50.359375 MB
 after generator initiated memory used: 50.359375 MB
 4999999950000000
 after sum called memory used: 50.109375 MB
 Wall time: 12.5 s

Объявить итератор очень просто, [ i for i in range(100000000)] может сгенерировать список со 100 миллионами элементов. Каждый элемент сохраняется в памяти после его генерации. Как видно из кода, они занимают огромное количество памяти, и если памяти не хватит, возникнет ошибка OOM.

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

Поэтому родилась концепция генератора. Когда вы вызываете функцию next(), генерируется следующая переменная. Генераторы в Python пишутся с использованием круглых скобок, ( i for i in range(100000000)), которые инициализируют генератор.

В результате хорошо видно, что генераторы не занимают большой объем памяти, как итераторы, и вызываются только при использовании. Более того, когда генератор инициализирован, ему не нужно выполнять операцию генерации один раз. По сравнению с функцией test_iterator() функция test_generator() экономит процесс генерации 100 миллионов элементов один раз, поэтому она занимает меньше времени, чем итератор.

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

Генераторы: Какие еще трюки мы можем разыграть?

В математике существует тождество, которое гласит: (1 2 3 … n)^2 = 1^3 2^3 3^3 … n^3. Вы, вероятно, изучали это в средней школе. Теперь давайте проверим правильность этой формулы. Как обычно, начнем с кода. Сначала посмотрите на него и не волнуйтесь, если вы еще не поняли его. Я объясню его подробно позже.

def generator(k):
     i = 1
     while True:
         yield i ** k
         i += 1
 
 gen_1 = generator(1)
 gen_3 = generator(3)
 print(gen_1)
 print(gen_3)
 
 def get_sum(n):
     sum_1, sum_3 = 0, 0
     for i in range(n):
         next_1 = next(gen_1)
         next_3 = next(gen_3)
         print('next_1 = {}, next_3 = {}'.format(next_1, next_3))
         sum_1 += next_1
         sum_3 += next_3
     print(sum_1 * sum_1, sum_3)
 
 get_sum(8)
 
 ########## Output ##########
 
 <generator object generator at 0x000001E70651C4F8>
 <generator object generator at 0x000001E70651C390>
 next_1 = 1, next_3 = 1
 next_1 = 2, next_3 = 8
 next_1 = 3, next_3 = 27
 next_1 = 4, next_3 = 64
 next_1 = 5, next_3 = 125
 next_1 = 6, next_3 = 216
 next_1 = 7, next_3 = 343
 next_1 = 8, next_3 = 512
 1296 1296

В этом разделе кода сначала обратите внимание на функцию generator(), которая возвращает генератор.

Следующий выход является ключевым. Для начинающих можно понять, что когда функция добежит до этой строки, программа сделает здесь паузу, а затем выскочит, но куда она выскочит? Ответ – в функцию next(). Что же делает i ** k? Это фактически становится возвращаемым значением функции next().

Таким образом, при каждом вызове функции next(gen) приостановленная программа воскресает и продолжает выполняться вниз от yield; при этом обратите внимание, что локальная переменная i не очищается, а продолжает накапливаться. Мы видим, что next_1 изменяется от 1 до 8, а next_3 – от 1 до 512.

Умные люди должны были заметить, что этот генератор действительно может продолжать работу! Да, на самом деле, итератор – это конечное множество, а генератор может стать бесконечным множеством. Нужно только вызвать next(), и генератор автоматически сгенерирует новые элементы на основе операции, а затем вернет их вам, что очень удобно.

В этот момент богатые товарищи не должны сидеть на месте. Итак, можем ли мы стать еще более могущественными?

Не волнуйтесь, давайте рассмотрим другую задачу: дан список и заданное число, найдите позицию этого числа в списке.

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

def index_normal(L, target):
     result = []
     for i, num in enumerate(L):
         if num == target:
             result.append(i)
     return result
 
 print(index_normal([1, 6, 2, 4, 5, 2, 8, 6, 3, 2], 2))
 
 ########## Output ##########
 
 [2, 5, 9]

Итак, как мы можем использовать итераторы? Без лишних слов, давайте посмотрим на код.

def index_generator(L, target):
     for i, num in enumerate(L):
         if num == target:
             yield i
 
 print(list(index_generator([1, 6, 2, 4, 5, 2, 8, 6, 3, 2], 2)))
 
 ########## Output ##########
 
 [2, 5, 9]

Как умный читатель, вы должны были заметить очевидную разницу, поэтому я не буду объяснять ее слишком подробно. Единственное, что следует подчеркнуть, это то, что index_generator вернет объект Generator, который необходимо преобразовать в список перед использованием print для вывода.

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

Давайте сначала интерпретируем саму проблему. Последовательность означает список, а подпоследовательность – ситуацию, когда элементы одного списка появляются по порядку во втором списке, но они не обязательно должны быть вместе. Например, [1, 3, 5] является подпоследовательностью [1, 2, 3, 4, 5], а [1, 4, 3] – нет.

Для решения этой проблемы традиционный алгоритм является жадным алгоритмом. Мы храним два указателя, указывающих на начало двух списков, а затем сканируем вторую последовательность до конца. Если число совпадает с числом, на которое указывает первый указатель, то мы перемещаем первый указатель вперед на один шаг. Когда первый указатель выходит из последнего элемента первой последовательности, мы возвращаем True, в противном случае – False.

Однако, если мы напишем этот алгоритм обычным образом, он должен занять около десяти строк.

Что же делать, если мы используем итераторы и генераторы?

def is_subsequence(a, b):
     b = iter(b)
     return all(i in b for i in a)
 
 print(is_subsequence([1, 3, 5], [1, 2, 3, 4, 5]))
 print(is_subsequence([1, 4, 3], [1, 2, 3, 4, 5]))
 
 ########## 输出 ##########
 
 True
 False

Вы запутались в этих нескольких строчках кода и не понимаете, что происходит? Давайте усложним этот код, а затем пройдемся по нему шаг за шагом.

def is_subsequence(a, b):
     b = iter(b)
     print(b)
 
     gen = (i for i in a)
     print(gen)
 
     for i in gen:
         print(i)
 
     gen = ((i in b) for i in a)
     print(gen)
 
     for i in gen:
         print(i)
 
     return all(((i in b) for i in a))
 
 print(is_subsequence([1, 3, 5], [1, 2, 3, 4, 5]))
 print(is_subsequence([1, 4, 3], [1, 2, 3, 4, 5]))
 
 ########## Output ##########
 
 <list_iterator object at 0x000001E7063D0E80>
 <generator object is_subsequence.<locals>.<genexpr> at 0x000001E70651C570>
 1
 3
 5
 <generator object is_subsequence.<locals>.<genexpr> at 0x000001E70651C5E8>
 True
 True
 True
 False
 <list_iterator object at 0x000001E7063D0D30>
 <generator object is_subsequence.<locals>.<genexpr> at 0x000001E70651C5E8>
 1
 4
 3
 <generator object is_subsequence.<locals>.<genexpr> at 0x000001E70651C570>
 True
 True
 False
 False

Во-первых, строка ” b = iter(b)” преобразует список b в итератор. Я не буду пока объяснять, зачем это делается.

Далее, оператор ” gen = (i for i in a)” прост для понимания. Оно создает генератор, который может выполнять итерацию над объектом a и выводить 1, 3, 5. Что касается ” (i in b)”, то над ним нужно поразмыслить. Можете ли вы вспомнить цикл “for in”?

Да, ” (i in b)” примерно эквивалентен следующему коду:

while True:
     val = next(b)
     if val == i:
         yield True

Здесь ловко используется свойство генераторов, когда функция next() сохраняет текущий указатель при выполнении. Например, посмотрите на следующий пример:

b = (i for i in range(5))
 
 print(2 in b)
 print(4 in b)
 print(3 in b)
 
 ########## Output ##########
 
 True
 True
 False

Что касается последней функции all(), то она очень проста. Она используется для определения того, все ли элементы итератора равны True. Если да, то она возвращает True, в противном случае – False.

Итак, мы элегантно решили этот вопрос интервью. Однако следует помнить, что при собеседовании старайтесь не использовать подобную технику, поскольку ваш интервьюер может быть не знаком с использованием генераторов и, возможно, не читал мою колонку Geek Time. Однако в плане практического применения этих технических знаний вы уже более компетентны, чем многие люди.

Продолжайте в том же духе!

Резюме

Подводя итог, сегодня мы поговорили о четырех различных объектах: контейнерах, итерируемых объектах, итераторах и генераторах.

• Контейнеры – это итерируемые объекты. Итерируемые объекты могут вызывать функцию iter() для получения итератора. Итератор может использовать функцию next() для получения следующего элемента, таким образом поддерживая обход.
• Генераторы – это особый тип итераторов (обратите внимание, что обратная логика не работает). Используя генераторы, вы можете писать более чистый код; с помощью генераторов можно разумно сократить использование памяти, оптимизировать структуру программы и повысить ее скорость.
• В Python 2 генераторы являются важной реализацией coroutines; после введения синтаксиса async/await в Python 3.5 способ реализации coroutines с помощью генераторов отошел на второй план. Мы продолжим изучать корутины Python в следующем уроке.

Вопрос для размышления

Оставляю вас с вопросом для размышления. Для генератора с конечным числом элементов, что произойдет, если вы продолжите вызывать next() после завершения итерации? Можно ли обойти генератор несколько раз?

Не стесняйтесь оставить сообщение и обсудить со мной этот вопрос. Вы также можете поделиться этой статьей со своими коллегами и друзьями и вместе добиться успехов в общении.

Спасибо за внимание!