Генератор (программирование)

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

Генератор похож на функцию, возвращающую массив, поскольку он имеет параметры, может быть вызван и возвращает последовательность значений. Однако выполнение генератора не является непрерывным[1]. Вместо того, чтобы создавать массив, содержащий все значения, и возвращать их в виде единой сущности, генератор возвращает значения по одному, что требует меньше памяти и позволяет вызывающему объекту немедленно приступить к обработке первых нескольких значений.

Генераторы, также известные как полусопрограммы[2], являются частным случаем сопрограмм. Однако, в отличие от классических сопрограмм, передающих управление в произвольную сопрограмму, генераторы возвращают управление вызывающей стороне при возврате значения.

Использование

править

Генераторы обычно выполняются внутри циклов. Однако, например, в языке программирования Icon все выражения являются генераторами[3], то есть могут исполняться вне контекста традиционных циклических конструкций. При первом вызове генератора в цикле создается объект, который инкапсулирует состояние подпрограммы генератора в начале её выполнения с аргументами, соответствующими требуемым параметрам. Далее тело генератора выполняется до тех пор, пока не будет встречен специальный оператор yield. Значение, указанное в операторе yield, используется в качестве возвращаемого значения. При последующих итерациях выполнение тела генератора возобновляется после оператора yield, пока не встретится следующий yield. Помимо yield, выполнение тела генератора также может быть прекращено оператором break, когда завершается цикл, заключающий в себе вызов генератора.

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

Значение, возвращаемое генератором, при необходимости может быть преобразовано в список. Например, в Python генератор g может быть преобразован в список l при помощи l = list(g).

Примеры

править

Java предоставляет стандартный интерфейс для реализации итераторов. Также, начиная с Java 5 конструкция foreach позволяет перебирать в цикле объекты, предоставляемые интерфейсом java.lang.Iterable.

record Pair(int a, int b) {};

Iterable<Integer> myIterable = Stream.iterate(new Pair(1, 1), p -> new Pair(p.b, p.a + p.b))
        .limit(10)
        .map(p -> p.a)::iterator;

myIterable.forEach(System.out::println);

Начиная с версии 2.0, C# также поддерживает генераторы

// Метод, принимающий на вход итерируемые данные (например, список)
// и возвращающий все четные числа.
public static IEnumerable<int> GetEven(IEnumerable<int> numbers)
{
    foreach (int number in numbers)
    {
        if ((number % 2) == 0)
        {
            yield return number;
        }
    }
}

Возможно использование нескольких операторов yield return. Они будут применены последовательно при каждой итерации:

public class CityCollection : IEnumerable<string>
{
    public IEnumerator<string> GetEnumerator()
    {
        yield return "New York";
        yield return "Paris";
        yield return "London";
    }
}

Генераторы были добавлены в Python в версии 2.2 в 2001 году.[4] Пример генератора:

from typing import Iterator

def countfrom(n: int) -> Iterator[int]:
    while True:
        yield n
        n += 1

# Вывод целых чисел от 10 до 20.
# Обратите внимание, что эта итерация завершается нормально, несмотря на то, что
# countfrom() представляет собой бесконечный цикл.

for i in countfrom(10):
    if i <= 20:
        print(i)
    else:
        break

# Следующий генератор возвращает простые числа неограниченное количество раз
import itertools

def primes() -> Iterator[int]:
    yield 2
    n = 3
    p = []
    while True:
         # Если n при делении на все числа в p вплоть до sqrt(n)
         # дает ненулевой остаток, то n — простое число.
         if all(n % f > 0 for f in itertools.takewhile(lambda f: f * f <= n, p)):
            yield n
            p.append(n)
        n += 2

Начиная с версии 3.3 Python поддерживает выражение yield from, позволяющее генератору делегировать часть своих операций другому генератору или итерируемому объекту.[5]

См. также

править

Примечания

править
  1. Iterators and generators. Дата обращения: 10 марта 2023. Архивировано 2 марта 2023 года.
  2. Anthony Ralston. Encyclopedia of computer science. — Nature Pub. Group, 2000. — ISBN 978-1-56159-248-7. Архивная копия от 17 октября 2023 на Wayback Machine
  3. Thomas W. Christopher. Icon Programming Language Handbook (англ.). — P. 35. — 226 p. Архивировано 18 февраля 2023 года.
  4. PEP 255 – Simple Generators. Дата обращения: 11 марта 2023. Архивировано 31 января 2023 года.
  5. PEP 380 – Syntax for Delegating to a Subgenerator. Дата обращения: 11 марта 2023. Архивировано 25 декабря 2022 года.

Ссылки

править