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

Чтобы узнать о других значениях, см. Генератор (значения) § Вычисления .

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

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

Использует

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

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

Когда желательно быстрое вычисление (в первую очередь, когда последовательность конечна, поскольку в противном случае вычисление никогда не завершится), можно либо преобразовать его в список , либо использовать параллельную конструкцию, которая создает список вместо генератора. Например, в Python генератор g может быть оценен в виде списка l с помощью l = list(g), а в F# выражение последовательности seq { ... } оценивает лениво (генератор или последовательность), но [ ... ] жадно оценивает (список).

При наличии генераторов конструкции цикла языка, такие как for и while, можно свести к одной конструкции цикла... конца цикла; все обычные конструкции циклов затем можно удобно смоделировать, правильно используя подходящие генераторы. Например, диапазонный цикл типа for x = 1 to 10 может быть реализовано как итерация через генератор, как в Python for x in range(1, 10). Дальше, break может быть реализовано как отправка завершения генератору, а затем использование continue в петле.

Хронология

Генераторы впервые появились в CLU (1975). были важной особенностью языка манипулирования строками Icon (1977 г.) и теперь доступны в Python (2001 г.), С# , Руби , PHP , ECMAScript (начиная с ES6/ES2015 ) и другие языки. В CLU и C# генераторы называются итераторами , а в Ruby — перечислителями .

Лисп

Окончательный стандарт Common Lisp изначально не предоставляет генераторы, однако существуют различные реализации библиотек, такие как SERIES, документированные в CLtL2 или pygen .

КЛУ

Оператор доходности используется для реализации итераторов над абстракциями данных, определяемыми пользователем.

string_chars = iter (s: string) yields (char);
  index: int := 1;
  limit: int := string$size (s);
  while index <= limit do
    yield (string$fetch(s, index));
    index := index + 1;
    end;
end string_chars;

for c: char in string_chars(s) do
   ...
end;

Значок

Каждое выражение (включая циклы) является генератором. Язык имеет множество встроенных генераторов и даже реализует некоторую логическую семантику с использованием механизма генератора ( логическая дизъюнкция или «ИЛИ» выполняется таким образом).

Печать квадратов от 0 до 20 может быть достигнута с помощью сопрограммы, написав:

   local squares, j
   squares := create (seq(0) ^ 2)
   every j := |@squares do
      if j <= 20 then
         write(j)
      else
         break

Однако в большинстве случаев пользовательские генераторы реализуются с ключевым словом «suspend», которое действует точно так же, как ключевое слово «yield» в CLU.

С

В языке C нет функций-генераторов, но, поскольку они являются подмножеством сопрограмм , их легко реализовать с помощью любой среды, реализующей стековые сопрограммы, например libdill. На платформах POSIX, когда стоимость переключения контекста на итерацию не является проблемой или полный параллелизм , а не просто параллелизм требуется , можно реализовать очень простую структуру функций генератора с использованием pthreads и Pipes .

С++

В C++ можно внедрить генераторы с помощью макросов препроцессора. Результирующий код может иметь аспекты, сильно отличающиеся от собственного кода C++, но синтаксис генератора может быть очень лаконичным. Набор макросов препроцессора, определенный в этом источнике, позволяет использовать генераторы, определенные с синтаксисом, как в следующем примере:

$generator(descent)
{
   int i;

   // place the constructor of our generator, e.g. 
   // descent(int minv, int maxv) {...}
   
   // from $emit to $stop is a body of our generator:
    
   $emit(int) // will emit int values. Start of body of the generator.
      for (i = 10; i > 0; --i)
         $yield(i); // similar to yield in Python,
                    // returns next number in [1..10], reversed.
   $stop; // stop, end of sequence. End of body of the generator.
};

Затем это можно повторить, используя:

int main(int argc, char* argv[])
{
  descent gen;
  for (int n; gen(n);) // "get next" generator invocation
    printf("next number is %d\n", n);
  return 0;
}

Более того, C++11 позволяет циклы foreach к любому классу, предоставляющему применять begin и end функции. Тогда можно написать классы, подобные генератору, определив оба итерируемых метода ( begin и end) и методы итератора ( operator!=, operator++ и operator*) в том же классе. Например, можно написать следующую программу:

#include <iostream>
int main()
{
    for (int i: range(10))
    {
        std::cout << i << std::endl;
    }
    return 0;
}

Базовая реализация диапазона будет выглядеть так:

class range
{
private:
    int last;
    int iter;

public:
    range(int end):
        last(end),
        iter(0)
    {}

    // Iterable functions
    const range& begin() const { return *this; }
    const range& end() const { return *this; }

    // Iterator functions
    bool operator!=(const range&) const { return iter < last; }
    void operator++() { ++iter; }
    int operator*() const { return iter; }
};

Перл

Perl изначально не предоставляет генераторы, но поддержка обеспечивается модулем Coro::Generator , который использует Coro структуру сопрограмм . Пример использования:

use strict;
use warnings;
# Enable generator { BLOCK } and yield
use Coro::Generator;
# Array reference to iterate over
my $chars = ['A'...'Z'];

# New generator which can be called like a coderef.
my $letters = generator {
    my $i = 0;
    for my $letter (@$chars) {
        # get next letter from $chars
        yield $letter;
    }
};

# Call the generator 15 times.
print $letters->(), "\n" for (0..15);

Raku

В примере, параллельном Icon, используется класс Range Raku (ранее известный как Perl 6) как один из нескольких способов создания генераторов с помощью языка.

Напечатать квадраты от 0 до 20 можно, написав:

for (0 .. *).map(* ** 2) -> $i {
    last if $i > 20;
    say $i
}

Однако в большинстве случаев пользовательские генераторы реализуются с ключевыми словами «собрать» и «взять» в ленивом контексте.

ТКЛ

В Tcl 8.6 механизм генератора основан на именованных сопрограммах .

proc generator {body} {
    coroutine gen[incr ::disambiguator] apply {{script} {
        # Produce the result of [generator], the name of the generator
        yield [info coroutine]
        # Do the generation
        eval $script
        # Finish the loop of the caller using a 'break' exception
        return -code break
    }} $body
}

# Use a simple 'for' loop to do the actual generation
set count [generator {
    for {set i 10} {$i <= 20} {incr i} {
        yield $i
    }
}]

# Pull values from the generator until it is exhausted
while 1 {
    puts [$count]
}

Хаскелл

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

countFrom :: Integer -> [Integer]
countFrom n = n : countFrom (n + 1)

from10to20 :: [Integer]
from10to20 = takeWhile (<= 20) $ countFrom 10

primes :: [Integer]
primes = 2 : 3 : nextPrime 5
  where
    nextPrime n
        | notDivisible n = n : nextPrime (n + 2)
        | otherwise = nextPrime (n + 2)
    notDivisible n =
        all ((/= 0) . (rem n)) $ takeWhile ((<= n) . (^ 2)) $ tail primes

где (:) — конструктор нестрогого списка, cons и $ это просто оператор «вызывается с» , используемый для заключения в круглые скобки. При этом используется стандартная функция адаптера,

takeWhile p [] = []
takeWhile p (x:xs) | p x = x : takeWhile p xs
                   | otherwise = []

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

squaresUnder20 = takeWhile (<= 20) [x * x | x <- countFrom 10]
squaresForNumbersUnder20 = [x * x | x <- takeWhile (<= 20) $ countFrom 10]

Ракетка

Racket предоставляет несколько сопутствующих возможностей для генераторов. Во-первых, его формы цикла for работают с последовательностями , которые являются своего рода производителем:

(for ([i (in-range 10 20)])
  (printf "i = ~s\n" i))

и эти последовательности также являются значениями первого класса:

(define 10-to-20 (in-range 10 20))
(for ([i 10-to-20])
  (printf "i = ~s\n" i))

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

Но если говорить более конкретно, Racket поставляется с библиотекой генераторов для более традиционной спецификации генератора. Например,

#lang racket
(require racket/generator)
(define (ints-from from)
  (generator ()
    (for ([i (in-naturals from)]) ; infinite sequence of integers from 0
      (yield i))))
(define g (ints-from 10))
(list (g) (g) (g)) ; -> '(10 11 12)

Обратите внимание, что ядро ​​Racket реализует мощные функции продолжения, предоставляя общие (повторно входящие) продолжения, которые можно компоновать, а также продолжения с разделителями. Используя это, в Racket реализована библиотека генератора.

PHP

Сообщество PHP реализовало генераторы в PHP 5.5. Подробности можно найти в оригинальном Запросе комментариев: Генераторы .

Бесконечная последовательность Фибоначчи:

function fibonacci(): Generator
{
    $last = 0;
    $current = 1;
    yield 1;
    while (true) {
        $current = $last + $current;
        $last = $current - $last;
        yield $current;
    }
}

foreach (fibonacci() as $number) {
    echo $number, "\n";
}

Последовательность Фибоначчи с пределом:

function fibonacci(int $limit): Generator 
{
    yield $a = $b = $i = 1;
 
    while (++$i < $limit) {
        yield $a = ($b = $a + $b) - $a;
    }
}

foreach (fibonacci(10) as $number) {
    echo "$number\n";
}

Любая функция, содержащая оператор доходности , автоматически является функцией-генератором.

Руби

Ruby поддерживает генераторы (начиная с версии 1.9) в виде встроенного класса Enumerator.

# Generator from an Enumerator object
chars = Enumerator.new(['A', 'B', 'C', 'Z'])

4.times { puts chars.next }

# Generator from a block
count = Enumerator.new do |yielder|
  i = 0
  loop { yielder.yield i += 1 }
end

100.times { puts count.next }

Ява

Java имеет стандартный интерфейс для реализации итераторов с самого начала, а начиная с Java 5 конструкция foreach позволяет легко перебирать объекты, предоставляющие java.lang.Iterable интерфейс. ( Структура коллекций Java и другие платформы коллекций обычно предоставляют итераторы для всех коллекций.)

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);

Или получите итератор из Java 8 суперинтерфейса BaseStream of Stream.

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

// Save the iterator of a stream that generates fib sequence
Iterator<Integer> myGenerator = Stream
        // Generates Fib sequence
        .iterate(new Pair(1, 1), p -> new Pair(p.b, p.a + p.b))
        .map(p -> p.a).iterator();

// Print the first 5 elements
for (int i = 0; i < 5; i++) {
    System.out.println(myGenerator.next());
}

System.out.println("done with first iteration");

// Print the next 5 elements
for (int i = 0; i < 5; i++) {
    System.out.println(myGenerator.next());
}

Выход:

1
1
2
3
5
done with first iteration
8
13
21
34
55

С#

Пример генератора C# 2.0 (файл yield доступен начиная с версии C# 2.0): В обоих этих примерах используются дженерики, но это не обязательно. Ключевое слово выход также помогает в реализации пользовательских итераций с отслеживанием состояния коллекции, как обсуждалось в этом обсуждении.

// Method that takes an iterable input (possibly an array)
// and returns all even numbers.
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";
    }
}

XL

В XL итераторы являются основой циклов for:

import IO = XL.UI.CONSOLE

iterator IntegerIterator (var out Counter : integer; Low, High : integer) written Counter in Low..High is
    Counter := Low
    while Counter <= High loop
        yield
        Counter += 1

// Note that I needs not be declared, because declared 'var out' in the iterator
// An implicit declaration of I as an integer is therefore made here
for I in 1..5 loop
    IO.WriteLn "I=", I

Ф#

Дополнительная информация: выражение последовательности.

F# предоставляет генераторы через выражения последовательности , начиная с версии 1.9.1. Они могут определять последовательность (лениво оцениваемая, последовательный доступ) через seq { ... }, список (быстро оцениваемый, последовательный доступ) через [ ... ] или массив (быстро оцениваемый, индексированный доступ) через [| ... |] которые содержат код, генерирующий значения. Например,

seq { for b in 0 .. 25 do
          if b < 15 then
              yield b * b }

формирует последовательность квадратов чисел от 0 до 14, отфильтровывая числа из диапазона чисел от 0 до 25.

Питон

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

from typing import Iterator

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

# Example use: printing out the integers from 10 to 20.
# Note that this iteration terminates normally, despite
# countfrom() being written as an infinite loop.

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

# Another generator, which produces prime numbers indefinitely as needed.
import itertools

def primes() -> Iterator[int]:
    """Generate prime numbers indefinitely as needed."""
    yield 2
    n = 3
    p = [2]
    while True:
        # If dividing n by all the numbers in p, up to and including sqrt(n),
        # produces a non-zero remainder then n is prime.
        if all(n % f > 0 for f in itertools.takewhile(lambda f: f * f <= n, p)):
            yield n
            p.append(n)
        n += 2

В Python генератор можно рассматривать как итератор , содержащий замороженный кадр стека . В любое время next() вызывается на итераторе, Python возобновляет замороженный кадр, который выполняется нормально до следующего yield заявление достигнуто. Затем кадр генератора снова замораживается, и полученное значение возвращается вызывающей стороне.

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

Выражения-генераторы

В Python есть синтаксис, смоделированный на синтаксисе списков , называемый выражением генератора, который помогает в создании генераторов. Следующий пример расширяет первый приведенный выше пример, используя выражение-генератор для вычисления квадратов из countfrom функция генератора:

squares = (n * n for n in countfrom(2))

for j in squares:
    if j <= 20:
        print(j)
    else:
        break

ECMAScript

ECMAScript 6 (он же Harmony) представил функции генератора.

Бесконечную последовательность Фибоначчи можно записать с помощью генератора функций:

function* fibonacci(limit) {
    let [prev, curr] = [0, 1];
    while (!limit || curr <= limit) {
        yield curr;
        [prev, curr] = [curr, prev + curr];
    }
}

// bounded by upper limit 10
for (const n of fibonacci(10)) {
    console.log(n);
}

// generator without an upper bound limit
for (const n of fibonacci()) {
    console.log(n);
    if (n > 10000) break;
}

// manually iterating
let fibGen = fibonacci();
console.log(fibGen.next().value); // 1
console.log(fibGen.next().value); // 1
console.log(fibGen.next().value); // 2
console.log(fibGen.next().value); // 3
console.log(fibGen.next().value); // 5
console.log(fibGen.next().value); // 8

// picks up from where you stopped
for (const n of fibGen) {
    console.log(n);
    if (n > 10000) break;
}

Р

Для этой цели можно использовать пакет итераторов.

library(iterators)

# Example ------------------
abc <- iter(c('a','b','c'))
nextElem(abc)

Смолток

Пример в Pharo Smalltalk :

Приведенный ниже генератор золотого сечения возвращает при каждом вызове GoldenRatio next лучшее приближение к золотому сечению.

goldenRatio := Generator on: [ :g | | x y z r | 
	x := 0.
	y := 1.
	[  
		z := x + y.
		r := (z / y) asFloat.
		x := y.
		y := z.
		g yield: r
	] repeat	
].

goldenRatio next.

Выражение ниже возвращает следующие 10 приближений.

Character cr join: ((1 to: 10) collect: [ :dummy | ratio next ]).

Подробнее см. в разделе «Скрытый драгоценный камень в Pharo: Generator» .

См. также

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

Ссылки

• Стефан Мюрер, Стивен Омохундро , Дэвид Стаутамир и Клеменс Шиперски: Абстракция итерации в Сазере . Транзакции ACM по языкам и системам программирования , 18(1):1-15 (1996) [1]