Итераторы

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

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

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

• next(seq) (seq.__next__())

• Исключение StopIteration по исчерпании

• Вариант: next(seq, default) — default при исчерпании (чтобы не пытаться ловить исключение)

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

• enumerate(), reversed()

• zip(), map(), filter()…

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

1. iter(итерируемый_объект): У объекта есть метод .__iter__()

2. или iter(индексируемый_объект): У объекта есть метод .__getitem__(int) (индексация пойдёт с нуля)

   • Вместо StopIteration используется IndexError

3. или 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(i)... 
       5     yield -1
       6 >>> print(*superseq(7))
       7 100500 0 0 1 0 1 2 0 1 2 3 0 1 2 3 4 0 1 2 3 4 5 -1
       8 >>> def supersuperseq(b):
       9 ...     for i in range(b):
      10 ...         yield from superseq(i)>>> 
      11 print(*supersuperseq(5))
      12 100500 -1 100500 -1 100500 0 -1 100500 0 0 1 -1 100500 0 0 1 0 1 2 -1
      13 
    

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

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

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

   1 >>> def stopicot(base):
   2   2     what = yield base
   3   3     while what:
   4   4         what += yield base + what
   5 >>> sto = stopicot(100500)
   6 >>> next(sto) # или, что то же самое, sto.send(None)
   7 100500
   8 >>> sto.send(1)
   9 100501
  10 >>> sto.send(1)
  11 100502
  12 >>> sto.send(-1)
  13 100501
  14 >>> sto.send(-1)
  15 Traceback (most recent call last):
  16   File "<stdin>", line 1, in <module>
  17 StopIteration

• (если не до конца понятно, можно на том же PythonTutor попробовать)

• Протокол:

  0. Первый вызов — только .send(None) (ещё ничего не передали),

     • это то же самое, что и next(итератор)

  1. Остальные — .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 
    

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

• Итератор — сопрограмма с однократным вводом

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

  • .send() / yield — управление сопрограммой

  • Значение yield from — результат работы сопрограммы

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

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

Обзор itertools:

• Бесконечные последовательности count, cycle, repeat

• Потоковая обработка последовательностей:

  • accumulate, chain/chain.from_iterable, compress, dropwhile, filterfalse, starmap, takewhile, zip_longest

  • pairwise, batched

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

  • Да, чудес на свете не бывает ☹

  • groupby, islice, tee

• Комбинаторика (product / permutations, combinations / combinations_with_replacement)

  • Не путать с math.prod / math.comb

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

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

Д/З

0. Прочитать

   • Про итераторы и генераторы в учебнике

   • Про итераторы и генераторы в справочнике

   • Про itertools

1. EJudge: LookSay 'Прочти это вслух'

   Написать генератор-функцию LookSay() цифр последовательности Конвея «Look and Say». Сама последовательность должна быть целочисленной. Описание в Википедии

   Input:

      1 for i, l in enumerate(LookSay()):
      2     print(f"{i}: {l}")
      3     if i > 10:
      4         break
   

   Output:

   0: 1
   1: 1
   2: 1
   3: 2
   4: 1
   5: 1
   6: 2
   7: 1
   8: 1
   9: 1
   10: 1
   11: 1

2. EJudge: ManyFor 'Многоцикл'

   Написать генератор-функцию manyfor(order, *sequences), у которой только один обязательный параметр — последовательность индексов, остальные — произвольные итерируемые последовательности. Функция должна возвращать генератор, который поочерёдно перебирает элементы последовательностей в порядке, заданном order. Если соответствующая значению из order последовательность опустела или это значение не является индексом sequences, генератор заканчивает работу.

   • Последовательности могут тоже быть генераторами, причём и бесконечными в том числе

   Input:

      1 print("".join(manyfor((1, 0, 2) * 16, "ae kha-kha", "Mnsatm", "nrme noob")))
   

   Output:

   Manners maketh man

3. EJudge: IterCalc 'Калькулятератор'

   Написать генератор-функцию itercalc(), которая возвращает параметрический итератор, работающий как примитивный стековый калькулятор. Команды калькулятору посылаются с помощью .send(), возвращаемое значение — None, за исключением команды «?», которая возвращает вершину стека. Другие команды — это либо целое число (оно добавляется на стек), либо одна из операций «+», «-», «*» или «/», которые заменяют два верхних элемента стека на результат применения к ним соответствующей операции (вершина стека — это второй операнд). Деление целочисленное. Если операция невозможна, она не выполняется, и выводится ошибка:

   • Zero division при попытке поделить на 0

   • Insufficient stack, когда нужного элемента на стеке нет

   • Unknown command, если команда не распознана

   Input:

      1 calc = itercalc()
      2 next(calc)
      3 for cmd in "? 3 -2 - what 5 * 2 / ?".split():
      4     if (res := calc.send(cmd)) is not None:
      5         print(res)
   

   Output:

   Insufficient stack
   Unknown command
   12

4. TODO ещё одну на itertools