В последнее время информация постепенно становится «новой нефтью» с точки зрения ценности. Проблема только в том, что объемы данных, которые приходится обрабатывать, растут не по дням, а по часам. Не все уже влезает даже на винчестер, не говоря уже об оперативной памяти, а на собеседованиях все чаще пугают задачками в духе «сравни на лету два петабайтных файла». Но к счастью программистов, необязательно заставлять машину давиться такими объемами, когда для поточной обработки можно использовать итераторы и генераторы, а еще язык программирования Python, который отлично их поддерживает. Хочешь, расскажу?
 

Потоки данных

Так уж повелось, что в русском языке слово «поток» используется во многих значениях, если говорить о программировании. Действительно, и thread, и stream, и flow — это все потоки. Про thread’ы на этот раз, пожалуй, не будем, а поговорим про stream и flow, то есть потоки ввода-вывода и потоки данных (буквальный перевод словосочетания data flow). Соответственно, дальше я буду часто использовать слово «поток», причем именно в таком значении.

Вообще, в контексте технологий мы очень часто встречаемся с тем, что нам надо анализировать или обрабатывать на лету эти самые потоки данных. Причем чем дальше, тем больше таких случаев, потому что слишком уж большие объемы информации генерирует современный мир. Настолько большие, что для их хранения и обработки строят целые вычислительные кластеры в дата-центрах. Да-да, те самые stdin, stdout и stderr, про которые рассказывают еще в школе, без устали гоняют биты и байты туда-сюда.

Если отойти от лирики и вернуться на землю, то простейшими примерами потоков данных могут служить сетевой трафик, сигнал какого-нибудь датчика или, скажем, биржевые котировки в реальном времени. И уже существует и развивается целый класс «поточных» алгоритмов для тех или иных задач. Когда ты набираешь в командной строке что-то наподобие «cat file.txt | sed s/foo/bar/g», то происходит именно манипуляция потоком данных, который с помощью «конвейера» в виде вертикальной черты передается от stdout’а команды cat на stdin команды sed.

И вот мы постепенно подходим к концепции итератора и так называемому Data Flow Programming. Для того чтобы как-нибудь сладить с этим непрерывным потоком поступающей информации, надо его порезать на кусочки и попытаться что-то сделать именно с этими кусочками. Вот тут и возникает итератор.

INFO

Итератор — это объект-абстракция, который позволяет брать из источника, будь это stdin или, скажем, какой-то большой контейнер, элемент за элементом, при этом итератор знает только о том объекте, на котором он в текущий момент остановился. С точки зрения C/C++, например, об этом можно думать как о передвигаемом по контейнеру указателе. Рекомендую применительно к этим языкам посмотреть презентацию Андрея Александреску.

 

Перебираем элементы с помощью итератора

А теперь ближе к Python. Если предыдущие абзацы показались тебе капитанством и скукой, то прошу не переживать — совсем скоро появится код.

Для начала разберемся в терминологии. В Python (и не только в нем) есть два понятия, которые звучат практически одинаково, но обозначают разные вещи, — iterator и iterable. Первое — это объект, который реализует описанный выше интерфейс, а второе — контейнер, который может служить источником данных для итератора.

Наверняка ты помнишь, что для того, чтобы экземпляр класса можно было засунуть куда-нибудь в for, класс должен реализовывать два метода — iter() и next(). Действительно, по list’у можно итерироваться, но сам по себе list никак не следит, где там мы остановились в проходе по нему. А следит объект по имени listiterator, который возвращается методом iter() и используется, скажем, циклом for или вызовом map(). Когда объекты в перебираемой коллекции кончаются, возбуждается исключение StopIteration.

Во многих случаях, за исключением особо обговоренных, я постараюсь писать код, совместимый как с Python 2, так и с Python 3. В этом мне поможет модуль six. Six представляет родительский класс, который позволяет не думать, какой next-метод объявлять в объекте, — это всегда __next__().

from __future__ import print_function
from six import Iterator
class MyIterator(Iterator):
  def __init__(self, step=5):
    self.step = step
  def __iter__(self):
    return self
  def __next__(self):
    self.step -= 1
  # Условие остановки итератора, чтобы он не бежал вечно
  if not self.step:
    raise StopIteration()
    return self.step
myiterator = MyIterator()
for item in myiterator:
  print(item, end=" ")
## 4 3 2 1

Ну, тут все совсем просто. Класс MyIterator предоставляет описанный выше интерфейс для перебора (точнее, генерации) элементов и возбуждает исключение, когда значение текущего шага достигает нуля. Рекомендую обратить внимание на «ленивость» — итератор начинает что-то делать только тогда, когда его по-дружески просит об этом for (то есть при переходе на каждую следующую итерацию).

 

Синтаксический сахар

Но стоит ли громоздить классы, когда все, что нам нужно, — это перебирать элементы коллекции? Давай вспомним такую вещь, как списковые включения, или, если по-басурмански, list comprehensions.

with open("file.txt", "r") as f:
  mylist = [l for l in f if "foo" in l]
  for item in mylist:
    print(item)
## Тут вывод из файла file.txt всех строк, где есть подстрока "foo"

Вот это уже неплохо. Три с половиной строчки кода (легко переписываются ровно в две, но я хочу проиллюстрировать идею), которые создают список, а у него, как известно, уже есть наготове итератор. Но есть одна маленькая проблема. Точнее, большая. Еще точнее, все зависит от того, насколько у нас много элементов в коллекции (в данном случае строк с подстрокой "foo" в файле, а следовательно, и в списке). Читатель ведь не забыл о том, что список в питоне — это целый кусок памяти, сродни сишному array? Более того, при добавлении элемента в конец (а именно это и происходит) есть шанс, что новый список категорически не поместится в аллоцированный для него кусок памяти и придется интерпретатору выпрашивать у системы новый, да еще и копировать туда все существующие элементы за O(n). А если файл большой и подходящих строк много? В общем, приведенный код не стоит использовать. Так что же делать?

with open("file.txt", "r") as f:
  mylist = (l for l in f if "foo" in l)
  for item in mylist:
    print(item)
## Тут тоже вывод из файла file.txt всех строк, где есть подстрока "foo"

Честно сказать, я был удивлен, когда при просмотре кода нескольких крупных open source проектов увидел, что люди очень любят списковые включения, но при этом совершенно забывают про генераторные выражения. Для меня это выглядит сродни использованию range() вместо xrange() в Python 2 только для того, чтобы перебрать числа по порядку, при этом забывая, что он отъедает кусок памяти для сохранения полного массива своих результатов.

 

Генерируем полезные вещи

Так что же такое генераторное выражение и что такое вообще генератор? Если простым языком, генераторное выражение — это еще один синтаксический сахар в Python, простейший способ создать объект с интерфейсом итератора, при этом не загружая всех элементов в память (а это чаще всего и не нужно). А что до генератора как концепции...

Вот, скажем, про функции в языке обычно не знает только тот, кому первую книжку по программированию подарили сегодня. Если вчера — уже, скорее всего, знает. Но у функций строго определенное поведение — у них одна точка входа и одно возвращаемое значение (то, что в Python можно делать "return a, b", — это не множественный возврат в полном смысле этого слова. Это всего лишь возврат кортежа). А что, если я скажу, что генератор — это та же функция, только с несколькими точками входа и выхода?

Основная фишка генератора в том, что он, подобно итератору, запоминает последний момент, когда к нему обращались, но при этом оперирует не абстрактными элементами, а вполне конкретными блоками кода. То есть если итератор по умолчанию будет перебирать элементы в контейнере, пока они не кончатся, то генератор будет гонять код, пока не выполнится какое-нибудь конкретное условие возврата. Да-да, по большому счету предоставленный в первом разделе код — это генератор с интерфейсом итератора, у которого есть вполне определенное условие выхода. Если развернуть генераторное выражение из кода выше в полноценную функцию-генератор, получится примерно так:

def my_generator(step=4):
  with open("file.txt", "r") as f:
    for l in f:
      if "foo" in l:
        yield l
myiterator = my_generator()
for item in myiterator:
  print(item)
## И тут тоже (вот так сюрприз) вывод из файла file.txt всех строк, где есть подстрока "foo"

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

def my_generator2(step=4):
  print("First block")
  yield 1
  print("Second block")
  yield 2
myiterator = my_generator2()
myiterator.next()
## "First block"
myiterator.next()
## "Second block"
myiterator.next()
## Traceback: StopIteration
 

Такой умный yield

Так, в принципе, с несколькими точками выхода мы разобрались. А как же с несколькими точками входа? Неужели next() — это все, что мы можем сделать с генератором? Оказывается, нет.

Со времен старичка Python 2.5 у объекта генератора появилось еще несколько методов: .close(), .throw() и .send(). И это привело, можно сказать, к революции в области Data Flow Programming. С помощью .close() теперь можно извне заставить генератор остановиться на следующем обращении к нему, а с помощью .throw() — заставить его бросить исключение:

from __future__ import print_function
import itertools

def my_generator3():
  # Бесконечный счетчик
  counter = itertools.count()
  while True:
    yield next(counter)
myiterator = my_generator3()
myiterator2 = my_generator3()
for item in myiterator:
  print(item, end=" ")
  if item == 3:
    # Корректно завершаем генератор
    myiterator.close()
for item in myiterator2:
  print(item, end=" ")
  if item == 2:
    # Все плохо
    myiterator2.throw(Exception("Everything is bad"))
## 0 1 2 3
## 0 1 2 Traceback (most recent call last):
## File "test.py", line 28, in <module>
## myiterator2.throw(Exception("Everything is bad"))
## File "test.py", line 12, in my_generator3
## yield next(counter)
## Exception: Everything is bad

А самое вкусное, как оказалось, спрятано в методе .send(). Он позволяет отправить данные в генератор перед вызовом следующего блока кода!

from __future__ import print_function
import itertools

def my_coroutine():
  # Бесконечный счетчик
  counter = itertools.count()
  while True:
    y = (yield next(counter))
    if y:
      # Меняем начало отсчета
      counter = itertools.count(y)
myiterator = my_coroutine()
for item in myiterator:
  print(item, end=" ")
  if item == 1:
    # Отправляем число в генератор
    myiterator.send(4)
  elif item == 6:
    myiterator.close()
## 0 1 5 6

Я не зря назвал здесь генератор словом coroutine. Корутина, или сопрограмма, — это как раз и есть та самая штука, о которой шепчутся программисты в переговорках офисов, обсуждая gevent, tornado и прочий eventlet. Более конкретно можно почитать в Википедии, а я, пожалуй, напишу о том, что корутины в таком вот виде чаще всего используют в Python для анализа потоков данных, реализуя кооперативную многозадачность.

Дело в том, что по вызову yield (как, в общем случае, и return) происходит передача управления. Сопрограмма сама решает, когда перенаправить flow в другое место (например, в другую сопрограмму). И это позволяет строить красивые разветвленные деревья обработки потоков данных, реализовывать MapReduce, возможно прокидывать текущие байты через сокет на другую ноду. Более того, сопрограммы могут быть фактически реализованы абсолютно на любом языке, равно как и утилиты командной строки в Linux, которые я приводил в пример в самом начале.

 

Крошечный практический пример

Читать код, написанный с использованием сопрограммного подхода, неподготовленному человеку довольно трудно. Он похож на набор несимметричных шестеренок, которые ухитряются вращать одна другую поочередно, храня при этом свое последнее состояние.

Но вообще такая «шестереночная» система имеет одну очень хорошую особенность: любую такую «шестеренку» можно либо переставить в другое место, либо заменить на другую, которая будет делать свою работу лучше. Это я про то, что в случае Python все, что нужно знать об объекте, — что он предоставляет внешний интерфейс итератора, понятный интерпретатору, а на каком языке он написан и что внутри себя делает — уже не так важно.

Позволю себе привести пример из презентации Дэвида Бизли (см. врезку). Прошу любить и жаловать, вариант лога Apache:

23.34.139.80 - ... "GET /categories/ HTTP/1.1" 200 6394
23.34.139.80 - ... "GET /favicon.ico HTTP/1.1" 404 807
23.34.139.80 - ... "GET /static/img/logo.gif HTTP/1.1" 200 41526
23.34.139.80 - ... "GET /news/story.html HTTP/1.1" 200 6223
23.34.139.80 - ... "GET /about/example.html HTTP/1.1" 200 1223
42.77.100.21 - ... "GET /index.html HTTP/1.1" 200 7774

Попробуем просуммировать последнюю колонку и узнать, сколько байт было переслано по сети. Вопрос, как это написать обычным циклом, оставлю тебе как домашнее задание. А мы попробуем сразу описать это генераторными выражениями.

wwwlog = open("access-log")
bytecolumn = (line.rsplit(None,1)[1] for line in wwwlog)
bytes = (int(x) for x in bytecolumn if x != '-')
print "Total", sum(bytes)

Довольно очевидно, что делает каждая строка, не правда ли? Если нам потребуется отфильтровывать какие-то определенные строки или попутно проводить еще какой-то подсчет — все можно встроить в одну «трубу», просто добавив еще несколько строк с генераторами в нужные места, как шестеренки.

 

Что со всем этим делать

Понимание того, как работают итераторы и генераторы в языках программирования, — один из первых шагов к освоению последовательной обработки гигантских потоков данных, а к этой сфере, например, относится трейдинг и технический анализ, то есть вещи, на которых в современном мире многие делают целое состояние.

Но даже если не скатываться в заоблачные выси — твой скрипт будет потреблять банально в несколько раз меньше ресурсов. Интерпретатор Python хоть и старается не копировать данные лишний раз, но он тут подневолен, ему приходится формировать в памяти список целиком, если так написал разработчик.

В общем, желаю тебе быстрого и красивого кода. Еще увидимся!

INFO

Дэвид Бизли — независимый разработчик на Python, как говорится, широко известный в узких кругах. Пишет интересные книги по программированию, преподает, а также известен как страстный любитель генераторного подхода, многопоточного программирования и модуля asyncio, что в Python 3. Рекомендую почитать две его презентации по теме статьи (оттуда взяты некоторые примеры):

  • www.dabeaz.com/generators-uk/
  • www.dabeaz.com/coroutines/

WWW

  • Подпишись на наc в Telegram!

    Только важные новости и лучшие статьи

    Подписаться

  • Подписаться
    Уведомить о
    0 комментариев
    Межтекстовые Отзывы
    Посмотреть все комментарии