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

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

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

Содержание

• 1 Использует
• 2 Временная шкала
  • 2.1 Lisp
  • 2.2 CLU
  • 2.3 Значок
  • 2.4 C
  • 2.5 C ++
  • 2.6 Perl
  • 2.7 Tcl
  • 2.8 Haskell
  • 2.9 Racket
  • 2.10 PHP
  • 2.11 Ruby
  • 2.12 Java
  • 2.13 C #
  • 2.14 XL
  • 2.15 F #
  • 2.16 Python
    • 2.16.1 Генератор выражений
  • 2.17 ECMAScript
  • 2.18 R
  • 2.19 Smalltalk
• 3 См. Также
• 4 Примечания
• 5 Ссылки

Использует

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

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

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

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

Временная шкала

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

Lisp

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

CLU

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

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

Icon

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

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

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

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

C

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

C ++

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

$ generator (descent) {int i; // размещаем конструктор нашего генератора, например // 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) {descent gen; for (int n; gen (n);) // "получить следующий" вызов генератора printf ("следующее число% d \ n", n); возврат 0; }

Более того, C ++ 11 позволяет применять циклы foreach к любому классу, который предоставляет функции 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; } void operator++() { ++iter; } int operator*() const { return iter; } };

Perl

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

use strict; использовать предупреждения; # Включить генератор {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' return -code break}} $ body} # Используйте простой цикл for для подсчета фактического набора генерации [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

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

countfrom n = n: countfrom (n + 1) - Пример использования: распечатка целых чисел от 10 до 20. test1 = mapM_ print $ takeWhile (<= 20) $ countfrom 10 primes = 2 : 3 : nextprime 5 where nextprime n | b = n : nextprime (n+2) | otherwise = nextprime (n+2) where b = all ((/= 0).(rem n)) $ takeWhile ((<= n).(^2)) $ tail primes

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

takeWhile p = takeWhile p (x : xs) | px = x: takeWhile p xs | else =

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

test2 = mapM_ print $ takeWhile (<= 20) [x*x | x <- countfrom 10] test3 = mapM_ print [x*x | x <- takeWhile (<= 20) $ countfrom 10]

Racket

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

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

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

(определить от 10 до 20 (в диапазоне 10 20)) (для ([i 10-to-20]) (printf "i = ~ s \ n" i))

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

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

#lang racket (требуется racket / generator) (define (ints-from from) (generator () (for ([i (in-naturals from)]); бесконечная последовательность целых чисел от 0 (yield i)))) (определить g (ints-from 10)) (list (g) (g) (g)); ->'(10 11 12)

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

PHP

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

function fibonacci () {$ last = 0; $ current = 1; yield 1; while (истина) {$ current = $ last + $ current; $ last = $ current - $ last; yield $ current; }} foreach (fibonacci () as $ number) {echo $ number, "\ n"; }

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

Ruby

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

# Генератор из объекта Enumerator chars = Enumerator.new (['A', 'B', 'C', 'Z']) 4 раза {помещает chars.next} # Генератор из блока count = Enumerator.new do | yielder | i = 0 loop {yielder.yield i + = 1} end 100.times {put count.next}

Java

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

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

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

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

// Итератор реализован как анонимный класс. Здесь используются дженерики, но в этом нет необходимости. for (int i: new Iterable () {@Override public Iterator iterator () {return new Iterator () {int counter = 1; @Override public boolean hasNext () {return counter <= 100; } @Override public Integer next() { return counter++; } @Override public void remove() { throw new UnsupportedOperationException(); } }; } }) { System.out.println(i); }

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

Iterable fibo = new Iterable () {@Override public Iterator iterator () { return new Iterator () {int a = 1, b = 2; @Override public boolean hasNext () {return true;} @Override public Integer next () {int temp = a; a = b; b = a + temp; return temp;} @Override public void remove () {throw new UnsupportedOperationException ();}};}}; // затем это можно было бы использовать как... for (int f: fibo) {System.out. println ("следующее число Фибоначчи -" + f); if (someCondition (f)) break;}

Также можно записать бесконечную последовательность Фибоначчи с использованием Java 8 Stream interface:

IntStream.generate (new IntSupplier () {int a = 1, b = 2; public int getAsInt () {int temp = a; a = b; b = a + temp; return temp;}}). для Каждый (System.out :: println);

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

public Iterable fibonacci (int limit) {return IntStream.generate (new IntSupplier () {int a = 1, b = 2; public int getAsInt () {int temp = a; a = b; b = a + temp; return temp;}}). limit (предел).boxed () :: iterator; } // затем это можно было бы использовать как... for (int f: fibonacci (10)) {System.out.println (f); }

C #

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

// Метод, который принимает итеративный ввод (возможно, массив) // и возвращает все четные числа. общедоступный статический IEnumerable GetEven (IEnumerable числа) {foreach (int i в числах) {if ((i% 2) == 0) {yield return i; }}}

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

открытый класс CityCollection: IEnumerable {public IEnumerator GetEnumerator () {yield return "Нью-Йорк"; yield return "Париж"; yield return "Лондон"; }}

XL

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

import IO = XL.UI.CONSOLE iterator IntegerIterator (var out Counter: integer ; Low, High: целое число) в поле Counter записано значение Low..High равно Counter: = Low, а 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 #

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

seq {для b в 0.. 25 do, если b < 15 then yield b * b }

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

Python

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

от ввода import Iterator def countfrom (n: int) ->Iterator [int] : while True: yield nn + = 1 # Пример использования: печать целых чисел от 10 до 20. # Обратите внимание, что эта итерация завершается нормально, несмотря на то, что # countfrom () записывается как бесконечный цикл. 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]: 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)): yield n p.append(n) n += 2

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

squares = (n * n для n в countfrom (2)) для j в квадратах: if j <= 20: print(j) else: break

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; } // итерация вручную let fibGen = fibonacci (); console.log (fibGen.next (). значение); // 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 // начинается с того места, где вы остановились на (const n из fibGen) {console.log (n); если (n>10000) перерыв; }

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

goldenRatio: = Генератор включен: [: g | | x y z r | x: = 0. y: = 1. [z: = x + y. r: = (z / y) asFloat. х: = у. у: = z. g yield: r] повтор]. goldenRatio следующий.

Персонаж cr join: ((от 1 до: 10) collect: [: dummy | ratio next]).