Generator (informatika)

Izvor: Wikipedija
(Preusmjereno sa stranice Generator (računarstvo))
Prijeđi na navigaciju Prijeđi na pretragu

U računarstvu, generator je specijalni potprogram koji može biti upotrebljen za kontrolu iteracijskog ponašanja ponavljanja . U suštini, svi generatori su iteratori.[1] Generartor je veoma sličan funkciji koja vraća niz, u kojoj generator ima parametre, koja se može pozvati, i generisati sekvencu vrednosti. Međutim, umesto da se pravi niz koji sadrži sve te elemente i i vraća sve njih, poziv generatora vraća jednu i samo jednu vrednost, što zahteva manje memorije i dopušta programeru da počne sa procesuiranjem prvih nekoliko vrednosti odmah. Ukratko, generator liči na funkciju ali se ponaša kao iterator.

Generatori mogu biti implementirani u pogledu brže konstrukcije kontrole protoka, kao što su korutine ili nastavljanje prve-klase.[2] Generatori, takođe poznati kao polu-korutine,[3] su specijalni slučaj (i slabiji od) korutina, u smislu da uvek daju povratnu kontrolu programeru (kada se vraća vrednost), umesto da odredi putanju korutini, videti komparacija korutina sa geratorima. 

Upotreba[uredi | uredi kod]

Generatori se uglavnom izvršavaju unutar petlje. Prvi put kada se generator izvrši u petlji, iteretorni objekat je kreiran da enkapsulira stanje generatora na njegovom početku, sa argumentima vezanih za odgovarajuće parametre. Telo generatora je tada izvršavano u vidu iteratora sve do „yield“ naredbe; tada je vrednost obezbeđena operacijom „yield' korišćena kao vrednost prizvanog izraza. Sleći put kada se pozove generator u naknadnoj iteraciji, izvršavanje tela generatora se nastavlja nakon operacije „yield“, sve dok ne dođe do sledeće „yield“ operacije. U prilog operaciji „yield“, izvršavanje tela generatora se može završiti uz pomoć „finish“ naredbe, u kojoj se prekida ponavljanje u petlji generatora. U mnogo komplikovanijim situacijama, generatori mogu biti korišćeni izvan petlje da bi se napravila iteracija, koja onda može biti upotrebljena na razne načine.

Pošto generatori izvršavaju njihove date vrednosti samo na poziv funkcije "yield“, korisni su za predstavljanje toka, kao sekvence koje bi bile skupe ili nemoguće za izvršavanje odjednom. Ovo uključuje e.g. beskonačan broj sekvenci i tokova podataka.

Kada je željena procena poželjna (prvenstvetno kada je sekvenca konačna, jer se u suprotnom evaluacije nikad neće izvršiti), jedan može da se konvertuje u listu, ili da se koristi kao paralelni konstruktor koji kreira listu umesto generatora. Na primer u Pajtonu generator g može biti označen listom l kao l = list(g), dok se u  F# ekspresija sekvenci seq { ... }  izvršava sporo (generator ili sekvenca) ali [ ... ] se izvršava efikasnije i poželjnije (lista).

U prisustvu generatora, konstrukcija petlje programa- kao što su for i while- može biti redukovana u jednu petlju...kraj konstrukcije petlje; sve obično korišćene konstrukcije petlji mogu biti stimulisane koristeći ispravno pogodan generator   . Na primer, rangirana petlja kao što je for x = 1 to 10 može biti implementirana kao iteracija kroz generator, kao i u Pajtonu for x in xrange(10, 1). Osim toga, break može biti implementirana tako što šalje naredbu kraj  generatoru i posle toga koristeći continue u petlji.

Izgled[uredi | uredi kod]

Generatori su se prvo pojavili u CLU  (1975),[4] gde je istaknuta odlika u vidu manipulacije stringa u programskom jeziku Icon (Ajkon) (1977) a sada je dostupna u Pajtonu,[5] C#,[6] Rubi, nadolazećoj verziji ECMASkript (Harmonija/ES6) i drugim programima. U CLU i C#, generatori se nazivaju „iteratori“, a u programskom jeziku Rubi, "enumeratori".

Lisp[uredi | uredi kod]

Konačni Zajednički Lisp ne podržava prirodno generatore, još postoji varirajuća biblioteka implementacija, kao što su SERIJE dokumentovane u CLtL2 ili pajgenu (pygen).

CLU (CLU)[uredi | uredi kod]

Yield funkcija je korišćena da implementira iteratore preko korisničko-definisane abstrakcije podataka .[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;

Ajkon (Icon)[uredi | uredi kod]

Svaka ekspresija (uključujući petlje) je generator. Program ima mnogo ugrađenih generatora, čak i neke logičko semantičke implementacije koriste mehanizam generatora (Disjunkcija ili "ILI" je urađena tako).

Štampanje kvadrata od 0 do 20 se postiže koristeći ko-rutine, pišući:  

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

Međutim, uglavnom se željeni generatori implementiraju sa suspendovanom ključnom rečju sa funkcijama kao što je yield ključna reč u CLU.

C++[uredi | uredi kod]

Moguće je uvesti generatore u C++ koristeći pre-procesorske makroe. Rezultirajući kod može imati aspekte različite od prirode C++, ali sintaksa generatora može biti vrlo neopterećena. Veoma dobar primer se može naći na.[8] Komplet preprocesorskih makroa definisanih u ovom kodu dozvoljava generatore definisanih sintaksama kao u sledećem primeru :

$generator(descent)
{
   // mesto za sve vrednosti korišćene u generatoru
   int i; // naš brojač

   // mesto konstrukcije našeg generatora, e.g. 
   // vrednost (int minv, int maxv) {...}
   
   // od $(emit)emitovanja do $(stop)stop je telo našeg generatora:
    
   $emit(int) // će emitovati celobrojne vrednosti. Poćetak tela generatora:
      for (i = 10; i > 0; --i)
         $yield(i); // poznato kao yield u Pajtonu,
                    // vraća sledeći broj u [1..10], preokrenut.
   $stop; // stop, kraj sekvence. Kraj tela generatora.
};

Ovo može biti izvršeno koristeći:

int main(int argc, char* argv[])
{
  descent gen;
  for(int n; gen(n);) // "sledeći" poziv generatora
    printf("next number is %d\n", n);
  return 0;
}

Štaviše, C++11 dozvoljava svakoj petlji da bude primenjena u bilo kojoj klasi koja podržava begin i end funkcije. Onda je moguće napisati generator kao klase uz pomoć obe merne metode (begin and end) i iterativne metode (operator!=, operator++ and operator*) u istoj klasi. Na primer, moguće je napisati sledeći proram:

#uključujući <iostream>
int main()
{
    for (int i: range(10))
    {
        std::cout << i << std::endl;
    }
    return 0;
}

Osnovni domet implementacije bi trebalo da izgleda ovako:

class range
{
private:
    int last;
    int iter;

public:
    range(int end):
        last(end),
        iter(0)
    {}

    // Merne funkcije
    const range& begin() const { return *this; }
    const range& end() const { return *this; }

    // Funkcije iteratora
    bool operator!=(const range&) const { return iter < last; }
    void operator++() { ++iter; }
    int operator*() const { return iter; }
};

Perl (Perl)[uredi | uredi kod]

Perl nema prirodno ugrađene generatore, ali podržavanje je sponzorisano od strane Koro Generatora modul koji koristi Koro ko-rutine okvir. Primer korišćenja. 

koristiti striktno;
koristiti upozorenja;
# Aktivirati generator { BLOCK } i ''yield''
koristiti Koro::Generator;
# Niz upućuje na izvršavanje preko mojih $znakova = ['A'...'Z'];
# Novi generator se može nazvati ''coderef''.
my $letters = generator {
    my $i = 0;
    for my $letter (@$chars) {
        # uzmi sledeće slovo od $chars
        yield $letter;
    }
};
# Pozovi generator 15 puta.
print $letters->(), "\n" for (0..15);

Tcl (Tcl)[uredi | uredi kod]

U Tcl-y 8.6, mehanizam generatora počiva na imenovanju korutina.

proc generator {body} {
    coroutine gen[incr ::disambiguator] apply {{script} {
        # produkuje rezultat [generatora], ime generatora
        yield [info corutine]
        # Uradi stvaranje
        eval $script
        # Završiti petlju poziva koristeći 'break' izuzetak.
        return -code break
    }} $body
}
# Koristiti jednostavnu 'for' petlju za stvaranje 
set count[generator {
    for {set i 10} {$i <= 20} {incr i} {
        yield $i
    }
}]
# Izvlači vrednosti iz generatora dok se ne iscrpe
while 1 {
    puts [$count]
}

Haskel (Haskell)[uredi | uredi kod]

U Haskelu, sa sporim određivanjem vrdnosti modelom, sve je generator- svaki datum kreiran sa ne-strogom konstrukcijom podataka je generisan na zahtev. Na primer,

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

gde je (:) ne-stroga lista konstruktora, protiv, i $ je samo "pozovi-sa" operator, korišćen za parentizaciju. Ovo koristi standarni adaptor funkcija,

takeWhile p [] = []
takeWhile p (x:xs) | p x = x : takeWhile p xs
                   | otherwise = []

čije se ponovno pronađene vrednosti slažu sa iskazom, i prestaju sa traženjem novih vrednosti čim se izvrši jedna neodgovarajuća vrednost. Pristup zajedničkom skladištu je korišćeno kao univerzalan posrednik u Haskelu. Lista shvatanja može biti besplatno korišćena:

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

Raket (Racket)[uredi | uredi kod]

Raket omogućava nekoliko pratećih objekata za generatore. Prvo, njena for-petlja ima formu rada sa sekvencama, koja je vrsta proizvođača:

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

i ove sekvence su takođe vrednosti prve-klase:

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

Neke sekvence su imperativno implementirane (sa skrivenim vrednostima varijabli) a neke su implementirane kao (verovatno beskonačne) lenje liste. Takođe, nova struktura definicije može imati moć koja određuje kako se mogu koristiti kao sekvence. Ali više direktno, Raket ima laboratoriju generatora za tradicionalnu specifikaciju generatora. Na primer,

#''lang'' raket
(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)

Primetiti da Raketovo jezgro implementira snažnu ponavljajuću karakteristiku, obezbeđujući opšta ponavljanja koja su kompatibilna ali takođe i ograničena. Koristeći ovo, biblioteka generatora je implementirana u Raketu.

PHP (PHP)[uredi | uredi kod]

Zajednica PHP-a je implementirala generatore u PHP 5.5. Detalji se mogu pornaći na RFC o generatorima.

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";
}

Rubi (Ruby)[uredi | uredi kod]

Rubi podržava generatore (počevši od verzije 1.9) u formi ugrađene Enumeratorske klase.

# Generator iz Enumeratorskog objekta
chars = Enumerator.new(['A', 'B', 'C', 'Z'])

4.times { puts chars.next }
# Generator iz bloka
count = Enumerator.new do |yielder
| i = 0
  loop { yielder.yield i += 1 }
end

100.times { puts count.next }

Java [uredi | uredi kod]

Java je imala standardni pristup za implementiranje iteratora još od ranih svojih dana, i od Jave 5, foreach konstrukcija čini to lakšim za ponavljanje preko objekata koje omogućava java.lang.Iterable pristup. ( Okvir java kolekcije i ostale okvirne kolekcije, proizvode iteratore za sve kolekcije.)

Međutim, Java nema ugrađene generatore. Ovo znači da je kreiranje iteratora češće mnogo komplikovanije nego u programima koji imaju ugrađene generatore, pogotovo kada je stvaranje kompleksno. Zbog toga što se sve vrednosti moraju snimiti i sačuvati svaki put kada se pozove stvar iz iteratora, nije moguće sačuvati vrednosti u lokalnim varijablama ili koristiti ugrađenu ponavljačku rutinu, kao kada su generatori dostupni; umesto toga, sve ovo mora biti manalno simulirano, koristeći polja da čuva lokalnu vrednost i broj ponavljanja.

Čak i jednostavni iteratori izgrađeni na ovaj način imaju tedenciju da budu značajno glomazniji od onih koji koriste generatori, sa mnogo opštenamenskih kodova.

Originalan primer se može napisati u Java 7 kao:

// Iterator je implementiran kao anonimna klasa. Ovo se koristi generički ali nije potrebno.
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);
}

Beskonačna Fibonačijeva sekvenca se takođe može mapisati kao iterator u Java 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();
            }
        };
    }
};
// ovo se zatim može koristiti kao...
for (int f: fibo) {
    System.out.println("next Fibonacci number is " + f);
    if (someCondition(f)) break;
}

Takođe, beskonačna Fibonačijeva sekvenca se može napisati i u Java 8 koristeći tok pristupa:

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);

Ili kao iterator iz Java 8 super-pristupa OsnovnogToka toka pristupa.

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();
    }
}

// ovo se zatim može koristiti kao...
for (int f: fibonacci(10)) {
    System.out.println(f);
}

C#[uredi | uredi kod]

Primer C# 2.0 generatora ( yield je dostušam od C# verzije 2.0):

Oba ova primera se koriste generički, ali ne moraju. 

// Metoda koja uzima merni ulaz (verovatno niz)
// i vraća sve parne brojeve.
public static IEnumerable<int> GetEven(IEnumerable<int> numbers) {
    foreach (int i in numbers) {
        if ((i % 2) == 0) {
            yield return i;
        }
    }
}

Moguće je koristiti više puta yield return funkciju i one se nalaze u sekvenci svake iteracije:

public class CityCollection : IEnumerable<string> {
    public IEnumerator<string> GetEnumerator() {
        yield return "New York";
        yield return "Paris";
        yield return "London";
    }
}

HL(XL)[uredi | uredi kod]

U HL-u, iteratori su osnova "for" petlje:

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

// Primetiti da I ne treba da bude deklarisano, zbog deklarisanog ''var out'' u iteratoru
// Implicitna deklaracija I kao celobrojna vrednost je napravljena ovde
for I in 1..5 loop
    IO.WriteLn "I=", I

F#[uredi | uredi kod]

F# sadrži generatore preko ekspresija sekvence, od verzije1.9.1.[9] Ovo može definisati sekvencu (sporu, sekvencijalnog pristupa) preko seq { ... }, liste (brza, sekvencijalnog pristupa) preko [ ... ] ili niza (brz, indeksnog pristupa) preko [| ... |] koja sadrži kod koji generiše vrednosti. Na primer,

seq { for b in 0 .. 25 do
          if b < 15 then
              yield b * b }

forma sekvence kvadrata brojeva od 0 do 14, ispitivanjem brojeva u rasponu od 0. do 25.

Pajton (Python)[uredi | uredi kod]

Generatori su dodati u Pajton u verziji 2.2.[5] Primer generatora:

def countfrom(n):
    while True:
        yield n
        n += 1
# Primer: štampa celobrojne vrednosti od 10 do 20
# Primetiti da se ova iteracija prestaje sa izvršavanjem normalno, uprkos
# countfrom() je napisana kao beskonačna petlja.

for i in countfrom(10):
    if i <= 20:
        print(i)
    else:
        break
# Još jedan generator, koji proizvodi proste bojeve neograničeno, tj. koliko je nama potrebno.

def primes():
    yield 2
    n = 3
    p = []
    while True:
        # Ovo radi u Pajtonovim verzijama 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

U Pajtonu, generator može biti misao iteratora koji sadrži nepromenljiv (zaleđen) okvir skladišta  . Kad god je iteratorova next() metoda pozvana, Pajton nastavlja nepromenljiv okvir, koji se izvršava normalno sve dok ne stigne do yield funkcije. Generatorov okvir je zaleđen ponovo, i pozvana vrednost je vraćena pozivaocu (korisniku).

PEP (PEP) 380 (ubačen u Pajton 3.3) dodaje yield from ekspresiju, koja dozvoljava generatoru da proverava deo njegovih operacia za drugi generator .[10]

Ekspresije Generatora[uredi | uredi kod]

Pajton ima modeliranu sintaksu po uzoru na listu spoznaja, koja se naziva ekspresija generatora i koja pomaže u kreiranju generatora. Sledeći primer pokazuje korišćenje ekspresije generatora da se izračuna kvadrat iz brojača (funkcije generatora):

squares = ( n*n for n in countfrom(2) )

for j in squares:
    if j <= 20:
        print(j)
    else:
        break

ECMASkript (ECMAScript)[uredi | uredi kod]

ECMASkript 6 (poznata kao Harmonija) će imati funkcije generatora.

Beskonačna Fibonačijeva sekvecna se može napisati koristeći funkciju generatora:

// inspirisano od strane: 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

Vidi još[uredi | uredi kod]

  • Lista želja za ostale konstrukcije koje sadrže sekvence vrednosti
  • Iterator za koncept stvaranja jednog elementa liste u vremenu
  • Iterejtee za alternativu
  • Spora dodela vrednosti za proizvodnju vrednosti kada su potrebne
  • Ko-rekurzija za potencijalno beskonačnu vrednost uz pomoć rekurzije umesto "yield"
  • Korutine za još veću generalizovaciju od sabrutine
  • Nastavljanje za generalizaciju kontrole protoka

Reference[uredi | uredi kod]

  1. ↑ What is the difference between an Iterator and a Generator? - Stack Overflow
  2. ↑ Kiselyov, Oleg (January 2004).
  3. ↑ Anthony Ralston (2000).
  4. ↑ Liskov, Barbara (April 1992).
  5. ↑ 5,0 5,1 Python Enhancement Proposals: PEP 255: Simple Generators, PEP 289: Generator Expressions, PEP 342: Coroutines via Enhanced Generators
  6. ↑ yield (C# Reference)
  7. ↑ Liskov, B.; Snyder, A.; Atkinson, R.; Schaffert, C. (1977).
  8. ↑ Generators in C++ - CodeProject
  9. ↑ "Some Details on F# Computation Expressions".
  10. ↑ PEP 380 -- Syntax for Delegating to a Subgenerator

Literatura[uredi | uredi kod]

  • Stefan Murer, Stiv Omohundro, Dejvid Stotumaer i Klemens Siperski: abstrakcija iteracije u Sateru. ACM Transakcije na Programske jezike i Sisteme, 18(1):1-15 (1996) [1]
Izvor: https://sh.wikipedia.org/w/index.php?title=Generator_(informatika)&oldid=41811139