Генератор (рачунарство)

Из Википедије, слободне енциклопедије
Иди на навигацију Иди на претрагу

У рачунарству, генератор је специјални потпрограм који може бити употребљен за контролу итерацијског понашања понављања . У суштини, сви генератори су итератори.[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 се постиже користећи ко-рутине, пишући:  

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

Међутим, углавном се жељени генератори имплементирају са суспендованом кључном речју са функцијама као што је 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"
  • Корутине за још већу генерализовацију од сабрутине
  • Настављање за генерализацију контроле протока

Референце[уреди]

Литература[уреди]

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