Генератор (рачунарство)
У рачунарству, генератор је специјални потпрограм који може бити употребљен за контролу итерацијског понашања понављања . У суштини, сви генератори су итератори.[1] Генерартор је веома сличан функцији која враћа низ, у којој генератор има параметре, која се може позвати, и генерисати секвенцу вредности. Међутим, уместо да се прави низ који садржи све те елементе и и враћа све њих, позив генератора враћа једну и само једну вредност, што захтева мање меморије и допушта програмеру да почне са процесуирањем првих неколико вредности одмах. Укратко, генератор личи на функцију али се понаша као итератор.
Генератори могу бити имплементирани у погледу брже конструкције контроле протока, као што су корутине или настављање прве-класе.[2] Генератори, такође познати као полу-корутине,[3] су специјални случај (и слабији од) корутина, у смислу да увек дају повратну контролу програмеру (када се враћа вредност), уместо да одреди путању корутини, видети компарација корутина са гераторима.
Употреба
[уреди | уреди извор]Генератори се углавном извршавају унутар петље. Први пут када се генератор изврши у петљи, итереторни објекат је креиран да енкапсулира стање генератора на његовом почетку, са аргументима везаних за одговарајуће параметре. Тело генератора је тада извршавано у виду итератора све до „yield“ наредбе; тада је вредност обезбеђена операцијом „yield' коришћена као вредност призваног израза. Слећи пут када се позове генератор у накнадној итерацији, извршавање тела генератора се наставља након операције „yield“, све док не дође до следеће „yield“ операције. У прилог операцији „yield“, извршавање тела генератора се може завршити уз помоћ „finish“ наредбе, у којој се прекида понављање у петљи генератора. У много компликованијим ситуацијама, генератори могу бити коришћени изван петље да би се направила итерација, која онда може бити употребљена на разне начине.
Пошто генератори извршавају њихове дате вредности само на позив функције "yield“, корисни су за представљање тока, као секвенце које би биле скупе или немогуће за извршавање одједном. Ово укључује нпр. бесконачан број секвенци и токова података.
Када је жељена процена пожељна (првенстветно када је секвенца коначна, јер се у супротном евалуације никад неће извршити), један може да се конвертује у листу, или да се користи као паралелни конструктор који креира листу уместо генератора. На пример у Пајтону генератор g
може бити означен листом l
као l = list(g)
, док се у F# експресија секвенци seq { ... }
извршава споро (генератор или секвенца) али [ ... ]
се извршава ефикасније и пожељније (листа).
У присуству генератора, конструкција петље програма- као што су for и while- може бити редукована у једну петљу...крај конструкције петље; све обично коришћене конструкције петљи могу бити стимулисане користећи исправно погодан генератор . На пример, рангирана петља као што је for x = 1 to 10
може бити имплементирана као итерација кроз генератор, као и у Пајтону for x in xrange(10, 1)
. Осим тога, break
може бити имплементирана тако што шаље наредбу крај генератору и после тога користећи continue
у петљи.
Изглед
[уреди | уреди извор]Генератори су се прво појавили у ЦЛУ (1975),[4] где је истакнута одлика у виду манипулације стринга у програмском језику Icon (Ајкон) (1977) а сада је доступна у Пајтону,[5] C#,[6] Руби, надолазећој верзији ЕЦМАСкрипт (Хармонија/EС6) и другим програмима. У ЦЛУ и C#, генератори се називају „итератори“, а у програмском језику Руби, "енумератори".
Лисп
[уреди | уреди извор]Коначни Заједнички Лисп не подржава природно генераторе, још постоји варирајућа библиотека имплементација, као што су СЕРИЈЕ документоване у ЦЛтЛ2 или пајгену (pygen).
ЦЛУ (CLU)
[уреди | уреди извор]Yield функција је коришћена да имплементира итераторе преко корисничко-дефинисане апстракције података .[7]
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;
Ајкон (Icon)
[уреди | уреди извор]Свака експресија (укључујући петље) је генератор. Програм има много уграђених генератора, чак и неке логичко семантичке имплементације користе механизам генератора (Дисјункција или "ИЛИ" је урађена тако).
Штампање квадрата од 0 до 20 се постиже користећи ко-рутине, пишући:
Међутим, углавном се жељени генератори имплементирају са суспендованом кључном речју са функцијама као што је yield кључна реч у ЦЛУ.
C++
[уреди | уреди извор]Могуће је увести генераторе у C++ користећи пре-процесорске макрое. Резултирајући код може имати аспекте различите од природе C++, али синтакса генератора може бити врло неоптерећена. Веома добар пример се може наћи на.[8] Комплет препроцесорских макроа дефинисаних у овом коду дозвољава генераторе дефинисаних синтаксама као у следећем примеру :
$generator(descent)
{
// место за све вредности коришћене у генератору
int i; // наш бројач
// место конструкције нашег генератора, нпр.
// вредност (int minv, int maxv) {...}
// од $(emit)емитовања до $(stop)стоп је тело нашег генератора:
$emit(int) // ће емитовати целобројне вредности. Поћетак тела генератора:
for (i = 10; i > 0; --i)
$yield(i); // познато као yield у Пајтону,
// враћа следећи број у [1..10], преокренут.
$stop; // стоп, крај секвенце. Крај тела генератора.
};
Ово може бити извршено користећи:
int main(int argc, char* argv[])
{
descent gen;
for(int n; gen(n);) // "следећи" позив генератора
printf("next number is %d\n", n);
return 0;
}
Штавише, C++11 дозвољава свакој петљи да буде примењена у било којој класи која подржава begin
и end
функције. Онда је могуће написати генератор као класе уз помоћ обе мерне методе (begin
and end
) и итеративне методе (operator!=
, operator++
and operator*
) у истој класи. На пример, могуће је написати следећи прорам:
#укључујући <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)
{}
// Мерне функције
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)
[уреди | уреди извор]Перл нема природно уграђене генераторе, али подржавање је спонзорисано од стране Коро Генератора модул који користи Коро ко-рутине оквир. Пример коришћења.
користити стриктно;
користити упозорења;
# Активирати генератор { BLOCK } и ''yield''
користити Коро::Генератор;
# Низ упућује на извршавање преко мојих $знакова = ['A'...'Z'];
# Нови генератор се може назвати ''coderef''.
my $letters = generator {
my $i = 0;
for my $letter (@$chars) {
# узми следеће слово од $chars
yield $letter;
}
};
# Позови генератор 15 пута.
print $letters->(), "\n" for (0..15);
Тцл (Tcl)
[уреди | уреди извор]У Тцл-y 8.6, механизам генератора почива на именовању корутина.
proc generator {body} {
coroutine gen[incr ::disambiguator] apply {{script} {
# продукује резултат [генератора], име генератора
yield [info corutine]
# Уради стварање
eval $script
# Завршити петљу позива користећи 'break' изузетак.
return -code break
}} $body
}
# Користити једноставну 'for' петљу за стварање
set count[generator {
for {set i 10} {$i <= 20} {incr i} {
yield $i
}
}]
# Извлачи вредности из генератора док се не исцрпе
while 1 {
puts [$count]
}
Хаскел (Haskell)
[уреди | уреди извор]У Хаскелу, са спорим одређивањем врдности моделом, све је генератор- сваки датум креиран са не-строгом конструкцијом података је генерисан на захтев. На пример,
countfrom n = n : countfrom (n+1)
-- Example use: printing out the integers from 10 to 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
где је (:)
не-строга листа конструктора, против, и $
је само "позови-са" оператор, коришћен за парентизацију. Ово користи стандарни адаптор функција,
takeWhile p [] = []
takeWhile p (x:xs) | p x = x : takeWhile p xs
| otherwise = []
чије се поновно пронађене вредности слажу са исказом, и престају са тражењем нових вредности чим се изврши једна неодговарајућа вредност. Приступ заједничком складишту је коришћено као универзалан посредник у Хаскелу. Листа схватања може бити бесплатно коришћена:
test2 = mapM_ print $ takeWhile (<= 20) [x*x | x <- countfrom 10]
test3 = mapM_ print [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))
Неке секвенце су императивно имплементиране (са скривеним вредностима варијабли) а неке су имплементиране као (вероватно бесконачне) лење листе. Такође, нова структура дефиниције може имати моћ која одређује како се могу користити као секвенце. Али више директно, Ракет има лабораторију генератора за традиционалну спецификацију генератора. На пример,
#''ланг'' ракет
(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)
Приметити да Ракетово језгро имплементира снажну понављајућу карактеристику, обезбеђујући општа понављања која су компатибилна али такође и ограничена. Користећи ово, библиотека генератора је имплементирана у Ракету.
PHP (PHP)
[уреди | уреди извор]Заједница PHP-a је имплементирала генераторе у PHP 5.5. Детаљи се могу порнаћи на РФЦ о генераторима.
function fibonacci() {
$last = 0;
$current = 1;
yield 1;
while (true) {
$current = $last + $current;
$last = $current - $last;
yield $current;
}
}
foreach (fibonacci() as $number) {
echo $number, "\n";
}
Руби (Ruby)
[уреди | уреди извор]Руби подржава генераторе (почевши од верзије 1.9) у форми уграђене Енумераторске класе.
# Генератор из Енумераторског објекта
chars = Enumerator.new(['A', 'B', 'C', 'Z'])
4.times { puts chars.next }
# Генератор из блока
count = Enumerator.new do |yielder
| i = 0
loop { yielder.yield i += 1 }
end
100.times { puts count.next }
Јава
[уреди | уреди извор]Јава је имала стандардни приступ за имплементирање итератора још од раних својих дана, и од Јаве 5, foreach конструкција чини то лакшим за понављање преко објеката које омогућава java.lang.Iterable приступ. ( Оквир јава колекције и остале оквирне колекције, производе итераторе за све колекције.)
Међутим, Јава нема уграђене генераторе. Ово значи да је креирање итератора чешће много компликованије него у програмима који имају уграђене генераторе, поготово када је стварање комплексно. Због тога што се све вредности морају снимити и сачувати сваки пут када се позове ствар из итератора, није могуће сачувати вредности у локалним варијаблама или користити уграђену понављачку рутину, као када су генератори доступни; уместо тога, све ово мора бити манално симулирано, користећи поља да чува локалну вредност и број понављања.
Чак и једноставни итератори изграђени на овај начин имају теденцију да буду значајно гломазнији од оних који користе генератори, са много општенаменских кодова.
Оригиналан пример се може написати у Јава 7 као:
// Итератор је имплементиран као анонимна класа. Ово се користи генерички али није потребно.
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() {
throw new UnsupportedOperationException();
}
};
}
}) {
System.out.println(i);
}
Бесконачна Фибоначијева секвенца се такође може маписати као итератор у Јава 7:
Iterable<Integer> fibo = new Iterable<Integer>() {
@Override
public Iterator<Integer> iterator() {
return new Iterator<Integer>() {
int a = 1, b = 1;
int total;
@Override
public boolean hasNext() {
return true;
}
@Override
public Integer next() {
total = a + b;
a = b;
b = total;
return total;
}
@Override
public void remove() {
throw new UnsupportedOperationException();
}
};
}
};
// ово се затим може користити као...
for (int f: fibo) {
System.out.println("next Fibonacci number is " + f);
if (someCondition(f)) break;
}
Такође, бесконачна Фибоначијева секвенца се може написати и у Јава 8 користећи ток приступа:
Stream.generate(new Supplier<Integer>() {
int a = 1, b = 2;
public Integer get() {
int temp = a;
a = b;
b = a + temp;
return temp;
}
}).forEach(System.out::print);
Или као итератор из Јава 8 супер-приступа ОсновногТока тока приступа.
public Iterable<Integer> fibonacci(int limit){
return ()->{
return Stream.generate(new Supplier<Integer>() {
int a = 1, b = 2;
public Integer get() {
int temp = a;
a = b;
b = a + temp;
return temp;
}
}).limit(limit).iterator();
}
}
// ово се затим може користити као...
for (int f: fibonacci(10)) {
System.out.println(f);
}
C#
[уреди | уреди извор]Пример C# 2.0 генератора ( yield
је достушам од C# верзије 2.0):
Оба ова примера се користе генерички, али не морају.
// Метода која узима мерни улаз (вероватно низ)
// и враћа све парне бројеве.
public static IEnumerable<int> GetEven(IEnumerable<int> numbers) {
foreach (int i in numbers) {
if ((i % 2) == 0) {
yield return i;
}
}
}
Могуће је користити више пута yield return
функцију и оне се налазе у секвенци сваке итерације:
public class CityCollection : IEnumerable<string> {
public IEnumerator<string> GetEnumerator() {
yield return "New York";
yield return "Paris";
yield return "London";
}
}
ХЛ(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
// Приметити да I не треба да буде декларисано, због декларисаног ''var out'' у итератору
// Имплицитна декларација I као целобројна вредност је направљена овде
for I in 1..5 loop
IO.WriteLn "I=", I
F#
[уреди | уреди извор]F# садржи генераторе преко експресија секвенце, од верзије1.9.1.[9] Ово може дефинисати секвенцу (спору, секвенцијалног приступа) преко seq { ... }
, листе (брза, секвенцијалног приступа) преко [ ... ]
или низа (брз, индексног приступа) преко [| ... |]
која садржи код који генерише вредности. На пример,
seq { for b in 0 .. 25 do
if b < 15 then
yield b * b }
форма секвенце квадрата бројева од 0 до 14, испитивањем бројева у распону од 0. до 25.
Пајтон (Python)
[уреди | уреди извор]Генератори су додати у Пајтон у верзији 2.2.[5] Пример генератора:
def countfrom(n):
while True:
yield n
n += 1
# Пример: штампа целобројне вредности од 10 до 20
# Приметити да се ова итерација престаје са извршавањем нормално, упркос
# countfrom() је написана као бесконачна петља.
for i in countfrom(10):
if i <= 20:
print(i)
else:
break
# Још један генератор, који производи просте бојеве неограничено, тј. колико је нама потребно.
def primes():
yield 2
n = 3
p = []
while True:
# Ово ради у Пајтоновим верзијама 2.5+
if not any(n % f == 0 for f in
itertools.takewhile(lambda f: f*f <= n, p)):
yield n
p.append(n)
n += 2
У Пајтону, генератор може бити мисао итератора који садржи непроменљив (залеђен) оквир складишта . Кад год је итераторова next()
метода позвана, Пајтон наставља непроменљив оквир, који се извршава нормално све док не стигне до yield
функције. Генераторов оквир је залеђен поново, и позвана вредност је враћена позиваоцу (кориснику).
ПЕП (PEP) 380 (убачен у Пајтон 3.3) додаје yield from експресију, која дозвољава генератору да проверава део његових операциа за други генератор .[10]
Експресије Генератора
[уреди | уреди извор]Пајтон има моделирану синтаксу по узору на листу спознаја, која се назива експресија генератора и која помаже у креирању генератора. Следећи пример показује коришћење експресије генератора да се израчуна квадрат из бројача (функције генератора):
squares = ( n*n for n in countfrom(2) )
for j in squares:
if j <= 20:
print(j)
else:
break
ЕЦМАСкрипт (ECMAScript)
[уреди | уреди извор]ЕЦМАСкрипт 6 (позната као Хармонија) ће имати функције генератора.
Бесконачна Фибоначијева секвецна се може написати користећи функцију генератора:
// инспирисано од стране: http://wiki.ecmascript.org/doku.php?id=harmony:generators
function* fibonacci() {
let [prev, curr] = [0, 1];
while (true) {
yield curr;
[prev, curr] = [curr, prev + curr];
}
}
var gen = fibonacci();
console.log(gen.next().value); // 1
console.log(gen.next().value); // 1
console.log(gen.next().value); // 2
console.log(gen.next().value); // 3
console.log(gen.next().value); // 5
console.log(gen.next().value); // 8
Види још
[уреди | уреди извор]- Листа жеља за остале конструкције које садрже секвенце вредности
- Итератор за концепт стварања једног елемента листе у времену
- Итерејтее за алтернативу
- Спора додела вредности за производњу вредности када су потребне
- Ко-рекурзија за потенцијално бесконачну вредност уз помоћ рекурзије уместо "yield"
- Корутине за још већу генерализовацију од сабрутине
- Настављање за генерализацију контроле протока
Референце
[уреди | уреди извор]- ^ What is the difference between an Iterator and a Generator? - Stack Overflow
- ^ Kiselyov, Oleg (January 2004).
- ^ Ralston, Anthony (2000). Encyclopedia of computer science. Nature Pub. Group. ISBN 978-1-56159-248-7. Приступљено 11. 5. 2013.
- ^ Liskov, Barbara (April 1992).
- ^ а б Python Enhancement Proposals: PEP 255: Simple Generators, PEP 289: Generator Expressions, PEP 342: Coroutines via Enhanced Generators
- ^ yield (C# Reference)
- ^ Liskov, B.; Snyder, A.; Atkinson, R.; Schaffert, C. (1977).
- ^ [„Generators in C++ - CodeProject[[Категорија:Ботовски наслови]]”. Архивирано из оригинала 07. 02. 2019. г. Приступљено 22. 11. 2015. Сукоб URL—викивеза (помоћ) Generators in C++ - CodeProject]
- ^ "Some Details on F# Computation Expressions".
- ^ PEP 380 -- Syntax for Delegating to a Subgenerator
Литература
[уреди | уреди извор]- Ralston, Anthony (2000). Encyclopedia of computer science. Nature Pub. Group. ISBN 978-1-56159-248-7. Приступљено 11. 5. 2013.
- Murer, Stephan; Omohundro, Stephen; Stoutamire, David; Szyperski, Clemens (1996). „Iteration abstraction in Sather”. ACM Transactions on Programming Languages and Systems. 18 (1): 1—15. S2CID 7334897. doi:10.1145/225540.225541.