Итераторы

Итераторы вокруг нас

Вычислимые последовательности, например, range().

Протокол итерируемой последовательности:

next(seq) (seq.__next__())
Исключение StopIteration по исчерпании

Собственно итераторы:

enumerate(), reversed()
zip(), map(), filter()…

Как сделать итератор:

iter(итерируемый_объект): У объекта есть метод .__iter__()
или iter(индексируемый_объект): У объекта есть метод .__getitem__(int) (индексация пойдёт с нуля)
- Вместо StopIteration используется IndexError
или iter(функция, стоп-значение) — возвращает результат функции, пока он не равен стоп-значению
```
   1 >>> import random
   2 >>> d = iter(lambda: random.randrange(10), 7)
   3 >>> list(d)
   4 [3, 1, 9, 6, 4, 5, 3, 9, 9, 2, 4, 2, 0, 0, 0, 3, 4, 1]
   5 
```
- ⇒ Здравствуй, частично рекурсивная функция!

Использование итераторов в протоколах:

Распаковка (любое множественное связывание и *-ловушки в нём)
Работа цикла for:
1. создание итератора
2. next()
3. обработка StopIteration

Генераторы

Как задать самому?

Например, циклической сборкой в круглых скобках (а иногда и без)

   1 >>> a = (i * 2 + 1 for i in range(9) if i % 5)
   2 >>> a
   3 <generator object <genexpr> at 0x7fb15d029d60>
   4 >>> list(a)
   5 [3, 5, 7, 9, 13, 15, 17]
   6 >>> list(a)
   7 []
   8 >>> a = (i * 2 + 1 for i in range(9) if i % 5)
   9 >>> next(a)
  10 3
  11 >>> next(a)
  12 5
  13 >>> next(a)
  14 7
  15 >>> next(a)
  16 9
  17 >>> next(a)
  18 13
  19 >>> next(a)
  20 15
  21 >>> next(a)
  22 17
  23 >>> next(a)
  24 Traceback (most recent call last):
  25   File "<stdin>", line 1, in <module>
  26 StopIteration
  27 >>> a = (i * 2 + 1 for i in range(9) if i % 5)
  28 >>> for i in a:
  29 ...     print(i, end=": ")
  30 ... print()
  31 3: 5: 7: 9: 13: 15: 17:
  32

Генератор-функция

Наличие yield в теле функции, ⇒ она вернёт генератор, а уж генератор yield-ит результаты

Пример работы

   1 >>> def seq(a):
   2 ...     for i in range(a):
   3 ...         if i % 5:
   4 ...             yield i * 2 + 1
   5 >>> seq
   6 <function seq at 0x7fb156a974c0>
   7 >>> seq(9)
   8 <generator object seq at 0x7fb156f12f20>
   9 >>> s = seq(9)
  10 >>> list(s)
  11 [3, 5, 7, 9, 13, 15, 17]
  12 >>> list(s)
  13 []
  14 >>> for i in seq(9):
  15 ...     print(i, end=": ")
  16 ... print()
  17 3: 5: 7: 9: 13: 15: 17:
  18

Передача потока управления в контекст генератора (next()) и обратно (yield значение)
- Пример на PythonTutor
- rеturn — закрытие итератора (в т. ч. неявный return None в конце)
  - ⇒ Время жизни пространства имён генератора: от создания до return
```
   1 >>> def genf(l):
   2 ...     for i in range(l):
   3 ...         yield i % 5
   4 >>> gen = genf(42)
   5 >>> gen.gi_frame.f_locals
   6 {'l': 42}
   7 >>> next(gen)
   8 0
   9 >>> gen.gi_frame.f_locals
  10 {'l': 5, 'i': 0}
  11 
```
- локальное пространство имён ∃ между yield-ами
Генератор — «одноразовая» последовательность

yield from — атомарный вызов вложенного итератора

   1 >>> def superseq(b):
   2 ...     yield 100500
   3 ...     for i in range(b):
   4 ...         yield from range(b)... 
   5     yield -1
   6 >>> list(superseq(4))
   7 [100500, 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3, -1]
   8

ИРЛ: итераторы — это вычислимые последовательности, в т. ч. бесконечные

Параметрические генераторы

В генератор можно затолкать значение на каждом обороте (оно прочтётся yield-ом).

   1 >>> def biased(init):
   2 ...     bias = yield init
   3 ...     while bias:
   4 ...         init += bias*2+1
   5 ...         bias = yield init
   6 ...
   7 >>> g = biased(10)
   8 >>> next(g) # или, что то же самое, g.send(None)
   9 10
  10 >>> g.send(5)
  11 21
  12 >>> g.send(5)
  13 32
  14 >>> g.send(-1)
  15 31
  16 >>> g.send(100500)
  17 201032
  18 >>> g.send(0)
  19 Traceback (most recent call last):
  20   File "<stdin>", line 1, in <module>
  21 StopIteration

(если не до конца понятно, можно на том же PythonTutor попробовать)
Протокол:
1. Первый вызов — только .send(None) (ещё ничего не передали),
  - это то же самое, что и next(итератор)
2. Остальные — .send(что угодно)

return из итератора и yield from:

return из итератора может иметь параметр — это параметр исключения StopIteration:

   1 >>> def calc(n):
   2 ...     s = 0
   3 ...     while (n := n // 2):
   4 ...         s += n
   5 ...         yield n
   6 ...     return s
   7 >>> r = calc(9)
   8 >>> next(r)
   9 4
  10 >>> next(r)
  11 2
  12 >>> next(r)
  13 1
  14 >>> r.gi_frame.f_locals
  15 {'n': 1, 's': 7}
  16 >>> next(r)
  17 Traceback (most recent call last):
  18   File "<stdin>", line 1, in <module>
  19 StopIteration: 7

Это значение считается возвращаемым конструкцией yield from:
```
   1 >>> def runner(n):
   2 ...     result = yield from calc(n)... 
   3     yield result
   4 >>> list(runner(9))
   5 [4, 2, 1, 7]
   6 
```

Зачем это может быть нужно??

Итератор — сопрограмма с однократным вводом
Параметрический итератор — сопрограмма с произвольным вводом!
- ⇒ Модель асинхронного взаимодействия: диспетчер и сопрограммы-обработчики

Itertools (сколько успеем)

Обработка вычислимых последовательностей и функциональное программирование

Обзор itertools:

Бесконечные последовательности
Потоковая обработка последовательностей:
- accumulate, chain/chain.from_iterable, compress, dropwhile, filterfalse, starmap, takewhile, zip_longest
- pairwise, batched
Обработка с хранением промежуточных последовательностей
- Да, чудес на свете не бывает ☹
- groupby, islice, tee
Комбинаторика (

Частичное вычисление (в т. ч. бесконечных последовательностей)

Кстати, functools.partial()

Д/З

Прочитать
- Про итераторы и генераторы в учебнике
- Про итераторы и генераторы в справочнике
- Про itertools

TODO непараметрический итератор без особых itertools
EJudge: VirtualTurtle 'Примитивная черепашка'

Написать параметрическую генератор-функцию turtle(coord, direction), описывающую движение «черепахи» по координатной плоскости. coord — это кортеж из двух целочисленных начальных координат, direction описывает первоначальное направление (0 — восток, 1 — север, 2 — запад, 3 — юг). Координаты увеличиваются на северо-восток. Генератор принимает три команды — "f" (переход на 1 шаг вперёд), "l" (поворот против часовой стрелки на 90°) и "r" (поворот по часовой стрелке на 90°) и возвращает текущие координаты черепахи.
Input:
```
   1 robo = turtle((0, 0), 0)
   2 start = next(robo)
   3 for c in "flfrffrffr":
   4     print(*robo.send(c))
```
Output:
```
1 0
1 0
1 1
1 1
2 1
3 1
3 1
3 0
3 -1
3 -1
```
EJudge: SeeSaw 'Чёт-нечет'

Написать генератор-функцию seesaw(sequence), которой на вход передаётся итерируемая целочисленная последовательность, а конструируемый ею генератор возвращает поочерёдно то чётный, то нечётный элемент последовательности в порядке следования. Если элементы одного типа заканчиваются, возвращаются только элементы другого.
Input:
```
print(*seesaw(i//3 for i in range(1, 27, 2)))
```
Output:
```
0 1 2 1 4 3 6 3 8 5 5 7 7
```
EJudge: RaceTesting 'Гоночные испытания'
Протокол испытаний самодвижущегося экипажа состоит из карты, расписания отчётности и отчёта о времени.
- Карта — это последовательность положительных чисел — расстояний между остановками
- Расписание отчётности — это (небольшая) последовательность натуральных чисел, в которой сказано, сколько остановок сделать перед тем, как отослать следующий отчёт (1 — отчитаться на следующей же остановке); когда последовательность заканчивается, её следует начать заново
- Отчёт о времени — результат испытаний: время, затраченное на то, чтобы доехать от предыдущей отчётной остановки до следующей
Испытания могут проходить непрерывно, а могут и поэтапно, поэтому отчёт может выдать и гораздо больше, и меньше информации, чем предусмотрено картой и расписанием. Написать генератор-функцию speed(path, stops, times), параметры которой — (возможно, слишком большая для хранения) карта, расписание и (возможно, бесконечный) отчёт, а возвращать она должна итератор, вычисляющий среднюю скорость, которую самодвижущийся экипаж показал на отчётных участках пути.
Input:
```
   1 print(*list(speed([2, 3, 4] * 11, [3, 4, 5], [1, 2, 4, 8] * 3)))
```
Output:
```
9.0 5.5 4.0 1.125 11.0 8.0 2.25 1.375 7.0
```

LecturesCMC/PythonIntro2024/07_Iterators (последним исправлял пользователь FrBrGeorge 2024-10-21 12:35:57)