Итераторы

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

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

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

• enumerate(), reversed()

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

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

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

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

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

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

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

  • Вместо 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 
  

⇒ 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 
    

• Передача потока управления в контекст генератора (next()) и обратно (yield значение)

  • Пример на PythonTutor

  • Время жизни пространства имён генератора: от создания до StopIteration

       1 >>> def genf(l):
       2 ...     for i in range(l):
       3 ...         yield i
       4 >>> gen = genf(42)
       5 >>> gen.gi_frame.f_locals
       6 {'l': 42}
       7 
    

  • 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

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

• Протокол:

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

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

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

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

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

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

itertools

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

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

Д/З

0. Прочитать

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

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

   • Про itertools

1. EJudge: NoMoreSeq 'Повторитель'

   Написать генератор-функцию nomore(sequence), которой на вход подаётся индексируемая последовательность однотипных эелментов, а порождаемый ею генератор возвращает в порядке следования сначала все элементы этой последовательности, не превосходящие sequence[0], затем — все элементы, не превосходящие sequence[1] и так до последнего.

   Input:

   print(*nomore([n % 13 for n in range(5,23,3)]))

   Output:

   5 1 4 5 8 1 4 7 5 8 11 1 4 7 1 1 4 5 1 4 7

2. 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

3. 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

4. EJudge: ChudnPi 'Много знаков Пи'

   Написать генератор-функцию PiGen(). Возвращаемый ею генератор вычисляет Decimal представление числа Пи c 9999 знаками после запятой (всего 10000☺) по алгоритму Чудновских (согласно английской Википедии Чудновских там было боле одного):

   • $$ \frac{(640320)^{3/2}}{12\pi}=\frac{426880\sqrt{10005}}{\pi} = \sum_{k=0}^{\infty} \frac{(6k)! (545140134k + 13591409)}{(3k)!(k!)^3 (-262537412640768000)^{k}} $$

   • На каждой итерации PiGen() возвращает значение для очередной частичной суммы.

   Input:

      1 for i, p in enumerate(PiGen()):
      2     if i>120:
      3         break
      4 print(str(p)[1400:1470])
   

   Output:

   7967823547816360093417216412199245863150302861829745557067498385054945