Итераторы

Когда вы говорите "for i in container:", в Python происходит не магия, а некий набор действий. Ясно, что идея конструкции такая, что у вас есть контейнер с последовательно идущими данными, а по ним бежит что-то вроде курсора, или, еще говорят, итератор. Что именно там происходит?

Чтобы объект container можно было использовать в конструкции "for i in container", от него требуется, чтоб он имел метод iter(), возвращающий некий объект-итератор:

   1 >>> class MyContainer:
   2 ...    __iter__(self):
   3 ...        iterator=MyIterator()
   4 ...        return iterator
   5 ...
   6 >>> container=MyContainer()

От этого объекта - iterator - также требуется наличие у него 2 методов: next() и iter(). Зачем нужен первый - станет ясно сразу, про второй - попозже, это наворот.

   1 class MyIterator:
   2     next(self):
   3         if <условие>:
   4             return something
   5         else:
   6             raise StopIteration
   7 
   8     __iter__(self):
   9         return self

Работа цикла "for i in container: print i;" эквивалентна следующей программе:

   1 iterator=container.__iter__()
   2     while True:
   3         try:
   4             i=iterator.next()
   5             print i
   6         except StopIteration:
   7             break

То есть сначала вызов метода iter() контейнера создает итератор, а затем к нему постоянно применяется метод next(), который что-то возвращает в переменную i, пока итератор не истощится, а в таком случае он должен выбросить исключение StopIteration, которое будет отловлено и остановит исполнение цикла.

Пример программы, создающей контейнер и итератор:

   1 class MyIterator(object):
   2     def __init__(self, value):
   3         self.value=value
   4     def next(self):
   5         if self.value>0:
   6             self.value-=1
   7             return self.value
   8         else:
   9             raise StopIteration
  10     def __iter__(self):
  11         return self
  12 
  13 class MyContainer(object):
  14     def __init__(self):
  15         self.a=10
  16     def __iter__(self):
  17         return MyIterator(self.a)

   1 >>> container=MyContainer()
   2 >>> for i in container:
   3 ...    print i
   4 ...
   5 
   6 9
   7 8
   8 7
   9 6
  10 5
  11 4
  12 3
  13 2
  14 1
  15 0    
  16 

Контейнеры-итераторы

У итераторов есть метод iter(), который просто возвращает сам итератор. В примере выше это была просто формальность. Реально это нужно, чтобы можно было сделать объект-контейнер, который был бы сам себе и итератором:

   1 class TenLittleNiggers(object):
   2         def __init__(self):
   3                 self.rhyme=[]
   4                 self.rhyme.append("""Ten little nigger boys went out to dine;
   5 One choked his little self, and then there were nine.""")
   6                 self.rhyme.append("""Nine little nigger boys sat up very late;
   7 One overslept himself, and then there were eight.""")
   8                 self.rhyme.append("""Eight little nigger boys travelling in Devon;
   9 One said he'd stay there, and then there were seven.""")
  10                 self.rhyme.append("""Seven little nigger boys chopping up sticks;
  11 One chopped himself in half, and then there were six.""")
  12                 self.rhyme.append("""Six little nigger boys playing with a hive;
  13 A bumble-bee stung one, and then there were five.""")
  14                 self.rhyme.append("""Five little nigger boys going in for law;
  15 One got in chancery, and then there were four.""")
  16                 self.rhyme.append("""Four little nigger boys going out to sea;
  17 A red herring swallowed one, and then there were three.""")
  18                 self.rhyme.append("""Three little nigger boys walking in the Zoo;
  19 A big bear hugged one, and then there were two.""")
  20                 self.rhyme.append("""Two little nigger boys sitting in the sun; One got frizzled up, and then there was one.""")
  21                 self.rhyme.append("""One little nigger boy living all alone;
  22 He got married, and then there were none.""")
  23         def __iter__(self):
  24                 return self
  25         def next(self):
  26                 try:
  27                         return self.rhyme.pop(0)
  28                 except:
  29                         raise StopIteration

   1 >>> niggers=TenLittleNiggers()
   2 >>> for i in niggers:
   3 ...     print i
   4 ...
   5         
   6 Ten little nigger boys went out to dine;
   7 One choked his little self, and then there were nine.
   8 Nine little nigger boys sat up very late;
   9 One overslept himself, and then there were eight.
  10 Eight little nigger boys travelling in Devon;
  11 One said he'd stay there, and then there were seven.
  12 Seven little nigger boys chopping up sticks;
  13 One chopped himself in half, and then there were six.
  14 Six little nigger boys playing with a hive;
  15 A bumble-bee stung one, and then there were five.
  16 Five little nigger boys going in for law;
  17 One got in chancery, and then there were four.
  18 Four little nigger boys going out to sea;
  19 A red herring swallowed one, and then there were three.
  20 Three little nigger boys walking in the Zoo;
  21 A big bear hugged one, and then there were two.
  22 Two little nigger boys sitting in the sun; One got frizzled up, and then there was one.
  23 One little nigger boy living all alone;
  24 He got married, and then there were none.
  25 >>> print niggers.next()
  26 
  27 Traceback (most recent call last):
  28   File "<pyshell#92>", line 1, in <module>
  29     print niggers.next()
  30   File "<pyshell#83>", line 29, in next
  31     raise StopIteration
  32 StopIteration

Тут гибридный объект niggers сначала возвращает сам себя при вызове его iter() из "for i in niggers:", а потом по нему же делаются проходы последовательными вызовами next(). У такого гибрида есть побочный эффект: он одноразовый. То есть после исполнения одного for по нему, повторно вызвать его уже будет невозможно (ну точнее, он выбросит StopIteration Exception).

Функция iter()

Есть такая встроенная функция iter(), которая в основном непонятно зачем нужна. Она может быть в 2 формах: В основной форме ей подается объект-контейнер с методом iter(), а она возвращает итератор. Что более интересно, у iter() есть еще одна форма: ей можно подать callable-объект (к примеру, функцию) первым аргументом, а вторым - т.н. метку. При этом iter() создаст итератор, который, при вызове его next(), будет исполнять наш callable-объект без аргументов, но если callable вернет значение, равное метке, выбросит StopIteration:

   1 file=open("myfile.txt")
   2     for line in iter(file.readline, "STOP"):
   3         process_line(line)

Генераторы

В Python можно делать функции, которые могут остановиться при выполнении, передать управление вызвавшей их программе, которая затем может попросить эту прерванную функцию продолжить работу с того же места. Такие функции называются генераторными функциями (generator functions) и вместо выражения return в точке выхода содержат выражение yield:

   1 >>> def MyGeneratorFunction(a=0):
   2 ...    a=a*a
   3 ...    yield a
   4 ...    a=a*a
   5 ...    yield a

Кроме того, при вызове такой функции выдается не значение, а объект - итератор (в данном случае называемый генератором), последовательные вызовы метода next() которого и будут заставлять генераторную функцию продолжить исполнение до следующего yield:

   1 >>> Generator=MyGeneratorFunction(2)
   2 >>> Generator.next()
   3 4
   4 >>> Generator.next()
   5 16
   6 >>> Generator.next()
   7 Traceback (most recent call last):
   8   File "<pyshell#42>", line 1, in <module>
   9     Generator.next()
  10 StopIteration

Еще у итератора-генератора есть забавный метод send(), который позволяет ему не только выдавать значения основной программе, но и получать их:

   1 >>> def MyGenFunc(value):
   2 ...     yield value
   3 ...     value-=1
   4 ...     yield value
   5 ...     value = (yield value)
   6 ...     yield value
   7 ...
   8 >>> generator=MyGenFunc(5)
   9 >>> generator.next()
  10 5
  11 >>> generator.next()
  12 4
  13 >>> generator.next()
  14 4
  15 >>> generator.send(10)
  16 10
  17 

Здесь метод send() возобновляет исполнение программы после третьего yield - того, что в строке value = (yield value). В этой строке сначала исполняется yield value, и только на следующей итерации (yield value) заменяется на переданное методом send() значение 10, соответственно value становится равна 10 и выдается следующим yield. Кстати, если вместо send() скомандовать next(), (yield value) заменится на None.

Убийца мозга - алгоритм перечисления всех простых чисел

Вот эта вот рекурсивная и углубляющаяся жуть перечисляет все простые числа от одного и до исчерпания динамической памяти.

   1 def sieve(prime, iter):
   2     for i in iter:
   3         if i%prime!=0:
   4             yield i
   5 
   6 def primes():
   7     iter=itertools.count(2)
   8     while True:
   9         prime=iter.next()
  10         yield prime
  11         iter=sieve(prime, iter)

   1 >>> for prime in primes():
   2 ...    print prime

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

Также Python поддерживает "ленивую" форму генераторов - generator expressions - что-то наподобие list comprehensions. Подразумевается, что выражение слева от for будет вычисляться и выдаваться yield:

   1 >>> sum(i*i for i in range(10))                 # sum of squares
   2 285
   3 

Модуль itertools

Это модуль, который содержит итераторы (например, itertools.count(), который перечисляет натуральные числа отсюда и до горизонта), а также функцию tee(), которая позволяет сделать копию итератора где-то посреди процесса извлечения им элементов.