В данной главе мы познакомимся с одним важным объектом в Python — итераторами.
Быстрый поиск
Что есть итераторы
Итераторы — объекты в Python, позволяющие последовательно возвращать элементы некоторой последовательности (возможно, вычислимой и бесконечной).
Итератор Работает по очень простому алгоритму:
- Метод
__next__()возвращает следующий элемент в итераторе - При окончании последовательности возвращается исключение, в обычном случае это исключение StopIteration
Итератор можно сделать из любого объекта, чьи элементы могут каким-то образом быть последовательно перебраны. В частности, все последовательности могут использоваться для создания итератора.
Важное отличие итератора от простого прохода по последовательности элементов — его «одноразовость»: для повторного обращения к элементам необходимо заново создавать итератор.
>>> seq = "qwertyuio"
>>> i = iter(seq)
>>> i
<str_ascii_iterator object at 0x7f0094e59750>
>>> next(i)
'q'
>>> next(i)
'w'
>>> next(i)
'e'
>>> next(i)
'r'
>>> next(i)
't'
>>> next(i)
'y'
>>> next(i)
'u'
>>> next(i)
'i'
>>> next(i)
'o'
>>> next(i)
Traceback (most recent call last):
File "<python-input-13>", line 1, in <module>
next(i)
~~~~^^^
StopIteration
>>>
>>> seq = "qwertyuio"
>>> i = iter(seq)
>>> list(i)
['q', 'w', 'e', 'r', 't', 'y', 'u', 'i', 'o']
>>> list(i)
[]
>>>
При работе с итераторами иногда удобнее обрабатывать не исключение, а некоторое контрольное значение, его можно задать параметром next:
>>> i = iter("qwertyui")
>>> for j in range(10):
... print(next(i, None))
...
q
w
e
r
t
y
u
i
None
None
>>>
Сама функция создания итератора также имеет отдельный параметр — ограничение для прерывания:
>>> import random
>>> e = iter(lambda: random.randrange(1, 10), 7)
>>> list(e)
[8]
>>> e = iter(lambda: random.randrange(1, 10), 7)
>>> list(e)
[5, 3, 5, 4, 9, 1, 9, 5, 6, 5, 8, 2, 6, 6, 9, 1, 1, 1, 6, 1, 9, 3, 5, 9, 6, 2, 3, 3, 3, 2, 2, 5, 5, 8,5, 3, 5, 5, 9, 6, 3]
>>> e = iter(lambda: random.randrange(1, 10), 7)
>>> list(e)
[]
>>> e = iter(lambda: random.randrange(1, 10), 7)
>>> list(e)
[]
>>> e = iter(lambda: random.randrange(1, 10), 7)
>>> list(e)
[6, 9, 5, 8]
>>>
Протокол итератора — метод __iter__. Однако итератор также можно получить при наличии метода __getitem__:
>>> s = "qwert"
>>> s.__iter__
<method-wrapper '__iter__' of str object at 0x7f0094eb27c0>
>>>
>>> class C:
... def __getitem__(self, idx):
... print(f"<{idx}>")
...
>>> c = C()
>>> iter(c)
<iterator object at 0x7f0094eb2770>
>>> i = iter(c)
>>> next(i)
<0>
>>> next(i)
<1>
>>> i.__next__()
<2>
>>> i.__next__()
<3>
>>>
Особенность таких итераторов — для них необходимо существование объекта-источника, поскольку для получения каждого элемента производится явное обращение к нему и его методу:
>>> class C:
... lst = [1, 2, 3, 4, 5]
... def __getitem__(self, idx):
... return C.lst[idx]
...
>>> i = iter(C())
>>> next(i)
1
>>> next(i)
2
>>> del C
>>> next(i)
Traceback (most recent call last):
File "<python-input-75>", line 1, in <module>
next(i)
~~~~^^^
File "<python-input-70>", line 4, in __getitem__
return C.lst[idx]
^
NameError: name 'C' is not defined
>>> i = iter("qwertyu")
>>> s = "qwerty"
>>> i = iter(s)
>>> next(i)
'q'
>>> next(i)
'w'
>>> del s
>>> next(i)
'e'
>>>
Итераторы в Python
Как и со словарями, с итераторами в Python мы встречаемся постоянно. Самый часто используемый нами итератор находится в цикле for: в нём на основе последовательности как раз создаётся итератор, на шагах цикла вызывается __next__, полученный объект связывается с именем из for и отправляется на обработку в тело цикла. А окончание работы цикла отслеживание по получению StopIteration. К слову, распаковка последовательностей также работает за счёт создания итератора.
Кроме неявных итераторов существует и множество вполне осязаемых:
- Уже знакомые нам с последовательностей enumerate и reversed являются итераторами:
>>> s = [1, 2, 3, 4, 5]
>>> i = enumerate(s)
>>> i
<enumerate object at 0x7fafae7de3e0>
>>> next(i)
(0, 1)
>>> next(i)
(1, 2)
>>> next(i)
(2, 3)
>>> next(i)
(3, 4)
>>> next(i)
(4, 5)
>>> next(i)
Traceback (most recent call last):
File "<python-input-101>", line 1, in <module>
next(i)
~~~~^^^
StopIteration
>>> r = reversed(s)
>>> r
<list_reverseiterator object at 0x7fafaea1cc40>
>>> for i in range(8):
... print(next(r, None))
...
5
4
3
2
1
None
None
None
>>>
- Знакомый после работы со словарями zip — также является итератором. При этом для сбора кортежей элементов также используются итераторы, взятые от самых последовательностей. Этим объясняется логика работы zip с «выравниванием» по самой маленькой последовательности: как только для какого-то из внутренних итераторов срабатывает признак конца, весь итератор zip завершается
>>> z = zip("ASLKFHVLS", [1, 2, 3, 4, 5, 6, 7], ((), 12, "qwerty", set()))
>>> z
<zip object at 0x7fafae7eeac0>
>>> for i in range(7):
... next(z, "QQQ")
...
('A', 1, ())
('S', 2, 12)
('L', 3, 'qwerty')
('K', 4, set())
'QQQ'
'QQQ'
'QQQ'
>>>
- Итератор
filter(Pred, seq)для каждого элемента последовательности проверяет значение предиката от него и возвращает элемент в случае успеха:
>>> def pred(i):
... return -1 < i < 2
...
>>> e = filter(pred, range(-5, 5))
>>> e
<filter object at 0x7f00950b6dd0>
>>> next(e)
0
>>> next(e)
1
>>> next(e)
Traceback (most recent call last):
File "<python-input-28>", line 1, in <module>
next(e)
~~~~^^^
StopIteration
>>>
- Итератор map возвращает результат применения некоторой функции к элементам последовательности:
>>> s = [1, 2, 3, 4, 5]
>>> def func(item):
... return f'2 * {item} + 1 = {2 * item + 1}'
...
>>> m = map(func, s)
>>> m
<map object at 0x7fafaea1d810>
>>> list(m)
['2 * 1 + 1 = 3', '2 * 2 + 1 = 5', '2 * 3 + 1 = 7', '2 * 4 + 1 = 9', '2 * 5 + 1 = 11']
>>>
Генераторы
Генератор — это объект, поддерживающий протокол итератора, по вызову вычисляющий каждое следующее значение последовательности. Самый элементарный генератор это циклический конструктор:
>>> i = (item * 2 + 1 for item in range(10))
>>> i
<generator object <genexpr> at 0x7fafae7e8040>
>>> list(i)
[1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
>>>
Функции-итераторы тоже правильнее называть генераторами, поскольку в процессе их работы они последовательно проводят операции над текущим значением и возвращают результат над ним.
Для написания произвольного генератора не нужно ничего особенного. Генератор-функция структурно ничем не отличается от обычной, однако возвращает вычисленное значение не с помощью return, а с помощью специального оператора yield:
>>> def genf(n):
... yield "Start"
... for i in range(n):
... yield f"<i>"
... yield "END"
...
>>> genf
<function genf at 0x7f0094edc360>
>>> e = genf(5)
>>> e
<generator object genf at 0x7f0094e7e5a0>
>>> list(e)
['Start', '<i>', '<i>', '<i>', '<i>', '<i>', 'END']
>>>
При работе генераторов нарушается привычная логика работы с фреймами функций на стеке. При вызове yield функция не завершается, а просто зависает на указанном месте выполнения, её фрейм остаётся неизменным, а управление переходит в пространство вызова генератора с передачей полученного внутри значения. При следующем обращении к генератору у правление перейдёт в ту же точку, из которой было изъято, и работа продолжится:
>>> def genf(n):
... print("**1")
... yield "Start"
... for i in range(n):
... print(f"**{i}/{n}")
... yield f"<{i}>"
... print("**done")
... yield "END"
...
>>> e = genf(5)
>>> res = next(e)
**1
>>> res
'Start'
>>> res = next(e)
**0/5
>>> res
'<0>'
>>> res = next(e)
**1/5
>>> res
'<1>'
>>> res = next(e)
**2/5
>>> res
'<2>'
>>>
>>> res = next(e)
**3/5
>>> res
'<3>'
>>> res = next(e)
**4/5
>>> res
'<4>'
>>> res = next(e)
**done
>>> res
'END'
>>> res = next(e)
Traceback (most recent call last):
File "<python-input-76>", line 1, in <module>
res = next(e)
StopIteration
>>> res
'END'
>>>
Удаление фрейма происходит либо по завершении генератора, либо по явному вызову return
>>> def find13(seq):
... for el in seq:
... if el == 13:
... return
... else:
... yield el
...
>>> e = find13(range(10, 20))
>>> list(e)
[10, 11, 12]
>>>
Состояние фрейма незавершённого генератора и его локальные параметры можно, обратившись к специальным полям:
>>> def genf(n):
... for i in range(n):
... yield f'<{i}>'
...
>>> i = genf(5)
>>> i.gi_frame.f_locals
{'n': 5}
>>> next(i)
'<0>'
>>> next(i)
'<1>'
>>> i.gi_frame.f_locals
{'n': 5, 'i': 1}
>>>
Для того, чтобы использовать вложенные итераторы (или генераторы) в генераторе с передачей управления в них, необходимо использовать составной оператор yield from. При его вызове внутренний генератор итеративно будет отрабатывать каждое обращение к нашему генератору (все действия будут как бы пробрасываться сквозь наш генератор что в одну, что в другую сторону), пока не закончится, после чего управление вернётся в генератор
>>> def gen(seq):
... for el in seq:
... yield f"<{el}>"
...
>>> list(gen("WET"))
['<W>', '<E>', '<T>']
>>>
>>> def repeat(seq, n):
... for i in range(n):
... yield from gen(seq)
...
>>> list(repeat("WET", 3))
['<W>', '<E>', '<T>', '<W>', '<E>', '<T>', '<W>', '<E>', '<T>']
>>>
С помощью yield можно не только передавать значения, но и получать их обратно. Работа с таким параметрическим итератором ведётся с помощью метода send. Первое обращение к генератору производится строго с помощью next или send(None)(что, на самом деле, одно и то же), а каждое следующее обращение — как угодно (в случае send в генератор будет передаваться указанный параметр, в случае next будет передаваться None):
>>> def stopiccot(base):
... res = yield base
... while res:
... res += yield res + base
...
>>> e = stopiccot(100500)
>>> next(e)
100500
>>> e.send(1)
100501
>>> e.send(1)
100502
>>> e.send(-1)
100501
>>> e.send(-1)
Traceback (most recent call last):
File "<python-input-94>", line 1, in <module>
e.send(-1)
~~~~~~^^^^
StopIteration
>>> e = stopiccot(100500)
>>> e.send(1)
Traceback (most recent call last):
File "<python-input-96>", line 1, in <module>
e.send(1)
~~~~~~^^^
TypeError: can't send non-None value to a just-started generator
>>> e.send(None)
100500
>>> e.send(0)
Traceback (most recent call last):
File "<python-input-98>", line 1, in <module>
e.send(0)
~~~~~~^^^
StopIteration
>>>
Чуть ближе рассмотрим данный пример, чтобы разобраться с приоритетностью оператора yield. Поближе рассмотрим значения локальных переменных генератора:
>>> def stopiccot(base):
... res = yield base
... while res:
... res += yield res + base
...
>>> i = stopiccot(100500)
>>> i.gi_frame.f_locals
{'base': 100500}
>>> next(i)
100500
>>> i.gi_frame.f_locals
{'base': 100500}
>>> i.send(1)
100501
>>> i.gi_frame.f_locals
{'base': 100500, 'res': 1}
>>> i.send(-1)
Traceback (most recent call last):
File "<python-input-155>", line 1, in <module>
i.send(-1)
~~~~~~^^^^
StopIteration
>>>
Теперь явно укажем скобки вокруг всего выражения после yield. На первый взгляд может показаться, что приоритет yield выше арифметических операций, однако результат работы окажется абсолютно таким же, как и без скобок:
>>> def stopiccot(base):
... res = yield base
... while res:
... res += yield (res + base)
...
>>> i = stopiccot(100500)
>>> i.gi_frame.f_locals
{'base': 100500}
>>> next(i)
100500
>>> i.gi_frame.f_locals
{'base': 100500}
>>> i.send(1)
100501
>>> i.gi_frame.f_locals
{'base': 100500, 'res': 1}
>>> i.send(-1)
Traceback (most recent call last):
File "<python-input-165>", line 1, in <module>
i.send(-1)
~~~~~~^^^^
StopIteration
>>>
На деле с точки зрения приоритетов необходимо воспринимать yield буквально как промежуточный return, возвращающий результат выражения. Явное же выделение его в приоритете операций может значительно поменять логику генератора:
>>> def stopiccot(base):
... res = yield base
... while res:
... res += (yield res) + base
...
>>> i = stopiccot(100500)
>>> i.gi_frame.f_locals
{'base': 100500}
>>> next(i)
100500
>>> i.gi_frame.f_locals
{'base': 100500}
>>> i.send(1)
1
>>> i.gi_frame.f_locals
{'base': 100500, 'res': 1}
>>> i.send(1)
100502
>>> i.gi_frame.f_locals
{'base': 100500, 'res': 100502}
>>> i.send(-1)
201001
>>> i.gi_frame.f_locals
{'base': 100500, 'res': 201001}
>>> i.send(-201001 - 100500)
Traceback (most recent call last):
File "<python-input-177>", line 1, in <module>
i.send(-201001 - 100500)
~~~~~~^^^^^^^^^^^^^^^^^^
StopIteration
>>>
Поскольку генератор это всё ещё функция, он всё ещё возвращает некоторое значение по return. Это возвращаемое значение передаётся в качестве параметра первого исключения StopIteration, возникающего по окончании итератора:
>>> def calc(n):
... s = 0
... while n := n // 2:
... s += n
... yield n
... return s
...
>>> list(calc(4))
[2, 1]
>>> list(calc(129))
[64, 32, 16, 8, 4, 2, 1]
>>> e = calc(9)
>>> next(e)
4
>>> next(e)
2
>>> next(e)
1
>>> next(e)
Traceback (most recent call last):
File "<python-input-120>", line 1, in <module>
next(e)
~~~~^^^
StopIteration: 7
>>> next(e)
Traceback (most recent call last):
File "<python-input-6>", line 1, in <module>
next(e)
~~~~^^^
StopIteration
>>>
И данное значение можно отловить с помощью yield from:
>>> def degrees_sum_iter(n):
... sum = yield from calc(n)
... yield f"{sum=}"
... return "HAHA"
...
>>> i = degrees_sum_iter(9)
>>> next(i)
4
>>> next(i)
2
>>> next(i)
1
>>> next(i)
'sum=7'
>>> next(i)
Traceback (most recent call last):
File "<python-input-13>", line 1, in <module>
next(i)
~~~~^^^
StopIteration: HAHA
>>>
Модуль itertools
Один из самых ёмких модулей с разными итераторами и генераторами — itertools. Большинство из них в качестве параметров могут сами принимать не просто последовательности, а итераторы, позволяя делать итераторы почти любой вложенности.
Рассмотрим несколько отдельных классов итераторов:
- Бесконечные последовательности:
- count — итератор-счётчик с указанием стартовой позиции и шага (по умолчанию 0 и 1 соответственно)
- cycle — итератор, получающий некоторый итерируемый объект (не обязательно конечный), и бесконечно зацикливающий его
- repeat — итератор, повторяющий объект указанное (или бесконечное) число раз:
>>> import itertools as itl
>>> i1, i2 = itl.count(), itl.count(30, -3)
>>> for i in range(5):
... print(next(i1), next(i2))
...
0 30
1 27
2 24
3 21
4 18
>>>
>>> i1, i2 = itl.cycle("QWE"), itl.cycle(itl.count(2))
>>> for i in range(5):
... print(next(i1), next(i2))
...
Q 2
W 3
E 4
Q 5
W 6
>>> i1, i2 = itl.repeat(10, 3), itl.repeat(20)
>>> for i in range(5):
... print(next(i1, None), next(i2, None))
...
10 20
10 20
10 20
None 20
None 20
>>>
- Потоковая обработка последовательностей:
- accumulate — Последовательное действие над множествами полученных объектов
- chain/chain.from_iterable — итератор-объединение итерируемых объектов / итерируемого объекта с итерируемыми объектами
- compress, dropwhile, takewhile — итераторы-фильтры: по маске / сброс до условия / выбор до условия
- filterfalse, zip_longest, starmap — Расширения над встроенные итераторами: filter по False / zip по самому длинному итератору с добавлением заполнителя для отсутствующих элементов / map с распаковкой параметров
- pairwise, batched — итератор, склеивающий элементы: во все последовательные пары / в непересекающиеся блоки размера n
>>> i1 = itl.accumulate(itl.count())
>>> i2 = itl.accumulate(itl.count(), lambda x, y: f"{x}QQ{y}")
>>> for i in range(5):
... print(next(i1), next(i2))
...
0 0
1 0QQ1
3 0QQ1QQ2
6 0QQ1QQ2QQ3
10 0QQ1QQ2QQ3QQ4
>>> i1, i2 = itl.chain('ABC', 'DEF'), itl.chain.from_iterable(['ABC', 'DEF'])
>>> list(i1), list(i2)
(['A', 'B', 'C', 'D', 'E', 'F'], ['A', 'B', 'C', 'D', 'E', 'F'])
>>> i1, i2, i3 = itl.compress('ABCDEF', [1,0,1,0,1,1]), itl.dropwhile(lambda x: x<5, [1,4,6,3,8]), itl.takewhile(lambda x: x<5, [1,4,6,3,8])
>>> list(i1), list(i2), list(i3)
(['A', 'C', 'E', 'F'], [6, 3, 8], [1, 4])
>>> i1, i2, i3 = itl.filterfalse(lambda x: x<5, [1,4,6,3,8]), itl.zip_longest('ABCD', 'xy', fillvalue='-'), itl.starmap(pow, [(2,5), (3,2), (10,3)])
>>> list(i1), list(i2), list(i3)
([6, 8], [('A', 'x'), ('B', 'y'), ('C', '-'), ('D', '-')], [32, 9, 1000])
>>> i1, i2 = itl.pairwise('QWERTY'), itl.batched("QWERTYU", 3)
>>> list(i1), list(i2)
([('Q', 'W'), ('W', 'E'), ('E', 'R'), ('R', 'T'), ('T', 'Y')],
[('Q', 'W', 'E'), ('R', 'T', 'Y'), ('U',)])
>>>
- Обработка с хранением промежуточных последовательностей:
- islice — итератор по секции от итерируемого объекта (со строго положительным движением)
- tee — копирование итератора
>>> i = itl.islice(itl.count(), 10, 24, 3)
>>> list(i)
[10, 13, 16, 19, 22]
>>> i1, i2 = itl.tee(itl.chain('ABC', 'DEF'), 2)
>>> list(i1), list(i2)
(['A', 'B', 'C', 'D', 'E', 'F'], ['A', 'B', 'C', 'D', 'E', 'F'])
>>>
- Комбинаторика:
- product — декартово произведение элементов
- permutations — перестановки элементов итерируемого объекта
- combinations — сочетания элементов итерируемого объекта
- combinations_with_replacement — сочетания с повторениями
>>> print( *itl.product( "ACB", [1, 2, 3, 4], ([], ()) ), sep = '\n' )
('A', 1, [])
('A', 1, ())
('A', 2, [])
('A', 2, ())
('A', 3, [])
('A', 3, ())
('A', 4, [])
('A', 4, ())
('C', 1, [])
('C', 1, ())
('C', 2, [])
('C', 2, ())
('C', 3, [])
('C', 3, ())
('C', 4, [])
('C', 4, ())
('B', 1, [])
('B', 1, ())
('B', 2, [])
('B', 2, ())
('B', 3, [])
('B', 3, ())
('B', 4, [])
('B', 4, ())
>>> print(*itl.permutations('qwer', 3), sep = '\n')
('q', 'w', 'e')
('q', 'w', 'r')
('q', 'e', 'w')
('q', 'e', 'r')
('q', 'r', 'w')
('q', 'r', 'e')
('w', 'q', 'e')
('w', 'q', 'r')
('w', 'e', 'q')
('w', 'e', 'r')
('w', 'r', 'q')
('w', 'r', 'e')
('e', 'q', 'w')
('e', 'q', 'r')
('e', 'w', 'q')
('e', 'w', 'r')
('e', 'r', 'q')
('e', 'r', 'w')
('r', 'q', 'w')
('r', 'q', 'e')
('r', 'w', 'q')
('r', 'w', 'e')
('r', 'e', 'q')
('r', 'e', 'w')
>>> print(*itl.combinations('qwer', 3), sep = '\n')
('q', 'w', 'e')
('q', 'w', 'r')
('q', 'e', 'r')
('w', 'e', 'r')
>>> print(*itl.combinations_with_replacement('qwer', 3), sep = '\n')
('q', 'q', 'q')
('q', 'q', 'w')
('q', 'q', 'e')
('q', 'q', 'r')
('q', 'w', 'w')
('q', 'w', 'e')
('q', 'w', 'r')
('q', 'e', 'e')
('q', 'e', 'r')
('q', 'r', 'r')
('w', 'w', 'w')
('w', 'w', 'e')
('w', 'w', 'r')
('w', 'e', 'e')
('w', 'e', 'r')
('w', 'r', 'r')
('e', 'e', 'e')
('e', 'e', 'r')
('e', 'r', 'r')
('r', 'r', 'r')
>>>