Итераторы

Вводные слова

Прежде, чем переходить к собственно теме итераторов, я хочу дать вам два предупреждения.

Во-первых, всё, что мы делали до сих пор с питоном, было в равной мере применимо почти к любому современному питону. (С единственной оговоркой для print, который в питонах после версии 3 стал обычной функцией и потому требует скобочек. Но даже и print можно писать таким образом, чтобы он работал во всех версиях питона – что я вам неявным образом и советовал). В сегодняшней теме есть много вещей, которые появились в питоне достаточно недавно. Это касается не устройства, а некоторых из стандартных функций, и о том, когда какая функция появилась в питоне, написано на сайте питона в Library reference про каждую из достаточно новых функций. Если вы будете писать программы, которыми пользоваться будете не только вы сами, рассчитывайте с самого начала на то, с какой версией питона вы хотите иметь совместимость, и подглядывайте в Library reference на тему того, что можно использовать.

В этом году мне ещё приходилось встречать где-то питон версии 2.3.

Во-вторых, итераторы в зависимости от того, где вы их применяете, могут играть роль либо достаточно существенной оптимизации программы по тому, сколько она занимает памяти (но не по быстродействию!), а могут помогать вам разделять код на более удобоваримые части и делать его более читаемым / выразительным. Но как и со многими выразительными конструкциями, если с ними перестараться, вы сделаете код совершенно непонятным – что я продемонстрирую простым примером в конце лекции.

Оба предупреждения сводятся к одному: не злоупотребляйте.

Итераторы

Несколько раз до сих пор вы встречались со штуками, которые не являются списками, но если их подставить, например, в цикл for, то они ведут себя как списки. Самый яркий пример – это объекты файла: если по ним ходить циклом for, то мы по очереди читаем строки из файла.

Как это на самом деле устоено?

На самом деле, когда мы говорим for i in container (здесь и далее по-русски мы объект container – и всё, что бы нам ни пришло в голову подставлять на его место – будем называть словом контейнер), происходит строго определённый набор действий: сначала питон вызывает у объекта container метод __iter__ без аргументов и ожидает, что container.__iter__() вернёт ему объект, который мы будем называть iterator (а по-русски, соответственно, итератором). Далее, перед входом в каждую итерацию цикла питон пытается у объекта iterator вызвать метод next без аргументов – и то, что он вернул, кладёт в переменную цикла. Завершается цикл тогда, когда iterator.next() вместо того, чтобы вернуть очередное значение, выбрасывает исключение StopIteration.

Таким устройством обладают все встроенные типы данных, которые можно подсовывать в for. Например, если вы посмотрите на dir([]), dir({}), dir(file) и т.п., то вы обнаружите у этих типов данных метод __iter__.

Мы можем описать и свой класс, объекты которого будут контейнерами (т.е. их можно подставлять в цикл for). Чтобы это получилось, нужно выполнить следующие требования:

• мы заводим класс контейнеров и класс итераторов

• у класса контейнеров есть метод __iter__, который возвращает объект класса итератор

• у объекта класса итератор должен быть метод next

• у объекта класса итератор должен быть метод __iter__, который возвращает self – в некоторых экзотических случаях сам объект итератора может оказаться в роли контейнера, и правильным поведением в этом случае было бы продолжать как ни в чём не бывало.

Полезно при этом, чтобы:

• метод __iter__ в контейнере передавал ссылку на контейнер итератору – при разделении на контейнер и итератор идея состоит в том, что контейнер помнит, какие в нём хранятся элементы, а итератор помнит, на каком месте цикла он сейчас стоит (какой элемент нужно будет возвращать в следующий раз)

• метод next в итераторе наверное, иногда должен выбрасывать исключение StopIteration – чтобы обозначить конец цикла

То есть выглядеть оно должно примерно так:

   1 class MyCollection(object):
   2     def __iter__(self):
   3         ...
   4         return iterator
   5 
   6 class MyIterator(object):
   7     def next(self):
   8         ...
   9         if ...:
  10             return value
  11         else:
  12             raise StopIteration
  13     def __iter__(self):
  14         return self

Приведём маленький пример:

   1 class Counter(object):
   2     """A container of numbers from the given value to 0"""
   3 
   4     def __init__(self, value):
   5         self.value = value
   6     
   7     def __iter__(self):
   8         return CountIterator(self)
   9 
  10 class CountIterator(object):
  11     """Iterator class for Conter"""
  12 
  13     def __init__(self, counter):
  14         self.value = counter.value
  15     
  16     def next(self):
  17         if self.value < 0:
  18             raise StopIteration
  19         else:
  20             result = self.value
  21             self.value -= 1
  22             return result
  23 
  24 >>> counter = Counter(5)
  25 >>> for i in counter:
  26 ...     print("Count: %d" % i)
  27 ...
  28 Count: 5
  29 Count: 4
  30 Count: 3
  31 Count: 2
  32 Count: 1
  33 Count: 0
  34 >>>

Что произошло:

• count = Counter(5) – мы создали объект класса Counter, ничего необычного

• for i in counter – первым делом, у нас за спиной создался итератор, напишем условно: iterator = counter.__iter__() (на самом деле, никакой переменной iterator из питона при этом не видно). Это символизирует начало цикла.

• for i in counter – попытка совершить первый шаг цикла: i = iterator.next(); получилось i = 5

• print("Count: %d" % i)

• for i in counter – попытка совершить второй шаг цикла: i = iterator.next(); получилось i = 4

• ...

• for i in counter – попытка совершить шестой шаг цикла: i = iterator.next(); получилось i = 0

• print("Count: %d" % i)

• for i in counter – попытка совершить седьмой шаг цикла: i = iterator.next(); вызов next выбросил исключение StopIteration, поэтому for решил больше итераций не делать и цикл завершился.

Другими словами, что здесь происходит, можно записать на языке питона. Для этого мы можем перевести цикл for в цикл while:

   1 container = MyContainer()
   2 for loopvar in container:
   3     something(loopvar)

   1 container = MyContainer()
   2 iterator = container.__iter__()
   3 while True:
   4     try:
   5         loopvar = iterator.next()
   6     except StopIteration:
   7         break
   8     something(loopvar)

Эти два куска кода эквивалентны, с точностью до того, что во втором случае возникает лишняя переменная iterator.

Замечение утиного толка.

Такие контейнеры можно обходить циклом for, передавать конструкторам списков, кортежей, множеств, словарей (правда у словарей есть свои дополнительные ограничения, читайте хелпы), и их можно распаковывать через tuple unpacking. Так как это большая куча операций и весьма много (в том числе и встроенных в питон) функций реалезованы через них, то получается, что мы можем наши контейнеры использовать довольно много где так же как списки.

   1 >>> a, b, c = Counter(2)
   2 >>> a, b, c
   3 (2, 1, 0)

Генераторы

Всё, сказанное выше, говорит о том, что в питоне возможно – если хорошо постараться – сделать свой объект, который будет вести себя как список. Но трудно.

Поэтому для создания итераторов в питоне есть специальные синтаксические конструкции. Первая из них зовётся генераторными функциями.

Генераторная функция описывается так же, как и обычная функция, с двумя отличиями:

• в ней нету return

• в ней есть конструкции yield

Конструкция yield x обозначает следующее: вернуть одно значение (x), остановиться, и подождать, пока нас спросят вернуть что-нибудь ещё.

   1 def abc():
   2     yield 'a'
   3     yield 'b'
   4     yield 'c'
   5 
   6 >>> iterator = abc()
   7 >>> for i in iterator:
   8 ...     print(i)
   9 ...
  10 a
  11 b
  12 c

Мы описали простейшую генераторную функцию abc.

iterator = abc(). Когда мы вызываем генераторную функцию, она ничего не исполняет из того, что в ней описано! Вместо этого, она сразу возвращает итератор.

for i in iterator: print(i). Каждое обращение к iterator.next() заставляет его выполнить кусочек тела генераторной функции от того места, где исполнение остановилось в прошлый раз до очередного yield – и возвращает то значение, которое мы передали в yeild.

Когда исполнение тела генераторной функции дошло до конца, цикл прекращается.

   1 >>> iterator = abc()
   2 >>> iterator.__iter__() is iterator
   3 True
   4 >>> iterator.next()
   5 'a'
   6 >>> iterator.next()
   7 'b'
   8 >>> iterator.next()
   9 'c'
  10 >>> iterator.next()
  11 Traceback (most recent call last):
  12   ...
  13 StopIteration

С точки зрения пользователя итератор подобен списку из тех значений, которые он передаёт в yield. Наш итератор abc подобен списку ['a', 'b', 'c'].

Встроенные итераторы в питоне

Кроме создания итераторов руками и генераторных функций, в питоне есть ещё множество способов получать итераторы.

Многие встроенные типы являются итераторами сами по себе: list, tuple, set, frozenset, dict, file.

У dict есть несколько методов, которые возвращают итераторы:

• dict.keys возвращает список ключей словаря (никаких итераторов, обычный список)

• dict.iterkeys возвращает итератор, который перебирает ключи словаря

• dict.values возвращает список значений в словаре (и значения могут повторяться)

• dict.itervalues возвращает итератор, который перебирает значения в словаре

• dict.items возвращает список пар (key, value)

• dict.iteritems возвращает итератор, который проходит по списку пар (key, value)

Мы уже неоднократно упоминали о том, что объекты файлов в питоне являются итераторами. (Хотя не всегда произносили при этом вслух слово итератор).

Мы натыкались на функции enumerate и reversed, которые на самом деле возвращают итераторы, а не создают новые списки.

В пару к range в питоне есть функция xrange, которая возвращает итератор, перебирающий числа в диапазоне, а не создаёт никаких списков.

• Предупреждение о совместимости: если вы хотите, чтобы ваши программы

  работали и в python2 и в python3, пользуйтесь dict.keys, dict.items, dict.values и range, а не dict.iterkeys, dict.iteritems, dict.itervalues, xrange. Дело в том, что в третий питон в довольно многих местах, где раньше возвращались списки, стал возвращать итераторы.

Если вы помните, когда я рассказывал про обход дерева директорий os.walk, я как-то очень невнятно объяснял, что эта штука похожа на список троек (root, dirs, files), но списком не является. Это тоже итератор, притом крайне забавный: на каждой следующей итерации он использует те самые объекты root, dirs, files, которые он вернул пользователю. Так как dirs и files – это списки, то их можно менять, и таким образом сразу забраковывать некоторые поддеревья.

Среди многочисленных питонских модулей для работы со всякой всячиной тоже есть множество итераторов. В памяти всплывают модули для работы с архивами (zipfile, tarfile и пр.).

Наконец, в питоне есть отдельный модуль "полезных штук для работы с итераторами": itertools. Приведу из них несколько примеров, чтобы дать понять, о чём оно:

file = itertools.chain(file1, file2, file) – получает на вход сколько-нибудь итераторов и возвращает итератор, который проходит сначала по первому, потом по второму, потом по третьему и так далее. Это эквивалент операции + для списков. (Сама операция + для итераторов не работает). В itertools есть ещё несколько функций, воспроизводящих для итераторов стандартные действия со списками: izip, izip_longest, islice, repeat.

numbers = itertools.count() – возвращает итератор, который перебирает до бесконечности целые числа начиная с 0. Ещё для создания бесконечных итераторов в itertools есть функции cycle и уже упомянутый repeat.

iter1, iter2 = itertools.tee(iter) – получает на вход итератор и возвращает пару независимых друг от друга итераторов, идущих с того же места. Пример:

   1 import itertools
   2 file1, file2 = itertools.tee(open("..."))
   3 for line1 in file1:
   4     for line2 in file2:
   5         print("%s %s" % (line1.rstrip("\n"), line2.rstrip("\n")))

в этом примере мы распечатываем все возможные пары строк из одного файла.

Если бы мы написали:

   1 file = open("...")
   2 for line1 in file:
   3     for line2 in file:
   4         print("%s %s" % (line1.rstrip("\n"), line2.rstrip("\n")))

то мы получили бы все возможные сочетания первой строки со всеми остальными. (Потому, что file уже является итератором, а не контейнером; в другой терминологии: когда мы заново запускаем цикл по файлу, мы не перематываем файл на начало, а продолжаем с того места, где остановились в последний раз).

В данном примере – когда речь идёт об обычном файле, лежашем на диске, (а не, например, о стандартном потоке ввода), и в том месте, где мы хотим распечатать пары строк, мы знаем его имя, сработал бы и такой код:

   1 for line1 in open("..."):
   2     for line2 in open("..."):
   3         print("%s %s" % (line1.rstrip("\n"), line2.rstrip("\n")))

Ещё в itertools есть набор функций для комбинаторики с итераторами, например: iter = itertools.permutations(iter, 3) получает на вход итератор и число, и возвращает итератор, который перебирает все возможные наборы элементов итератора во всех возможных последовательностях. (И снова рядом лежит ещё несколько функций с родственными задачами: combinations и product).

Новые функции в itertools появляются довольно часто, поэтому следите за тем, в какой версии питона возникли те из функций, которыми вы пользуетесь.

Генераторные выражения

Если вы помните предыдущую лекцию и что такое list comprehensions в питоне, то к ним есть маленькое дополнение: если выражение list comprehensions писать не в квадратных скобках, а в круглых, то результирующий список сразу создан не будет, а вместо него выражение вернёт итератор, перебирающий этот список. Эта конструкция называется генераторными выражениями.

Пример: построим список квадратов натуральных чисел и распечатаем первые 10.

   1 >>> import itertools
   2 >>> natural_numbers = itertools.count(1)
   3 >>> squares = (x ** 2 for x in natural_numbers)
   4 >>> print(list(itertools.islice(squares, 10)))
   5 [1, 4, 9, 16, 25, 36, 49, 64, 81, 100]

В случае обычных list comprehensions такой фокус у нас не прошёл бы.

Несколько примеров

Где это возможно я привожу пары примеров: проста

Песенка про бутылки пива

• (Была бы на то моя воля, я бы бутылки пива заменил на что-нибудь ещё)

   1 def rhimes(numbers):
   2     for i in numbers:
   3         yield "%d lines of code to write, %d lines of code" % (i, i)
   4         yield "Think alot, write one line, %d lines of code to write" % (i - 1)
   5 
   6 sequence = itertools.repeat(range(99, 0, -1))
   7 for line in rhimes(sequence):
   8     print(line)

Через списки и не бесконечное:

   1 def rhimes(numbers):
   2     result = []
   3     for i in numbers:
   4         result.append("%d lines of code to write, %d lines of code" % (i, i))
   5         result.append("Think alot, write one line, %d lines of code to write" % (i - 1))
   6 
   7 sequence = range(99, 0, -1)
   8 for line in rhimes(sequence):
   9     print(line)

Разбор csv

Предположим, у нас есть CSV-файл с двумя колонками чисел, и мы хотим сложить эти колонки. (Конечно, можно было бы просто сделать это в каким-нибудь Excel'ем, но мы не ищем лёгких путей!)

   1 def parse_csv(file):
   2     for line in file:
   3         values = [int(word) for word in line.split(',')]
   4         yiled values # each iteration yields a list of items!
   5 
   6 for a, b in parse_csv(open("...")):
   7     print(a + b)

Через списки:

   1 def parse_csv(file):
   2     return [
   3         [int(word) for word in line.split(',')]
   4         for line in file
   5     ]
   6 
   7 for a, b in parse_csv(open("...")):
   8     print(a + b)

Здесь через списки получилось чуть ли не короче: при переводе генераторной функции на списки выбор был между надоевшей уже парой строк {{{result = []}}}, result.append(...) и более весёлой парой list comprehensions.

Бесконечный список простых чисел

Идея:

• первое простое число – 2

• второе простое число – первое из тех, которое не делится на 2

• третье простое число – первое из тех, которое не делится на 2 и второе

• ...

Соответственно, алгоритм:

1. положим под именем ints у нас есть список всех целых чисел больше 2

2. возьмём из них первое – это простое число

3. подменим список ints списком из всех ints, которые не делятся на найденное простое число
4. повторить снова с шага 2.

Для реализации мы выносим отдельно отсеивание чисел, кратных данному, из последовательности в функцию sieve. Дальше строго по алгоритму.

   1 def sieve(n, ints):
   2     """Yield elements of 'ints' that are not multiple of 'n'."""
   3     for i in ints:
   4         if i % n != 0:
   5             yield i
   6 
   7 def primes():
   8     """Yield prime numbers sequentially."""
   9     ints = itertools.count(2)
  10     while True:
  11         prime = ints.next()
  12         yield prime
  13         ints = sieve(prime, ints)
  14 
  15 for prime in primes():
  16     print(prime)