Глава 5. Последовательности и сопрограммы

Источник: Chapter 5: Sequences and Coroutines

Переводчик: Летучий дракон

Протокол: CC BY-NC-SA 4.0

5.1 Введение

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

Последовательные типы данных эффективны и позволяют эффективно обращаться к большому количеству упорядоченных наборов данных. Однако использование абстракции последовательности для представления упорядоченных данных имеет два важных ограничения. Первое заключается в том, что последовательность длиной n занимает объём памяти, пропорциональный n. Таким образом, чем длиннее последовательность, тем больше места она занимает в памяти. Второе ограничение заключается в том, что последовательности могут представлять только известные и конечные наборы данных. Многие упорядоченные множества, которые мы хотим представить, не имеют определённой длины или даже бесконечны. Математические примеры бесконечных последовательностей включают положительные целые числа и числа Фибоначчи. Бесконечные упорядоченные наборы данных также встречаются в других областях вычислений, например, последовательность состояний всех твитов растёт каждую секунду и поэтому не имеет фиксированной длины. Аналогично, последовательность телефонных звонков, отправляемых с базовой станции, последовательность действий мыши, выполняемых пользователем компьютера, и последовательность измерений ускорения, производимых датчиками на самолёте, постоянно расширяются в процессе эволюции мира.

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

5.2 Неявные последовательности

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

Простым примером этой концепции является диапазон, представленный во второй главе. Диапазон представляет собой последовательность целых чисел, ограниченную определёнными границами. Однако каждый элемент не хранится явно в памяти; когда элемент извлекается из диапазона, он вычисляется. Поэтому мы можем представлять очень большие диапазоны целых чисел. Только конечное положение диапазона сохраняется как часть объекта диапазона, а все остальные элементы вычисляются по мере необходимости.

>>> r = range(10000, 1000000000)
>>> r[45006230]
45016230

В этом примере при создании диапазона не сохраняются все 999 990 000 целых чисел внутри диапазона. Вместо этого объект диапазона будет добавлять 45 006 230 к первому элементу 10 000 для получения 45-го элемента. Вычисление требуемого значения элемента происходит не путём извлечения его из существующего представления, это пример ленивых вычислений. Ленивые вычисления высоко ценятся в информатике.

Итератор — это объект, предоставляющий упорядоченный доступ к базовому набору упорядоченных данных. Итераторы являются фундаментальным понятием во многих языках программирования, включая Python. Итератор состоит из двух частей: механизма для получения следующего элемента базовой последовательности элементов и механизма для определения того, что последовательность элементов достигла конца и больше нет доступных элементов. В языках программирования с встроенными объектами эта абстракция обычно реализуется через определённый интерфейс, который может быть реализован классом. Интерфейс итератора Python будет описан в следующем разделе.

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

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

5.2.1 Итераторы Python

Интерфейс итератора Python включает в себя два сообщения. __next__ сообщение получает следующий элемент базовой последовательности от итератора. Для ответа на вызов метода __next__, итератор может выполнять любые вычисления для получения или вычисления следующего элемента базовых данных последовательности. Вызов __next__ приводит к изменению итератора: он перемещает позицию итератора вперёд. Следовательно, многократные вызовы __next__ возвращают элементы базовой последовательности по порядку. Во время вызова __next__ Python использует исключение StopIteration, чтобы указать, что базовые данные последовательности достигли конца.

Следующий класс Letters перебирает буквы от a до d в базовой последовательности. Переменная экземпляра current содержит букву в последовательности. Метод __next__ возвращает эту букву и использует её для вычисления нового значения current.

>>> class Letters(object):
        def __init__(self):
            self.current = 'a'
        def __next__(self):
            if self.current > 'd':
                raise StopIteration
            result = self.current
            self.current = chr(ord(result)+1)
            return result
        def __iter__(self):
            return self

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

Используя этот класс, мы можем получить доступ к буквам в последовательности:

>>> letters = Letters()
>>> letters.__next__()
'a'
>>> letters.__next__()
'b'
>>> letters.__next__()
'c'
>>> letters.__next__()
'd'
>>> letters.__next__()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 12, in next
StopIteration

Пример класса Letters можно повторить только один раз. Как только метод __next__() вызывает исключение StopIteration, оно остаётся таким навсегда. Если не создать новый экземпляр, его невозможно сбросить.

Итераторы также позволяют нам представлять бесконечные последовательности путём реализации метода __next__, который никогда не вызывает исключение StopIteration. Например, следующий класс Positives перебирает бесконечную последовательность положительных целых чисел:

>>> class Positives(object):
        def __init__(self):
            self.current = 0;
        def __next__(self):
            result = self.current
            self.current += 1
            return result
        def __iter__(self):
            return self

5.2.2 Оператор for

В Python последовательности можно использовать в операторе for, реализуя метод __iter__, чтобы вернуть итератор. Если объект представляет упорядоченные данные, его можно использовать как итерируемый объект в операторе for, отвечая на сообщение __iter__, которое возвращает итератор. Этот итератор должен иметь метод __next__(), который последовательно возвращает каждый элемент последовательности, вызывая исключение StopIteration после достижения конца последовательности.

>>> counts = [1, 2, 3]
>>> for item in counts:
        print(item)
1
2
3

В приведённом выше примере список counts возвращает итератор в ответ на вызов метода __iter__(). Оператор for затем многократно вызывает метод __next__() итератора и присваивает возвращаемое значение переменной item. Этот процесс продолжается до тех пор, пока итератор не вызовет исключение StopIteration, после чего оператор for завершается.

Зная об итераторах, мы можем реализовать оператор for, используя while, присваивание и try операторы:

>>> i = counts.__iter__()
>>> try:
        while True:
            item = i.__next__()
            print(item)
    except StopIteration:
        pass
1
2
3

Здесь вызов метода __iter__() списка counts возвращает итератор, связанный с именем i, что позволяет последовательно получать каждый элемент. Обработка исключения StopIteration в предложении except ничего не делает, но обеспечивает механизм выхода из цикла while. Генераторы и оператор yield

В приведённом выше коде объекты Letters и Positives требуют введения нового поля self.current для отслеживания процесса обработки последовательности. В простой последовательности, показанной выше, это можно легко реализовать. Однако для сложных последовательностей next() может быть трудно сохранить пространство в вычислениях. Генераторы позволяют нам определять более сложные итерации, используя особенности интерпретатора Python.

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

Генераторы не используют никаких свойств объекта для отслеживания обработки последовательности. Они управляют выполнением генераторной функции, выполняя каждый раз метод next при его вызове. Итерация Letters может быть реализована более лаконично с использованием генераторной функции.

>>> def letters_generator():
        current = 'a'
        while current <= 'd':
            yield current
            current = chr(ord(current)+1)
>>> for letter in letters_generator():
        print(letter)
a
b
c
d

Даже если мы никогда явно не определяем методы iter или next, Python понимает, что мы намерены определить генераторную функцию, когда используем оператор yield. При вызове генераторная функция не возвращает конкретное значение, а возвращает генератор (вид итератора), который сам может возвращать значения. Генератор имеет методы iter и next, каждый вызов next продолжает выполнение генераторной функции с того места, где она остановилась в последний раз.

Первый вызов next запускает выполнение функции letters_generator до достижения оператора yield. Затем он приостанавливается и возвращает значение current. Оператор yield не разрушает созданную среду, а сохраняет её для последующего использования. Когда next вызывается снова, выполнение возобновляется с того места, где оно было приостановлено. Значения current и любых связанных имён сохраняются в области видимости letters_generator для последующих вызовов next.

Мы можем перебирать генератор, вызывая next вручную:

>>> letters = letters_generator()
>>> type(letters)
<class 'generator'>
>>> letters.__next__()
'a'
>>> letters.__next__()
'b'
>>> letters.__next__()
'c'
>>> letters.__next__()
'd'
>>> letters.__next__()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
StopIteration

Перед первым вызовом next генератор не начинает выполнять какие-либо операторы в теле генераторной функции. s.rest

Stream(5, <compute_rest>)

Когда make_integer_stream впервые вызывается, он возвращает поток, первый элемент которого является первым целым числом в последовательности (по умолчанию 1). Однако make_integer_stream, по сути, рекурсивен, потому что его функция compute_rest снова вызывает make_integer_stream. Это делает make_integer_stream рекурсивным и ленивым.

Пример:

>>> ints.first
1
>>> ints.rest.first
2
>>> ints.rest.rest
Stream(3, <compute_rest>)

Каждый раз, когда запрашивается rest потока целых чисел, происходит только рекурсивный вызов make_integer_stream.

Те же высокоуровневые функции для работы с последовательностями — map и filter — могут быть применены к потокам, хотя их реализация должна быть изменена, чтобы лениво вызывать их параметрические функции. Функция map_stream отображает функцию на потоке, создавая новый поток. Локально определённая функция compute_rest гарантирует, что независимо от того, когда вычисляется rest, эта функция будет отображать поток на его оставшейся части.

Пример реализации:

def map_stream(fn, s):
    if s.empty:
        return s
    def compute_rest():
        return map_stream(fn, s.rest)
    return Stream(fn(s.first), compute_rest)

Поток может быть отфильтрован путём определения функции compute_rest, которая вызывает функцию фильтратора на оставшейся части потока. Если функция фильтратора отклоняет первый элемент потока, оставшаяся часть немедленно вычисляется. Поскольку filter_stream является рекурсивной функцией, оставшаяся часть может вычисляться несколько раз до тех пор, пока не будет найден действительный первый элемент.

Пример реализации:

def filter_stream(fn, s):
    if s.empty:
        return s
    def compute_rest():
        return filter_stream(fn, s.rest)
    if fn(s.first):
        return Stream(s.first, compute_rest)
    return compute_rest()

Функции map_stream и filter_stream демонстрируют общий шаблон обработки потоков: независимо от того, когда оставшаяся часть потока вычисляется, локально определённая функция compute_rest всегда будет рекурсивно вызывать функцию обработки на оставшейся части потока.

Чтобы наблюдать за содержимым потока, мы должны ограничить его длину и преобразовать в список Python.

Примеры реализации:

def truncate_stream(s, k):
    if s.empty or k == 0:
        return Stream.empty
    def compute_rest():
        return truncate_stream(s.rest, k-1)
    return Stream(s.first, compute_rest)

def stream_to_list(s):
    r = []
    while not s.empty:
        r.append(s.first)
        s = s.rest
    return r

Эти удобные функции позволяют нам проверить реализацию map_stream, используя простой пример, который возводит в квадрат целые числа от 3 до 7.

Пример использования:

s = make_integer_stream(3)
m = map_stream(lambda x: x*x, s)
stream_to_list(truncate_stream(m, 5))

Мы можем использовать нашу функцию filter_stream, чтобы определить поток простых чисел, используя метод сита Эратосфена, который фильтрует поток целых чисел и удаляет кратные первому элементу. Удаляя все кратные числа первого элемента, поток становится потоком простых чисел.

Пример реализации:

def primes(pos_stream):
    def not_divible(x):
        return x % pos_stream.first != 0
    def compute_rest():
        return primes(filter_stream(not_divible, pos_stream.rest))
    return Stream(pos_stream.first, compute_rest)

Ограничивая поток primes, мы можем перечислить любое количество простых чисел:

Пример использования:

p1 = primes(make_integer_stream(2))
stream_to_list(truncate_stream(p1, 7))

В отличие от списков, потоки можно многократно передавать чистым функциям, и каждый раз они будут выдавать одно и то же значение. Поток простых чисел не «исчерпывается» после преобразования в список. То есть после преобразования префикса потока в список первый элемент p1 всё ещё равен 2.

Пример проверки:

p1.first