Итераторы

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

Вычислимые последовательности.

• enumerate(), reversed()

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

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

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

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

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

• У объекта есть метод .__iter__()

• У объекта есть метод .__getitem__() (индексация пойдёт с нуля)

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

• iter(функция, стоп-значение) — возвращает результат функции, пока он не равен стоп-значению

⇒ iter() от всего подряд

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

• Распаковка (любое множественное связывание и *-ловушки в нём)

• Работа цикла 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 
    

  • return в генераторе = StopIteration

  • Генератор — «одноразовая» последовательность

  • yield from

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

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

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

В генератор можно затолкать значение на каждом обороте (оно прочтётся 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

• Протокол:

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

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

  1. Остальные — .send(что угодно)

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

• Итератор — сопрограмма с однократным вводом
• Параметрический итератор — сопрограмма с произвольным вводом!

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

itertools

• Обработка вычислимых последовательностей
• Функциональное программирование
• Обзор
  • Вычислимые подпоследовательности
  • Бесконечные последовательности и частичные вычисления
  • Модификация последовательностей
  • Комбинаторика

Особенности tee() и islice() и других воспроизводящих итераторов — чудес на свете не бывает

Д/З

0. Прочитать

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

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

   • Про itertools

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

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

   Input:

   for i, l in enumerate(LookSay()):
       print(f"{i}: {l}")
       if i > 10:
           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: ChainSlice 'Режем лазанью'

   Написать Генератор-функцию chainslice(begin, end, seq0, seq1, …), которая принимает не менее трёх параметров: два целых числа и не менее одной последовательности. Рассмотрим последовательность seq, образованную всеми элементами seq0, затем — всеми элементами seq1, и т. д. Вернуть эта функция должна итератор, пробегающий элементы этой последовательности seq с №begin до №end-1 включительно.

   Input:

   print(*(chainslice(17, 33, range(7),  range(8),  range(6),  range(9),  range(5))))

   Output:

   2 3 4 5 0 1 2 3 4 5 6 7 8 0 1 2

3. EJudge: VarRandom 'Случайные диапазоны'

   Написать генератор-функцию randomes(seq), которой передаётся на вход последовательность пар seq — диапазоны для функции random.randint(). На выходе должен быть генератор, который бесконечно возвращает случайные числа по одному из каждого диапазона. Сами пары тоже могут оказаться итераторами. Пример вывода, разумеется, не эталонный.

   Input:

      1 for e in zip(randomes([(1, 3), (100, 200), (-10, 10)]), range(7)):
      2     print(e[0])
   

   Output:

   1
   123
   -3
   3
   177
   7
   2

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

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

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

   Input:

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

   Output:

   aabqrszt