Потоки данных
Так уж повелось, что в русском языке слово «поток» используется во многих значениях, если говорить о программировании. Действительно, и 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. Для того чтобы как-нибудь сладить с этим непрерывным потоком поступающей информации, надо его порезать на кусочки и попытаться что-то сделать именно с этими кусочками. Вот тут и возникает итератор.
Перебираем элементы с помощью итератора
А теперь ближе к 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 хоть и старается не копировать данные лишний раз, но он тут подневолен, ему приходится формировать в памяти список целиком, если так написал разработчик.
Что такое Итератор (Iterator)?
Итератор – это объект, который позволяет вам поэлементно проходить (перебирать) коллекцию данных (например, список, кортеж или словарь) или последовательность, не зная ее внутренней структуры.
Протокол Итератора: Чтобы быть итератором, объект должен реализовывать два “магических” метода:
__iter__(): Возвращает сам объект-итератор.
__next__(): Возвращает следующий элемент последовательности. Когда элементы заканчиваются, он вызывает исключение StopIteration.
Использование: Итераторы лежат в основе цикла for в Python. Когда вы используете for, Python автоматически создает итератор и вызывает его метод __next__() на каждой итерации.
Особенность: Итератор позволяет работать с данными по одному, не загружая всю коллекцию в память сразу (хотя сама коллекция может храниться целиком).
Python
Пример создания итератора из списка
my_list = [1, 2, 3]
my_iterator = iter(my_list) # Получаем итератор
print(next(my_iterator)) # Выводит 1
print(next(my_iterator)) # Выводит 2
Что такое Генератор (Generator)?
Генератор – это более простой и элегантный способ создания итераторов. По сути, любой генератор является итератором.
Создание: Генераторы создаются с помощью функций-генераторов или генераторных выражений.
Функция-генератор: Обычная функция, которая использует ключевое слово yield вместо return.
Ключевое слово yield: Оно “замораживает” выполнение функции, возвращает значение (выдает его), а затем сохраняет все свое локальное состояние (значения переменных, место в коде). При следующем вызове функция возобновляет работу с того же места.
“Ленивые вычисления” (Lazy Evaluation): Главное преимущество генераторов. Они генерируют значения по требованию (когда вызывается next()), а не создают всю последовательность сразу и не хранят ее в памяти.
Эффективность: Это делает генераторы невероятно эффективными для работы с очень большими или даже бесконечными последовательностями данных, так как они экономят оперативную память.
Python
Пример функции-генератора
def simple_generator():
yield 1
yield 2
yield 3
my_generator = simple_generator() # Создается объект-генератор (итератор)
print(next(my_generator)) # Выводит 1
print(next(my_generator)) # Выводит 2
Основные различия
Итератор (Iterator):
Общая концепция, механизм обхода.
Обычно реализуется как класс с методами __iter__() и __next__().
Требует больше "шаблонного" кода (boilerplate) для реализации протокола.
Позволяет перебирать, но исходная коллекция может храниться в памяти.
Состояние (текущий элемент) сохраняется в полях класса.
Генератор (Generator)
Специальный тип Итератора.
Реализуется как функция с ключевым словом yield.
Значительно проще и короче (синтаксический сахар).
Реализует ленивые вычисления; генерирует значения по одному, очень экономно расходует память.
Состояние (локальные переменные, ход выполнения) сохраняется автоматически между вызовами yield.
Что такое контейнер
Контейнер – это тип данных, который инкапсулирует в себе значения других типов. Списки, кортежи, множества, словари и т.д. являются контейнерами.
Что такое итерабельный объект
Итерабельный объект (в оригинальной терминологии – «iterable») – это объект, который может возвращать значения по одному за раз. Примеры: все контейнеры и последовательности (списки, строки и т.д.), файлы, а также экземпляры любых классов, в которых определён метод __iter__() или __getitem__(). Итерабельные объекты могут быть использованы внутри цикла for, а также во многих других случаях, когда ожидается последовательность (функции sum(), zip(), map() и т.д.).
Подробнее:
Рассмотрим итерируемый объект (Iterable). В стандартной библиотеке он объявлен как абстрактный класс collections.abc.Iterable:
class Iterable(metaclass=ABCMeta):
\_\_slots\_\_ = ()
@abstractmethod
def \_\_iter\_\_(self):
while False:
yield None
@classmethod
def \_\_subclasshook\_\_(cls, C):
if cls is Iterable:
return _check_methods(C, "\_\_iter\_\_")
return NotImplemented У него есть абстрактный метод \_\_iter\_\_ который должен вернуть объект итератора. И метод \_\_subclasshook\_\_ который проверяет наличие у класса метод \_\_iter\_\_. Таким образом, получается, что итерируемый объект это любой объект который реализует метод \_\_iter\_\_class SomeIterable1(collections.abc.Iterable):
def __iter__(self):
pass
class SomeIterable2:
def __iter__(self):
pass
print(isinstance(SomeIterable1(), collections.abc.Iterable))
# True
print(isinstance(SomeIterable2(), collections.abc.Iterable))
# True
Но есть один момент, это функция iter(). Именно эту функцией использует например цикл for для получения итератора. Функция iter() в первую очередь для получения итератора из объекта, вызывает его метод __iter__. Если метод не реализован, то она проверяет наличие метода __getitem__ и если он реализован, то на его основе создается итератор. __getitem__ должен принимать индекс с нуля. Если не реализован ни один из этих методов, тогда будет вызвано исключение TypeError.
from string import ascii_letters
class SomeIterable3:
def __getitem__(self, key):
return ascii_letters[key]
for item in SomeIterable3():
print(item)
Что такое итератор
Итератор (iterator) – это объект, который представляет поток данных. Повторяемый вызов метода __next__() (next() в Python 2) итератора или передача его встроенной функции next() возвращает последующие элементы потока.
Если больше не осталось данных, выбрасывается исключение StopIteration. После этого итератор исчерпан и любые последующие вызовы его метода __next__() снова генерируют исключение StopIteration.
Итераторы обязаны иметь метод __iter__, который возвращает сам объект итератора, так что любой итератор также является итерабельным объектом и может быть использован почти везде, где принимаются итерабельные объекты.
Подробнее:
Итераторы представлены абстрактным классом collections.abc.Iterator:
class Iterator(Iterable):
\_\_slots\_\_ = ()
@abstractmethod
def \_\_next\_\_(self):
'Return the next item from the iterator. When exhausted, raise StopIteration'
raise StopIteration
def \_\_iter\_\_(self):
return self
@classmethod
def \_\_subclasshook\_\_(cls, C):
if cls is Iterator:
return _check_methods(C, '\_\_iter\_\_', '\_\_next\_\_')
return NotImplemented \_\_next\_\_ Возвращает следующий доступный элемент и вызывает исключение StopIteration, когда элементов не осталось. \_\_iter\_\_ Возвращает self. Это позволяет использовать итератор там, где ожидается итерируемых объект, например for. \_\_subclasshook\_\_ Проверяет наличие у класса метода \_\_iter\_\_ и \_\_next\_\_Что такое генератор
В зависимости от контекста, может означать либо функцию-генератор, либо итератор генератора (чаще всего, последнее). Методы __iter__ и __next__ у генераторов создаются автоматически.
С точки зрения реализации, генератор в Python — это языковая конструкция, которую можно реализовать двумя способами: как функция с ключевым словом yield или как генераторное выражение. В результате вызова функции или вычисления выражения, получаем объект-генератор типа types.GeneratorType. Канонический пример - генератор, порождающий последовательность чисел Фибоначчи, которая, будучи бесконечна, не смогла бы поместиться ни в одну коллекцию. Иногда термин применяется для самой генераторной функции, а не только объекта, возвращенного ей в качестве результата.
Так как в объекте-генераторе определены методы __next__ и __iter__, то есть реализован протокол итератора, с этой точки зрения, в Python любой генератор является итератором.
Когда выполнение функции-генераторы завершается (при помощи ключевого слова return или достижения конца функции), возникает исключение StopIteration.
Что такое генераторная функция
Генераторная функция - функция, в теле которой встречается ключевое слово yield. Будучи вызвана, такая функция возвращает объект-генератор (generator object) (итератор генератора (generator iterator)).
Что делает yield
yield замораживает состояние функции-генератора и возвращает текущее значение. После следующего вызова __next__() функция-генератор продолжает своё выполнение с того места, где она была приостановлена.
В чем отличие [x for x in y] от (x for x in y)
Первое выражение возвращает список (списковое включение), второе – генератор
Что особенного в генераторе
Генератор хранит в памяти не все элементы, а только внутреннее состояние для вычисления очередного элемента. На каждом шаге можно вычислить только следующий элемент, но не предыдущий. Пройти генератор в цикле можно только один раз
Как объявить генератор
- использовать синтаксис (x for x in seq)
- оператор yield в теле функции вместо return
- встроенная функция iter, которая вызывает у объекта метод __iter__(). Этот метод должен возвращать генератор
Как получить из генератора список
Передать его в конструктор списка: list(x for x in some_seq). Важно, что после этого по генератору уже нельзя будет итерироваться.
Что такое подгенератор
В Python 3 существуют так называемые подгенераторы (subgenerators). Если в функции-генераторе встречается пара ключевых слов yield from, после которых следует объект-генератор, то данный генератор делегирует доступ к подгенератору, пока он не завершится (не закончатся его значения), после чего продолжает своё исполнение.
На самом деле yield является выражением. Оно может принимать значения, которые отправляются в генератор. Если в генератор не отправляются значения, результат данного выражения равен None.
yield from также является выражением. Его результатом является то значение, которое подгенератор возвращает в исключении StopIteration (для этого значение возвращается при помощи ключевого слова return).
Какие методы есть у генераторов
- __next__() – начинает или продолжает исполнение функции-генератора. Результат текущего yield-выражения будет равен None. Выполнение затем продолжается до следующего yield-выражения, которое передаёт значение туда, где был вызван __next__. Если генератор завершается без возврата значения при помощи yield, возникает исключение StopIteration. Метод обычно вызывается неявно, то есть циклом for или встроенной функцией next().
- send(value) – продолжает выполнение и отправляет значение в функцию-генератор. Аргумент value становится значением текущего yield-выражения. Метод send() возвращает следующее значение, возвращённое генератором, или выбрасывает исключение StopIteration, если генератор завершается без возврата значения. Если send() используется для запуска генератора, то единственным допустимым значением является None, так как ещё не было выполнено ни одно yield-выражение, которому можно присвоить это значение.
- throw(type[, value[, traceback]]) – выбрасывает исключение типа type в месте, где был приостановлен генератор, и возвращает следующее значение генератора (или выбрасывает StopIteration). Если генератор не обрабатывает данное исключение (или выбрасывает другое исключение), то оно выбрасывается в месте вызова.
- close() – выбрасывает исключение GeneratorExit в месте, где был приостановлен генератор. Если генератор выбрасывает StopIteration (путём нормального завершения или по причине того, что он уже закрыт) или GeneratorExit (путём отсутствия обработки данного исключения), close просто возвращается к месту вызова. Если же генератор возвращает очередное значение, выбрасывается исключение RuntimeError. Метод close() ничего не делает, если генератор уже завершён.
Можно ли извлечь элемент генератора по индексу
Нет, будет ошибка. Генератор не поддерживает метод __getitem__.
Что возвращает итерация по словарю
Ключ. Порядок следования ключей не гарантируется (в 3.6 гарантируется неофициально, в 3.7 гарантируется). Для маленьких словарей порядок будет тот же, что и в объявлении. Для больших порядок зависит от расположения элементов в памяти. Особый класс OrderedDict учитывает порядок добавления ключей.
for key in {‘foo’: 1, ‘bar’: 2}:
process_key(key)
