В информатике , А генератор является процедурой , которая может быть использована для управления итерацией поведения цикла . Все генераторы также являются итераторами . [1] Генератор очень похож на функцию, возвращающую массив, в том, что генератор имеет параметры, может быть вызван и генерирует последовательность значений. Однако вместо того, чтобы строить массив, содержащий все значения, и возвращать их все сразу, генератор выдает значения по одному, что требует меньше памяти и позволяет вызывающей стороне сразу приступить к обработке первых нескольких значений. Короче говоря, генератор выглядит как функция , но ведет себя какитератор .
Генераторы могут быть реализованы в виде более выразительных конструкций потока управления , таких как сопрограммы или первоклассные продолжения . [2] Генераторы, также известные как полупрограммы, [3] являются частным случаем (и более слабым, чем) сопрограмм, поскольку они всегда возвращают управление вызывающей стороне (при передаче значения обратно), а не указывают сопрограмму для перехода к; см. сравнение сопрограмм с генераторами .
Использует
Генераторы обычно вызываются внутри циклов. [4] При первом вызове генератора в цикле создается объект- итератор, который инкапсулирует состояние подпрограммы генератора в ее начале с аргументами, привязанными к соответствующим параметрам . Затем тело генератора выполняется в контексте этого итератора до тех пор, пока не встретится специальное действие yield ; в это время значение, предоставленное действием yield, используется как значение выражения вызова. В следующий раз, когда тот же вызов генератора будет достигнут на следующей итерации, выполнение тела генератора возобновится после действия yield , пока не встретится еще одно действие yield . В дополнение к действию yield выполнение тела генератора также может быть прекращено действием завершения, когда завершается самый внутренний цикл, включающий вызов генератора. В более сложных ситуациях генератор можно использовать вручную вне цикла для создания итератора, который затем можно использовать по-разному.
Поскольку генераторы вычисляют полученные значения только по запросу, они полезны для представления потоков , таких как последовательности, которые было бы дорого или невозможно вычислить сразу. К ним относятся, например, бесконечные последовательности и потоки данных в реальном времени.
Когда желательна активная оценка (в первую очередь, когда последовательность конечна, иначе оценка никогда не завершится), можно либо преобразовать в список , либо использовать параллельную конструкцию, которая создает список вместо генератора. Например, в Python генератор g
может быть преобразован в список с l
помощью l = list(g)
, тогда как в F # выражение последовательности seq { ... }
вычисляется лениво (генератор или последовательность), но [ ... ]
оценивается быстро (список).
При наличии генераторов конструкции цикла языка, такие как for и while, могут быть сведены к одной конструкции цикла ... end loop; все обычные конструкции цикла можно затем удобно смоделировать, правильно используя подходящие генераторы. Например, ранжированный цикл вроде for x = 1 to 10
может быть реализован как итерация через генератор, как в Python for x in range(1, 10)
. Кроме того, это break
может быть реализовано как отправка финиша генератору с последующим использованием continue
в цикле.
График
Генераторы впервые появились в CLU (1975), [5] были важной особенностью языка обработки строк Icon (1977) и теперь доступны в Python (2001), [6] C # , [7] Ruby , более поздних версиях ECMAScript. (по состоянию на ES6 / ES2015) и на других языках. В CLU и C # генераторы называются итераторами , а в Ruby - счетчиками .
Лисп
Окончательный стандарт Common Lisp изначально не предоставляет генераторы, однако существуют различные реализации библиотек, такие как SERIES, задокументированные в CLtL2 или pygen .
CLU
Оператор yield используется для реализации итераторов над пользовательскими абстракциями данных. [8]
string_chars = iter (s: string) дает (char); индекс: int: = 1; ограничение: int: = строка $ size (s); в то время как индекс <= предел делать yield (строка $ fetch (s, index)); index: = index + 1; конец;конец string_chars;для c: char в string_chars (s) сделать ...конец;
Икона
Каждое выражение (включая циклы) является генератором. Язык имеет множество встроенных генераторов и даже реализует некоторую логическую семантику, используя механизм генератора ( таким образом выполняется логическая дизъюнкция или «ИЛИ»).
Печать квадратов от 0 до 20 может быть достигнута с помощью совместной процедуры, написав:
местные площади, j квадраты: = создать (seq (0) ^ 2) каждый j: = | @squares делать если j <= 20, то написать (j) еще перерыв
Однако в большинстве случаев пользовательские генераторы реализуются с помощью ключевого слова «suspend», которое действует точно так же, как ключевое слово «yield» в CLU.
C
C не имеет функций генератора в качестве языковой конструкции, но, поскольку они являются подмножеством сопрограмм , их легко реализовать с помощью любой инфраструктуры, которая реализует стековые сопрограммы, например libdill. [9] На платформах POSIX, когда стоимость переключения контекста на итерацию не является проблемой или требуется полный параллелизм, а не просто параллелизм , очень простая структура функций генератора может быть реализована с использованием pthreads и конвейеров .
C ++
В C ++ можно ввести генераторы с помощью макросов препроцессора. Полученный код может иметь аспекты, которые сильно отличаются от нативного C ++, но синтаксис генератора может быть очень лаконичным. [10] Набор макросов препроцессора, определенных в этом источнике, разрешает генераторы, определенные с помощью синтаксиса, как в следующем примере:
генератор $ ( спуск ) { int я ; // размещаем конструктор нашего генератора, например // descent (int minv, int maxv) {...} // от $ emit до $ stop - это тело нашего генератора: $ emit ( int ) // выдаст значения типа int. Запуск корпуса генератора. for ( i = 10 ; i > 0 ; - i ) $ yield ( i ); // аналогично yield в Python, // возвращает следующее число в [1..10] в обратном порядке. $ стоп ; // остановка, конец последовательности. Конец корпуса генератора. };
Затем это можно повторить, используя:
int main ( int argc , char * argv []) { спуск ген ; for ( int n ; gen ( n );) // "получить следующий" вызов генератора printf ( "следующее число% d \ n " , n ); возврат 0 ; }
Кроме того, C ++ 11 позволяет цикл просмотр , чтобы быть применен к любому классу , который обеспечивает begin
и end
функцию. Затем можно писать классы, подобные генератору, определяя как итерируемые методы ( begin
и end
), так и методы итератора ( operator!=
, operator++
и operator*
) в одном и том же классе. Например, можно написать следующую программу:
#include int main () { for ( int i : range ( 10 )) { std :: cout << i << std :: endl ; } return 0 ; }
Реализация базового диапазона будет выглядеть так:
диапазон класса { частный : int last ; int iter ;public : range ( int end ) : last ( end ), iter ( 0 ) {} // Итерируемые функции const range & begin () const { return * this ; } const range & end () const { return * this ; } // Функции итератора bool operator ! = ( Const range & ) const { return iter < last ; } недействительный оператор ++ () { ++ iter ; } int оператор * () const { return iter ; } };
Perl
Perl изначально не предоставляет генераторы, но поддержка обеспечивается модулем Coro :: Generator, который использует структуру совместной подпрограммы Coro . Пример использования:
используйте строгий ; использовать предупреждения ; # Включите генератор {BLOCK} и получите использование Coro :: Generator ; # Ссылка на массив для перебора моих $ chars = [ 'A' ... 'Z' ];# Новый генератор, который можно вызвать как coderef. мои $ письма = генератор { мой $ я = 0 ; для моего $ letter ( @ $ chars ) { # получить следующее письмо от $ chars yield $ letter ; } };# Вызвать генератор 15 раз. выведите $ букв -> (), "\ n" для ( 0 .. 15 );
Tcl
В Tcl 8.6 механизм генератора основан на именованных сопрограммах .
proc generator { body } { coroutine gen [ incr :: disambiguator ] apply {{ script } { # Произвести результат [генератора], имя генератора yield [ info coroutine ] # Выполнить генерацию eval $ script # Завершить цикл вызывающего абонента, использующего возврат исключения "break" - code break }} $ body }# Используйте простой цикл for, чтобы вычислить фактическое количество наборов генерации [ генератор { for {set i 10 } { $ i <= 20 } { incr i } { yield $ i } }]# Извлекаем значения из генератора, пока он не будет исчерпан, пока 1 { кладет [ $ count ] }
Haskell
В Haskell с его моделью ленивой оценки все является генератором - все данные, созданные с помощью нестрогого конструктора данных, генерируются по запросу. Например,
countfrom n = n : countfrom ( n + 1 )- Пример использования: распечатка целых чисел от 10 до 20. test1 = mapM_ print $ takeWhile ( <= 20 ) $ countfrom 10primes = 2 : 3 : nextprime 5, где nextprime n | b = n : nextprime ( n + 2 ) | в противном случае = nextprime ( n + 2 ), где b = all (( / = 0 ) . ( rem n )) $ takeWhile (( <= n ) . ( ^ 2 )) $ tail primes
где (:)
- нестрогий конструктор списка, cons и $
просто оператор «вызываемого с помощью» , используемый для заключения в скобки. Здесь используется стандартная функция адаптера,
takeWhile p [] = [] takeWhile p ( x : xs ) | p x = x : takeWhile p xs | в противном случае = []
который повторно выбирает значения, согласующиеся с предикатом, и прекращает запрашивать новые значения, как только обнаруживается несовместимое. Доступ к общему хранилищу используется в Haskell как универсальный посредник. Понимание списков можно свободно использовать:
test2 = mapM_ print $ takeWhile ( <= 20 ) [ x * x | x <- countfrom 10 ] test3 = mapM_ print [ x * x | x <- takeWhile ( <= 20 ) $ countfrom 10 ]
Ракетка
Racket предоставляет несколько связанных возможностей для генераторов. Во-первых, его формы цикла for работают с последовательностями , которые являются своего рода продюсерами:
( для ([ i ( in-range 10 20 )]) ( printf "i = ~ s \ n " i ))
и эти последовательности также являются первоклассными ценностями:
( определите от 10 до 20 ( в диапазоне от 10 до 20 )) ( для ([ i от 10 до 20 ]) ( printf "i = ~ s \ n " i ))
Некоторые последовательности реализованы императивно (с переменными частного состояния), а некоторые реализованы как (возможно, бесконечные) ленивые списки. Кроме того, новые определения структур могут иметь свойство, указывающее, как их можно использовать в качестве последовательностей.
Но если говорить более конкретно, Racket поставляется с библиотекой генератора для более традиционной спецификации генератора. Например,
#lang racket ( требуется ракетка / генератор ) ( define ( ints-from from ) ( generator () ( for ([ i ( in-naturals from )]) ; бесконечная последовательность целых чисел от 0 ( yield i )))) ( define г ( целые-из 10 )) ( список ( г ) ( г ) ( г )) ; -> '(10 11 12)
Обратите внимание, что ядро Racket реализует мощные функции продолжения, обеспечивая общие (повторно входящие) продолжения, которые можно компоновать, а также разграниченные продолжения. Используя это, в Racket реализована библиотека генератора.
PHP
Сообщество PHP реализовало генераторы в PHP 5.5. Подробности можно найти в исходном запросе комментариев: генераторы .
Бесконечная последовательность Фибоначчи:
функция fibonacci () { $ last = 0 ; $ current = 1 ; yield 1 ; while ( истина ) { $ current = $ last + $ current ; $ last = $ current - $ last ; yield $ current ; } }foreach ( fibonacci () as $ number ) { echo $ number , " \ n " ; }
Последовательность Фибоначчи с пределом:
функция fibonacci ( int $ limit ) : генератор { yield $ a = $ b = $ i = 1 ; while ( ++ $ i < $ limit ) { yield $ a = ( $ b = $ a + $ b ) - $ a ; } }foreach ( фибоначчи ( 10 ) как $ число ) { эхо " $ число \ п " ; }
Любая функция, которая содержит оператор yield, автоматически становится функцией генератора.
Рубин
Ruby поддерживает генераторы (начиная с версии 1.9) в виде встроенного класса Enumerator.
# Генератор из объекта перечислителя chars = Enumerator . новый ( [ 'A' , 'B' , 'C' , 'Z' ] )4 . раз { помещает символы . следующий }# Генератор от блока подсчета = Enumerator . новый делать | уроженец | i = 0 loop { yielder . yield i + = 1 } конец100 . раз { ставит счет . следующий }
Ява
С самого начала в Java был стандартный интерфейс для реализации итераторов, а начиная с Java 5 конструкция «foreach» позволяет легко перебирать объекты, обеспечивающие java.lang.Iterable
интерфейс. ( Фреймворк коллекций Java и другие фреймворки коллекций обычно предоставляют итераторы для всех коллекций.)
Однако в Java нет встроенных генераторов. Это означает, что создание итераторов часто намного сложнее, чем в языках со встроенными генераторами, особенно когда логика генерации сложна. Поскольку все состояние должно сохраняться и восстанавливаться каждый раз, когда элемент должен быть получен из итератора, невозможно сохранить состояние в локальных переменных или использовать встроенные процедуры цикла, как когда доступны генераторы; вместо этого все это необходимо моделировать вручную, используя поля объекта для хранения локального состояния и счетчиков циклов.
Даже простые итераторы, построенные таким образом, имеют тенденцию быть значительно более громоздкими, чем те, которые используют генераторы, с большим количеством шаблонного кода .
Исходный пример выше может быть записан на Java 5 как:
// Итератор реализован как анонимный класс. Здесь используются дженерики, но в этом нет необходимости. for ( int i : new Iterable < Integer > () { @Override public Iterator < Integer > iterator () { return new Iterator < Integer > () { int counter = 1 ; @Override public boolean hasNext () { return counter <= 100 ; } @Override public Integer next () { return counter ++ ; } @Override public void remove () { бросить новое исключение UnsupportedOperationException (); } }; } }) { System . из . println ( я ); }
Бесконечную последовательность Фибоначчи также можно записать в Java 5 как итератор:
Iterable < Integer > fibo = new Iterable < Integer > () { @Override public Iterator < Integer > iterator () { return new Iterator < Integer > () { int a = 1 , b = 2 ; @Override public boolean hasNext () { return true ; } @Override public Integer next () { int temp = a ; а = б ; б = а + темп ; возвратная температура ; } @Override public void remove () { бросить новое исключение UnsupportedOperationException (); } }; } }; // затем это можно было бы использовать как ... for ( int f : fibo ) { System . из . println ( "следующее число Фибоначчи" + f ); if ( someCondition ( f )) перерыв ; }
Также бесконечная последовательность Фибоначчи может быть написана с использованием интерфейса Java 8 Stream:
IntStream . генерировать ( новый IntSupplier () { int a = 1 , b = 2 ; общедоступный int getAsInt () { int temp = a ; а = б ; б = а + темп ; возвратная температура ; } }). forEach ( System . out :: println );
Или получите Iterator из интерфейса BaseStream of Stream супер-интерфейса Java 8 .
public Iterable < Integer > fibonacci ( int limit ) { return IntStream . генерировать ( новый IntSupplier () { int a = 1 , b = 2 ; общедоступный int getAsInt () { int temp = a ; а = б ; б = а + темп ; возвратная температура ; } }). limit ( предел ). boxed () :: iterator ; }// затем это можно было бы использовать как ... for ( int f : fibonacci ( 10 )) { System . из . println ( f ); }
C #
Пример генератора C # 2.0 ( yield
доступен, начиная с версии C # 2.0): в обоих этих примерах используются универсальные шаблоны, но это не требуется. Ключевое слово yield также помогает в реализации настраиваемых итераций с отслеживанием состояния по коллекции, как обсуждалось в этом обсуждении. [11]
// Метод, который принимает итеративный ввод (возможно, массив) // и возвращает все четные числа. общедоступный статический IEnumerable < int > GetEven ( IEnumerable < int > numbers ) { foreach ( int number в числах ) { if (( number % 2 ) == 0 ) { yield return number ; } } }
Можно использовать несколько yield return
операторов, и они применяются последовательно на каждой итерации:
открытый класс CityCollection : IEnumerable < строка > { общедоступный IEnumerator < строка > GetEnumerator () { yield return «Нью-Йорк» ; yield return "Париж" ; доходность доходность «Лондон» ; } }
XL
В XL итераторы являются основой циклов for:
импорт IO = XL.UI.CONSOLEiterator IntegerIterator (var out Counter: integer; Low, High: integer) записывает Counter в Low..High Счетчик: = Низкий в то время как счетчик <= высокий цикл урожай Счетчик + = 1// Обратите внимание, что меня не нужно объявлять, потому что в итераторе объявлено 'var out'// Поэтому здесь делается неявное объявление I как целого числадля I в 1..5 петле IO.WriteLn "I =", I
F #
F # предоставляет генераторы через выражения последовательности , начиная с версии 1.9.1. [12] Они могут определять последовательность (ленивое вычисление, последовательный доступ) через seq { ... }
, список (быстро оцениваемый, последовательный доступ) через [ ... ]
или массив (быстро оцениваемый, индексированный доступ) через, [| ... |]
которые содержат код, генерирующий значения. Например,
seq { for b in 0 .. 25 do if b < 15 then yield b * b }
образует последовательность квадратов чисел от 0 до 14, отфильтровывая числа из диапазона чисел от 0 до 25.
Python
Генераторы были добавлены в Python в версии 2.2 в 2001 году. [6] Пример генератора:
от ввода import Iteratordef countfrom ( n : int ) -> Iterator [ int ]: while True : yield n n + = 1# Пример использования: вывод целых чисел от 10 до 20. # Обратите внимание, что эта итерация завершается нормально, несмотря на то, что # countfrom () записывается как бесконечный цикл.for i в countfrom ( 10 ): if i <= 20 : print ( i ) else : break# Другой генератор, который производит неограниченное количество простых чисел по мере необходимости. импортировать itertoolsdef primes () -> Iterator [ int ]: yield 2 n = 3 p = [] while True : # При делении n на все числа в p, вплоть до sqrt (n) включительно, # дает ненулевой остаток тогда n простое. if all ( n % f > 0 для f в itertools . takewhile ( lambda f : f * f <= n , p )): вывести n p . добавить ( п ) п + = 2
В Python генератор можно рассматривать как итератор , содержащий замороженный кадр стека . Всякий раз, когда next()
вызывается итератор, Python возобновляет замороженный фрейм, который обычно выполняется до тех пор, пока не yield
будет достигнут следующий оператор. Затем кадр генератора снова замораживается, и полученное значение возвращается вызывающей стороне.
PEP 380 (реализованный в Python 3.3) добавляет yield from
выражение, позволяя генератору делегировать часть своих операций другому генератору или итерируемому. [13]
Генератор выражений
Python имеет синтаксис, смоделированный на основе синтаксиса списков , называемый выражением генератора, который помогает в создании генераторов. Следующее расширяет первый пример выше, используя выражение генератора для вычисления квадратов из countfrom
функции генератора:
квадраты = ( n * n для n в countfrom ( 2 ))для j в квадратах : if j <= 20 : print ( j ) else : break
ECMAScript
ECMAScript 6 (он же Harmony) представил функции генератора.
Бесконечную последовательность Фибоначчи можно записать с помощью генератора функций:
функция * fibonacci ( предел ) { let [ prev , curr ] = [ 0 , 1 ]; while ( ! limit || curr <= limit ) { yield curr ; [ предыдущая , текущая ] = [ текущая , предыдущая + текущая ]; } }// ограничено верхним пределом 10 для ( const n из fibonacci ( 10 )) { console . журнал ( п ); }// генератор без верхней границы для ( const n из fibonacci ()) { console . журнал ( п ); если ( n > 10000 ) перерыв ; }// итерация вручную let fibGen = fibonacci (); консоль . журнал ( fibGen . next (). value ); // 1 консоль . журнал ( fibGen . next (). value ); // 1 консоль . журнал ( fibGen . next (). value ); // 2 консоли . журнал ( fibGen . next (). value ); // 3 консоль . журнал ( fibGen . next (). value ); // 5 консоль . журнал ( fibGen . next (). value ); // 8// берет с того места, где вы остановились для ( const n из fibGen ) { console . журнал ( п ); если ( n > 10000 ) перерыв ; }
р
Для этого можно использовать пакет итераторов. [14] [15]
библиотека ( итераторы )# Пример ------------------ abc <- iter ( c ( 'a' , 'b' , 'c' )) nextElem ( abc )
Болтовня
Пример в Pharo Smalltalk :
Золотое сечение генератор ниже возвращается в каждый вызов «золотого сечение следующего» лучшее приближение к золотому сечению.
золотое сечение : = Генератор на: [ : г | | xyzr | х : = 0 . у : = 1 .[ г : = х + у . r : = ( z / y ) asFloat . х : = у . у : = z . g yield: r ] повтор
] .goldenRatio следующий .
Выражение ниже возвращает следующие 10 приближений.
Персонаж cr присоединяется: ((от 1 до: 10 ) collect: [ : dummy | ratio next ]) .
Подробнее см . Скрытый камень в Pharo: Generator .
Смотрите также
- Понимание списка для другой конструкции, которая генерирует последовательность значений
- Итератор концепции создания списка по одному элементу за раз
- Итеративная альтернатива
- Ленивая оценка для получения значений при необходимости
- Corecursion для потенциально бесконечных данных путем рекурсии вместо yield
- Coroutine для еще большего обобщения подпрограммы
- Продолжение обобщения потока управления
Заметки
- ^ В чем разница между итератором и генератором?
- ↑ Киселев, Олег (январь 2004 г.). «Общие способы обхода коллекций в схеме» .
- ^ Энтони Ральстон (2000). Энциклопедия информатики . Природа Паб. Группа. ISBN 978-1-56159-248-7. Проверено 11 мая 2013 года .
- ^ Язык программирования иконок использует генераторы для реализации целенаправленной оценки. В Icon генераторы могут быть вызваны в контекстах за пределами обычных структур управления циклом.
- ^ Лисков, Варвара (апрель 1992 г.). «История CLU» (PDF) . Архивировано из оригинального (pdf) 17 сентября 2003 года . Проверено 5 января 2006 .
- ^ a b Предложения по расширению Python: PEP 255: простые генераторы , PEP 289: выражения генератора , PEP 342: сопрограммы через расширенные генераторы
- ^ yield (Справочник по C #)
- ^ Лисков, Б .; Снайдер, А .; Аткинсон, Р .; Шафферт, К. (1977). «Механизмы абстракции в CLU». Коммуникации ACM . 20 (8). CiteSeerX 10.1.1.112.656 . DOI : 10.1145 / 359763.359789 .
- ^ «Структурированный параллелизм для C» .
- ^ http://www.codeproject.com/KB/cpp/cpp_generators.aspx
- ^ "Для чего в C # используется ключевое слово yield?" . stackoverflow.com . Проверено 1 января 2018 .
- ^ «Некоторые подробности о вычислительных выражениях F #» . Проверено 14 декабря 2007 .
- ^ PEP 380 - Синтаксис для делегирования субгенератору
- ^ Функции генератора в R
- ^ http://cartesianfaith.wordpress.com/2013/01/05/infinite-generators-in-r/
Рекомендации
- Стефан Мурер, Стивен Омохундро , Дэвид Статамир и Клеменс Шиперски: Итерационная абстракция в Sather . Транзакции ACM по языкам и системам программирования , 18 (1): 1-15 (1996) [1]