Наши партнеры

UnixForum






Книги по Linux (с отзывами читателей)

Библиотека сайта rus-linux.net

Python 2.3: рассмотрим itertools

Р.А.Сузи

Язык программирования Python уже достиг версии 2.3. Справиться о современном состоянии можно на сайте http://www.python.org.

Одно из свежих добавлений -- модуль itertools, который включает в себя набор функций для построения итераторов. Но в начале разберемся, что же такое итератор. Не секрет, что итерация, то есть повторение вычислительного процесса -- цикл -- является одним из фундаментальных блоков, из которых строятся императивные программы. В языке Python итерации можно производить с использованием циклов ДЛЯ (for), ПОКА (while), а также в списковых включениях -- новом методе описания списков, появившемся в Python 2.x.

В языке Python итерация часто производится с использованием некоторого параметра, который пробегает все значения из некоторой последовательности или, в более общем случае -- итерабельного (способного к итерации) объекта. Именно так происходит при использовании оператора for или спискового включения. Следующий пример иллюстрирует итерацию по символам строки:

for c in "example":
    print c

Здесь c является параметром цикла.

В следующем примере итерация производится по последовательности целых чисел от 1 до 10. Для порождения такой последовательности в Python имеется специальная встроенная функция range():

s = 0
for i in range(1, 11):
    s = s + i**2
print c

Конечно, с помощью range() использовать большие последовательности неудобно: они занимают много памяти, поэтому в Python имеется функция xrange(), которая в описании цикла for ведет себя также, как и range(), но реального списка не создает.

Аналогично можно рассмотреть методы readlines() и xreadlines() файлового объекта. В первом случае из файла читаются все строки и записываются в память в виде списка строк, а во втором строки читаются из файла по мере необходимости. Следующий пример показывает применение функции xreadlines():

f = open("file.txt")
for l in f.xreadlines():
    print len(l)

Примеры с xrange() и xreadlines() являются примерами функций, которые возвращают объекты-итераторы: специальные объекты, призванные выдавать очередное значение по требованию. В версиях Python 2.1 и ниже такие объекты можно было создавать с помощью описания довольно хитрого класса. Вот простейший пример, в котором класс Fibonacci описывает объекты для получения последовательности чисел Фибоначчи:

class Fibonacci:
  """Прообраз итератора последовательности Фибоначчи"""
  def __init__(self, max):
    self.n, self.a, self.b, self.max = 0, 0, 1, max
  def __getitem__(self, x):
    if self.n < self.max:
      a, self.n, self.a, self.b = self.a, self.n+1, self.b, self.a+self.b
      return a
    else: 
      raise IndexError

# Пример выполнения
for i in Fibonacci(10):
  print i,

Итераторы в Python можно встретить повсюду, где раньше были списки. Например, ключи, значения и пары ключей-значений теперь можно получить в виде итератора:

d = {1: 'a', 2: 'b', 3: 'c'}
for k, v in d.iteritems():
  print k, v

1 a
2 b
3 c

То есть, теперь нет нужды создавать отдельный (подчас огромный) список на основе словаря -- значения без труда в нужный момент (just-in-time, так сказать) выдаст итератор!

Нужно пронумеровать объекты списка или другого итерабельного объекта? Теперь есть встроенная функция enumerate():

for (n, v) in enumerate("example"):
  print n, ":", v

0 : e
1 : x
2 : a
3 : m
4 : p
5 : l
6 : e

В Python 2.2 появился специальный интерфейс для итераторов, благодаря чему итераторы стало возможным описывать единообразно. Тот же пример с использованием стандартного интерфейса:

class Fibonacci:
  """Итератор последовательности Фибоначчи"""
  def __init__(self, max): 
    self.n, self.a, self.b, self.max = 0, 0, 1, max
  def __iter__(self): 
    return self
  def next(self):
    if self.n < self.max:
      a, self.n, self.a, self.b = self.a, self.n+1, self.b, self.a+self.b
      return a
    else: 
      raise StopIteration

Заметьте, что по сравнению с предыдущим примером произошли три изменения. Во-первых, добавился метод __iter__(), который возвращает объект-итератор (в нашем примере -- сам объект). Во вторых, вместо метода __getitem__(), через который цикл for получал значения последовательности, применен метод next(), который является необходимым для объекта-итератора в Python. В-третьих, теперь в качестве сигнала завершения итераций используется исключение StopIteration.

В Python также появилась встроенная функция iter(), которая создает итератор для некоторой последовательности. Пример:

s = [1, 2, 3, 4, 5]
siter = iter(s)
for i in siter:
    print i

Конечно, в данном случае итератор нужен не был, так как оператор for прекрасно работает с последовательностями.

Есть и другая форма функции iter(), которая в качестве первого аргумента принимает функцию без аргументов, а в качестве второго аргумента -- стоповое значение.

В следующем примере происходит ввод и суммирование чисел. Итерации останавливаются при вводе числа 0:

s = 0
for i in iter(input, 0):
    s += i
print s

Кстати, построчное чтение из файла можно теперь записать так:

f = open("file.txt")
for l in iter(f.readline, ""):
    print l  # делаем что-то с очередной строкой файла

Итераторы применяются в нескольких стандартных модулях Python. Например, с помощью finditer() из модуля re легко получить в обычном цикле for все куски строки, соответствующие регулярному выражению:

for i in re.finditer("[0-9]+", "12 3 1 23 fff 1678"): 
   print int(i.group())

Перейдем теперь к рассмотрению функций модуля itertools, который появился в Python 2.3b1.

Функция chain() позволяет сделать итератор, состоящий из нескольких итераторов. Итераторы задаются в виде отдельных аргументов. Пример:

from itertools import chain
it1 = iter([1,2,3])
it2 = iter([8,9,0])
for i in chain(it1, it2):
    print i,

Даст:

1 2 3 8 9 0

Функция repeat() строит итератор, повторяющий некоторый элемент заданное количество раз:

for i in itertools.repeat(1, 4): 
    print i,

1 1 1 1

Бесконечный итератор, дающий целые числа, начиная с заданного:

for i in itertools.count(1):
    print i,
    if i > 100:
        break

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49
50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72
73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95
96 97 98 99 100 101

Можно бесконечно повторять и некоторую последовательность (или значения другого итератора) с помощью функции cycle():

tango = [1, 2, 3]
for i in itertools.cycle(tango):
    print i,

1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2
3 1 2 3 1
2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3
1 2 3 1 2
3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 . . .

Аналогами map() и filter() в модуле itertools найдутся imap() и ifilter(). Отличие imap от map в том, что для преждевременно завершившихся итераторов None не подставляется. Пример:

for i in map(lambda x, y: (x,y), [1,2], [1,2,3]):
    print i,

(1, 1) (2, 2) (None, 3)

from itertools import imap
for i in imap(lambda x, y: (x,y), [1,2], [1,2,3]):
  print i,

(1, 1) (2, 2)

Здесь следует заметить, что обычная функция map() нормально воспринимает итераторы в любом сочетании с итерабельными (поддающимися итерациям) объектами:

for i in map(lambda x, y: (x,y), iter([1,2]), [1,2,3]):
    print i,

(1, 1) (2, 2) (None, 3)

Есть и еще одна разновидность imap() -- starmap():

for i in itertools.starmap(lambda x, y: x+y, [(1,2),(2,3),(3,4)]): 
    print i,

3 5 7

Надеемся, из этой записи понятно, в чем ее суть.

Аналогично ifilter() работает как filter(). Кроме того, в модуле itertools есть функция ifilterfalse(), которая как бы добавляет отрицание к значению функции-первого аргумента:

for i in ifilterfalse(lambda x: x > 0, [1, -2, 3, -3]): 
    print i,

-2 -3

Некоторую новизну вносит другой вид фильтра: takewhile() и его "отрицательный" аналог dropwhile(). Следующий пример поясняет их принцип действия:

for i in takewhile(lambda x: x > 0, [1, -2, 3, -3]):
    print i,

print 
for i in dropwhile(lambda x: x > 0, [1, -2, 3, -3]):
  print i,

1
-2 3 -3

То есть, takewhile() дает значения пока условие истинно, а остальные значения не берет из итератора (именно не берет, а не высасывает все до конца!). И, наоборот, dropwhile() ничего не выдает, пока выполняется условие, зато потом выдает все без остатка.

Функция izip() аналогична встроенной zip(), но не тратит много памяти на построение списка кортежей, так как итератор выдает их строго по требованию.

В модуле itertools есть функция islice(), которая возвращает итератор, который выбирает из итерабельного объекта только значения с заданными индексами:

for i in islice(range(100), 10, 23, 2): 
    print i,

10 12 14 16 18 20 22

В заключение хочется отметить, что итераторы -- это очень практичное продолжение славного функционально-программного начала в языке Python. Итераторы по сути позволяют организовать так называемые "ленивые" (lazy) вычисления, при которых значения вычисляются только когда они непосредственно требуются.

Post Scriptum:

А вы знаете, что в Python есть еще и генераторы? Наш пример с Фибоначчи упрощается во много раз, если мы применим простой генератор (simple generator):

def Fibonacci(max):
  a, b = 0, 1
  for i in xrange(max):
    yield a
    a, b = b, a + b  

for i in Fibonacci(10):
  print i,

Но об этом в следующий раз.