Итераторы

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

Вычислимые последовательности, например, 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: CommFunction 'Коммутативная функция'

   Написать функцию checkcomm(fun, *args), которой передаётся не менее одного параметра. Параметр fun — это некоторая n-местная функция, где n — это длина args. checkcomm() должна возвращать True, если функция fun() на заданных параметрах коммутативна, то есть в каком бы порядке они ей не передавались, результат одинаков, и False в противном случае. Гарантируется, что во всех случаях функция вычислима, а возвращаемые ею значения — сравнимы на "==".

   Input:

      1 print(checkcomm(max, 1, 9, 2, 7, 3, 6))
   

   Output:

   True

2. EJudge: SeqJoin 'Слияние'

   Написать генератор-функцию joinseq(seq0, seq1, …), принимающую на вход произвольное количество (возможно, бесконечных) последовательностей. Порождаемый ею генератор должен всякий раз возвращать наименьший из начальных элементов этих последовательностей. Если таких несколько, используется самый первый. Если последовательность закончилась, она больше не учитывается. Итератор завершается, когда все последовательности иссякли.

   • Условие: использовать обработку исключений в этой задаче нельзя.

   Input:

      1 print("".join(joinseq("abs", "qr", "azt")))
   

   Output:

   aabqrszt

3. EJudge: NonPrime 'непростые числа'

   Написать генетатор-функцию nonprime(n=0), которая будет выдавать последовательность непростых чисел (единица и составные числа), превосходящих целое положительное n (по умолчанию — 0).

   Input:

      1 print(*dict(zip(nonprime(16), range(20))))
   

   Output:

   18 20 21 22 24 25 26 27 28 30 32 33 34 35 36 38 39 40 42 44

4. TODO обязательная задача для магистров