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

Для использования в других целях см. Генератор (значения) § Вычисления.

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

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

Использует

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

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

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

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

График

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

Лисп

Финал Common Lisp стандарт не предоставляет генераторы изначально, но существуют различные реализации библиотек, такие как СЕРИИ задокументировано в CLtL2 или Pygen.

CLU

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

string_chars = iter (s: string) дает (char); индекс: int: = 1; ограничение: int: = строка $ size (s); в то время как index <= limit do yield (string $ fetch (s, index)); index: = index + 1; конец; конец string_chars; для c: char в string_chars (s) do ... end;

Значок

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

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

   локальные квадраты, j квадратов: = create (seq (0) ^ 2) каждый j: = | @squares do if j <= 20 then write (j) else break

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

C

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

C ++

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

$генератор(спуск){   int я;   // размещаем конструктор нашего генератора, например    // спуск (int minv, int maxv) {...}      // от $ emit до $ stop - это тело нашего генератора:       $испускают(int) // выдаст значения типа int. Запуск корпуса генератора.      за (я = 10; я > 0; --я)         $урожай(я); // аналогично yield в Python,                    // возвращает следующее число в [1..10] в обратном порядке.   $остановка; // стоп, конец последовательности. Конец корпуса генератора.};

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

int главный(int argc, char* argv[]){  спуск ген;  за(int п; ген(п);) // вызов генератора "получить следующий"    printf("следующий номер% d п", п);  возвращаться 0;}

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

#включают <iostream>int главный(){    за (int я: классифицировать(10))    {        стандартное::cout << я << стандартное::конец;    }    возвращаться 0;}

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

учебный класс классифицировать{частный:    int последний;    int iter;общественный:    классифицировать(int конец):        последний(конец),        iter(0)    {}    // Итерируемые функции    const классифицировать& начинать() const { возвращаться *это; }    const классифицировать& конец() const { возвращаться *это; }    // Функции итератора    bool оператор!=(const классифицировать&) const { возвращаться iter < последний; }    пустота оператор++() { ++iter; }    int оператор*() const { возвращаться iter; }};

Perl

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

использовать строгий;использовать предупреждения;# Включить генератор {BLOCK} и датьиспользовать Coro :: Генератор;# Ссылка на массив для переборамой $ символы = ['А'...'Z'];# Новый генератор, который можно вызывать как coderef.мой буквы $ = генератор {    мой $ i = 0;    за мой $ письмо (@ $ символы) {        # получить следующее письмо от $ chars        урожай $ письмо;    }};# Вызвать генератор 15 раз.Распечатать буквы $->(), " п" за (0..15);

Tcl

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

proc генератор {тело} {    сопрограмма ген[incr ::средство устранения неоднозначности] подать заявление {{сценарий} {        # Произвести результат [генератор], имя генератора        урожай [Информация сопрограмма]        # У поколения        оценка $ script        # Завершить цикл вызывающего, используя исключение break        возвращаться -взлом кода }} $ body}# Используйте простой цикл for для фактической генерациинабор считать [генератор {    за {набор я 10} {$ i <= 20} {incr я} {        урожай $ i    }}]# Извлекаем значения из генератора, пока он не исчерпанпока 1 {    ставит [$ count]}

Haskell

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

считать от п = п : считать от (п+1)- Пример использования: распечатка целых чисел от 10 до 20.test1 = mapM_ Распечатать $ взять (<= 20) $ считать от 10простые числа = 2 : 3 : nextprime 5  куда  nextprime п | б = п : nextprime (п+2)              | иначе = nextprime (п+2)    куда б = все ((/= 0).(rem п)) $ взять ((<= п).(^2)) $ хвост простые числа

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

взять п [] = []взять п (Икс:хз) | п Икс = Икс : взять п хз                   | иначе = []

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

test2 = mapM_ Распечатать $ взять (<= 20) [Икс*Икс | Икс <- считать от 10]test3 = mapM_ Распечатать [Икс*Икс | Икс <- взять (<= 20) $ считать от 10]

Ракетка

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

(за ([я (в диапазоне 10 20)])  (printf "я = ~ с п" я))

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

(определять С 10 до 20 (в диапазоне 10 20))(за ([я С 10 до 20])  (printf "я = ~ с п" я))

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

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

#lang ракетка(требовать ракетка / генератор)(определять (ints-from из)  (генератор ()    (за ([я (натуральные из)]) ; бесконечная последовательность целых чисел от 0      (урожай я))))(определять грамм (ints-from 10))(список (грамм) (грамм) (грамм)) ; -> '(10 11 12)

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

PHP

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

функция Фибоначчи(){    $ последний = 0;    $ текущий = 1;    урожай 1;    пока (истинный) {        $ текущий = $ последний + $ текущий;        $ последний = $ текущий - $ последний;        урожай $ текущий;    }}для каждого (Фибоначчи() в качестве число $) {    эхо число $, " п";}

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

Рубин

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

# Генератор из объекта Enumeratorсимволы = Счетчик.новый(['А', 'B', 'C', 'Z'])4.раз { ставит символы.следующий }# Генератор из блокасчитать = Счетчик.новый делать |уступающий|  я = 0  петля { уступающий.урожай я += 1 }конец100.раз { ставит считать.следующий }

Ява

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

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

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

Исходный пример выше может быть записан на Java 5 в качестве:

// Итератор реализован как анонимный класс. Здесь используются дженерики, но в этом нет необходимости.за (int я: новый Итерабельный<Целое число>() {    @Override    общественный Итератор<Целое число> итератор() {        возвращаться новый Итератор<Целое число>() {            int прилавок = 1;            @Override            общественный логический hasNext() {                возвращаться прилавок <= 100;            }            @Override            общественный Целое число следующий() {                возвращаться прилавок++;            }            @Override            общественный пустота удалять() {                бросать новый UnsupportedOperationException();            }        };    }}) {    Система.из.println(я);}

Бесконечную последовательность Фибоначчи также можно записать в Java 5 в качестве Итератора:

Итерабельный<Целое число> фибо = новый Итерабельный<Целое число>() {    @Override    общественный Итератор<Целое число> итератор() {        возвращаться новый Итератор<Целое число>() {            int а = 1, б = 2;            @Override            общественный логический hasNext() {                возвращаться истинный;            }            @Override            общественный Целое число следующий() {                int темп = а;                а = б;                б = а + темп;                возвращаться темп;            }            @Override            общественный пустота удалять() {                бросать новый UnsupportedOperationException();            }        };    }};// затем это можно было бы использовать как ...за (int ж: фибо) {    Система.из.println("следующее число Фибоначчи" + ж);    если (someCondition(ж)) перемена;}

Также бесконечную последовательность Фибоначчи можно записать с помощью Java 8 Интерфейс потока:

IntStream.генерировать(новый IntSupplier() {    int а = 1, б = 2;    общественный int getAsInt() {        int темп = а;        а = б;        б = а + темп;        возвращаться темп;    }}).для каждого(Система.из::println);

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

общественный Итерабельный<Целое число> Фибоначчи(int предел){    возвращаться IntStream.генерировать(новый IntSupplier() {        int а = 1, б = 2;        общественный int getAsInt() {            int темп = а;            а = б;            б = а + темп;            возвращаться темп;        }    }).предел(предел).в штучной упаковке()::итератор;}// затем это можно было бы использовать как ...за (int ж: Фибоначчи(10)) {    Система.из.println(ж);}

C #

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

// Метод, принимающий итеративный ввод (возможно, массив)// и возвращает все четные числа.общественный статический IEnumerable<int> Получить еще(IEnumerable<int> числа) {    для каждого (int я в числа) {        если ((я % 2) == 0) {            урожай возвращаться я;        }    }}

Можно использовать несколько доходность доходность операторы, и они применяются последовательно на каждой итерации:

общественный учебный класс CityCollection : IEnumerable<нить> {    общественный IEnumerator<нить> GetEnumerator() {        урожай возвращаться "Нью-Йорк";        урожай возвращаться "Париж";        урожай возвращаться "Лондон";    }}

XL

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

import IO = XL.UI.CONSOLEiterator IntegerIterator (var out Counter: integer; Low, High: integer) записал Counter в Low..High is Counter: = Low while Counter <= High loop yield Counter + = 1 // Обратите внимание, что I не нужно объявлять, потому что в итераторе объявлено 'var out' // Поэтому здесь неявное объявление I как целого числа сделано для I в 1..5 цикла IO.WriteLn "I =", I

F #

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

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

seq { за б в 0 .. 25 делать          если б < 15 тогда              урожай б * б }

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

Python

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

из набор текста импорт Итераторdef считать от(п: int) -> Итератор[int]:    пока Истинный:        урожай п        п += 1# Пример использования: вывод целых чисел от 10 до 20.# Обратите внимание, что эта итерация завершается нормально, несмотря на# countfrom () записывается как бесконечный цикл.за я в считать от(10):    если я <= 20:        Распечатать(я)    еще:        перемена# Другой генератор, который производит неограниченное количество простых чисел по мере необходимости.импорт itertoolsdef простые числа() -> Итератор[int]:    урожай 2    п = 3    п = []    пока Истинный:        # При делении n на все числа в p до sqrt (n) включительно,        # дает ненулевой остаток, тогда n простое.        если все(п % ж > 0 за ж в itertools.взять пока(лямбда ж: ж*ж <= п, п)):            урожай п            п.добавить(п)        п += 2

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

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

Генератор выражений

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

квадраты = (п * п за п в считать от(2))за j в квадраты:    если j <= 20:        Распечатать(j)    еще:        перемена

ECMAScript

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

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

функция* Фибоначчи(предел) {    позволять [предыдущий, curr] = [0, 1];    пока (!предел || curr <= предел) {        урожай curr;        [предыдущий, curr] = [curr, предыдущий + curr];    }}// ограничено верхним пределом 10за (const п из Фибоначчи(10)) {    консоль.бревно(п);}// генератор без верхней границыза (const п из Фибоначчи()) {    консоль.бревно(п);    если (п > 10000) перемена;}// итерация вручнуюпозволять fibGen = Фибоначчи();консоль.бревно(fibGen.следующий().ценить); // 1консоль.бревно(fibGen.следующий().ценить); // 1консоль.бревно(fibGen.следующий().ценить); // 2консоль.бревно(fibGen.следующий().ценить); // 3консоль.бревно(fibGen.следующий().ценить); // 5консоль.бревно(fibGen.следующий().ценить); // 8// берет с того места, где вы остановилисьза (const п из fibGen) {    консоль.бревно(п);    если (п > 10000) перемена;}

р

Для этого можно использовать пакет итераторов.[14][15]

библиотека(итераторы)# Пример ------------------abc <- iter(c('а','b','c'))nextElem(abc)

Болтовня

Пример в Pharo Smalltalk:

В Золотое сечение генератор ниже возвращает к каждому вызову 'goldenRatio next' лучшее приближение к золотому сечению. 

Золотое сечение := Генератор на: [ :грамм | | х г г | 	Икс := 0.	у := 1.	[  		z := Икс + у.		р := (z / у) asFloat.		Икс := у.		у := z.		грамм урожай: р	] повторение	].Золотое сечение следующий.

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

Характер cr присоединиться: ((1 к: 10) собирать: [ :дурачок | соотношение следующий ]).

Смотрите больше в Скрытый камень в Pharo: Generator.

Смотрите также

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

Примечания

  1. ^ В чем разница между итератором и генератором?
  2. ^ Киселев, Олег (январь 2004 г.). «Общие способы просмотра коллекций в схеме».
  3. ^ Энтони Ральстон (2000). Энциклопедия информатики. Природа Паб. Группа. ISBN  978-1-56159-248-7. Получено 11 мая 2013.
  4. ^ В Значок Язык программирования использует генераторы для выполнения своей целевой оценки. В Icon генераторы могут быть вызваны в контекстах за пределами обычных структур управления циклом.
  5. ^ Лисков, Варвара (Апрель 1992 г.). «История КЛУ» (PDF). Архивировано из оригинал (pdf) на 2003-09-17. Получено 2006-01-05.
  6. ^ а б Предложения по усовершенствованию Python:PEP 255: простые генераторы,PEP 289: Генератор выражений,PEP 342: сопрограммы через расширенные генераторы
  7. ^ yield (Справочник по C #)
  8. ^ Лисков, Б .; Снайдер, А .; Аткинсон, Р .; Шафферт, К. (1977). «Механизмы абстракции в CLU». Коммуникации ACM. 20 (8). CiteSeerX  10.1.1.112.656. Дои:10.1145/359763.359789.
  9. ^ «Структурированный параллелизм для C».
  10. ^ http://www.codeproject.com/KB/cpp/cpp_generators.aspx
  11. ^ "Для чего в C # используется ключевое слово yield?". stackoverflow.com. Получено 2018-01-01.
  12. ^ "Некоторые подробности о вычислительных выражениях F #". Получено 2007-12-14.
  13. ^ PEP 380 - Синтаксис для делегирования субгенератору
  14. ^ Генераторные функции в R
  15. ^ http://cartesianfaith.wordpress.com/2013/01/05/infinite-generators-in-r/

Рекомендации

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