Jeneratör (bilgisayar programlama) - Generator (computer programming)

Gelen bilgisayar bilimleri , bir jeneratör , bir olan rutin kontrol etmek için kullanılabilir yineleme bir davranışını döngü . Tüm oluşturucular aynı zamanda yineleyicidir . Bir üreteç, bir dizi döndüren bir işleve çok benzer, çünkü bir üreteç parametrelere sahiptir, çağrılabilir ve bir dizi değer üretir. Ancak, tüm değerleri içeren bir dizi oluşturmak ve hepsini bir kerede döndürmek yerine, bir üretici değerleri birer birer verir, bu da daha az bellek gerektirir ve arayanın ilk birkaç değeri hemen işlemeye başlamasına olanak tanır. Kısacası, bir üreteç bir fonksiyon gibi görünür ancak bir yineleyici gibi davranır .

Jeneratörler, eşyordamlar veya birinci sınıf süreklilikler gibi daha etkileyici kontrol akışı yapıları açısından uygulanabilir . Yarı eşyordamlar olarak da bilinen üreteçler, eşyordamların özel bir durumudur (ve daha zayıftır), çünkü atlanacak bir eşyordam belirtmek yerine kontrolü her zaman arayan kişiye verirler (bir değeri geri gönderirken); eşyordamların jeneratörlerle karşılaştırmasına bakın .

kullanır

Jeneratörler genellikle döngüler içinde çağrılır . Bir döngüde bir üreteç çağrısına ilk ulaşıldığında , ilgili parametrelere bağlı bağımsız değişkenlerle, başlangıçtaki üreteç rutininin durumunu kapsülleyen bir yineleyici nesnesi oluşturulur . Oluşturucunun gövdesi, özel bir verim eylemiyle karşılaşılıncaya kadar bu yineleyici bağlamında yürütülür ; o zaman, verim eylemiyle sağlanan değer, çağırma ifadesinin değeri olarak kullanılır. Bir sonraki yinelemede aynı üreteç çağrısına bir sonraki ulaşıldığında, üreteç gövdesinin yürütülmesi, verim eyleminden sonra, yine başka bir verim eylemiyle karşılaşılıncaya kadar devam ettirilir. Verim eylemine ek olarak, üreteç gövdesinin yürütülmesi, aynı zamanda , üreteç çağrısını çevreleyen en içteki döngünün sonlandırıldığı bir bitirme eylemi ile de sonlandırılabilir. Daha karmaşık durumlarda, bir jeneratör, daha sonra çeşitli şekillerde kullanılabilen bir yineleyici oluşturmak için bir döngünün dışında manuel olarak kullanılabilir.

Üreteçler elde edilen değerleri yalnızca talep üzerine hesapladıkları için, bir kerede hesaplanması pahalı veya imkansız olan diziler gibi akışları temsil etmek için kullanışlıdırlar . Bunlara örneğin sonsuz diziler ve canlı veri akışları dahildir.

İstekli değerlendirme istendiğinde (esas olarak dizi sonlu olduğunda, aksi takdirde değerlendirme asla sona ermeyecektir), kişi ya bir listeye dönüştürülebilir ya da bir oluşturucu yerine bir liste oluşturan paralel bir yapı kullanılabilir. Örneğin, Python'da bir üreteç aracılığıyla gbir listeye göre değerlendirilebilirken , F#' da dizi ifadesi tembel bir şekilde (bir üreteç veya dizi) değerlendirir, ancak hevesle (bir liste) değerlendirir. ll = list(g)seq { ... }[ ... ]

Jeneratörlerin varlığında, bir dilin döngü yapıları – for ve while gibi – tek bir döngüye indirgenebilir ... son döngü yapısı; tüm olağan döngü yapıları daha sonra uygun jeneratörler doğru şekilde kullanılarak rahatça simüle edilebilir. Örneğin, aralıklı bir döngü benzeri for x = 1 to 10Python'da olduğu gibi bir jeneratör aracılığıyla yineleme olarak uygulanabilir for x in range(1, 10). Ayrıca, jeneratöre bitişbreak gönderme ve ardından döngüde kullanma olarak uygulanabilir. continue

Zaman çizelgesi

Jeneratörler ilk olarak CLU'da (1975) ortaya çıktı , dize işleme dili Icon'da (1977) öne çıkan bir özellikti ve şimdi Python (2001), C# , Ruby , ECMAScript'in sonraki sürümleri (ES6/ES2015 itibariyle) ve diğer sürümlerde mevcuttur. Diller. CLU ve C#'da oluşturuculara yineleyiciler ve Ruby'de numaralandırıcılar denir .

Lisp

Son Common Lisp standardı yerel olarak oluşturucular sağlamaz, ancak CLtL2 veya pygen içinde belgelenen SERIES gibi çeşitli kitaplık uygulamaları mevcuttur .

CLU

Kullanıcı tanımlı veri soyutlamaları üzerinde yineleyicileri uygulamak için bir verim ifadesi kullanılır.

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;

Simge

Her ifade (döngüler dahil) bir jeneratördür. Dilin yerleşik birçok üreteci vardır ve hatta üreteç mekanizmasını kullanarak bazı mantık anlambilimini uygular ( mantıksal ayırma veya "VEYA" bu şekilde yapılır).

0'dan 20'ye kadar olan kareleri yazdırmak, aşağıdakiler yazılarak bir ortak rutin kullanılarak elde edilebilir:

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

Ancak, çoğu zaman özel oluşturucular, tam olarak CLU'daki "verim" anahtar sözcüğü gibi işlev gören "askıya alma" anahtar sözcüğüyle uygulanır.

C

C bir dil yapısı olarak üreteç işlevlerine sahip değildir, ancak bunlar eşyordamların bir alt kümesi olduklarından, bunları libdill gibi yığınlı eşyordamları uygulayan herhangi bir çerçeve kullanarak uygulamak kolaydır. POSIX platformlarında, yineleme başına bağlam değiştirme maliyeti bir endişe konusu olmadığında veya yalnızca eşzamanlılık yerine tam paralellik istendiğinde, pthreads ve borular kullanılarak çok basit bir üreteç işlevi çerçevesi uygulanabilir .

C++

Ön işlemci makrolarını kullanarak oluşturucuları C++'a dahil etmek mümkündür. Ortaya çıkan kodun yerel C++'dan çok farklı yönleri olabilir, ancak oluşturucu sözdizimi çok düzenli olabilir. Bu kaynakta tanımlanan ön işlemci makroları seti, aşağıdaki örnekte olduğu gibi sözdizimi ile tanımlanan oluşturuculara izin verir:

$generator(descent)
{
   int i;

   // place the constructor of our generator, e.g. 
   // descent(int minv, int maxv) {...}
   
   // from $emit to $stop is a body of our generator:
    
   $emit(int) // will emit int values. Start of body of the generator.
      for (i = 10; i > 0; --i)
         $yield(i); // similar to yield in Python,
                    // returns next number in [1..10], reversed.
   $stop; // stop, end of sequence. End of body of the generator.
};

Bu daha sonra aşağıdakiler kullanılarak yinelenebilir:

int main(int argc, char* argv[])
{
  descent gen;
  for(int n; gen(n);) // "get next" generator invocation
    printf("next number is %d\n", n);
  return 0;
}

Ayrıca, C++11 foreach döngülerininbegin ve endişlevlerini sağlayan herhangi bir sınıfa uygulanmasına izin verir . Daha sonra , aynı sınıfta hem yinelenebilir yöntemleri ( beginve end) hem de yineleyici yöntemlerini ( operator!=, operator++ve operator*) tanımlayarak üreteç benzeri sınıflar yazmak mümkündür . Örneğin, aşağıdaki programı yazmak mümkündür:

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

Temel bir aralık uygulaması şöyle görünür:

class range
{
private:
    int last;
    int iter;

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

    // Iterable functions
    const range& begin() const { return *this; }
    const range& end() const { return *this; }

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

Perl

Perl yerel olarak oluşturucular sağlamaz, ancak Coro ortak rutin çerçevesini kullanan Coro::Generator modülü tarafından destek sağlanır . Örnek kullanım:

use strict;
use warnings;
# Enable generator { BLOCK } and yield
use Coro::Generator;
# Array reference to iterate over
my $chars = ['A'...'Z'];

# New generator which can be called like a coderef.
my $letters = generator {
    my $i = 0;
    for my $letter (@$chars) {
        # get next letter from $chars
        yield $letter;
    }
};

# Call the generator 15 times.
print $letters->(), "\n" for (0..15);

Tcl

In Tcl 8.6, jeneratör mekanizması adlı üzerine kurulmuştur değiş tokuş eden kavramlar .

proc generator {body} {
    coroutine gen[incr ::disambiguator] apply {{script} {
        # Produce the result of [generator], the name of the generator
        yield [info coroutine]
        # Do the generation
        eval $script
        # Finish the loop of the caller using a 'break' exception
        return -code break
    }} $body
}

# Use a simple 'for' loop to do the actual generation
set count [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 , onun ile tembel değerlendirme modeli, her şey bir jeneratör - bir ile oluşturulan her veri olmayan katı talep üzerine oluşturulan veri yapıcısı. Örneğin,

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

nerede (:)katı olmayan bir liste oluşturucusu, eksileri ve parantez için kullanılan $yalnızca "birlikte çağrılan" bir operatördür. Bu, standart adaptör işlevini kullanır,

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

bir yüklemle uyumlu değerleri yeniden getiren ve uygun olmayan bir değerle karşılaşıldığında yeni değerler istemeyi durduran. Paylaşılan depolama erişimi, Haskell'de evrensel bir aracı olarak kullanılır. Liste kavrayışları serbestçe kullanılabilir:

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

raket

Raket , jeneratörler için çeşitli ilgili olanaklar sağlar. İlk olarak, for-loop formları , bir tür üretici olan dizilerle çalışır :

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

ve bu diziler de birinci sınıf değerlerdir:

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

Bazı diziler zorunlu olarak (özel durum değişkenleriyle) uygulanır ve bazıları (muhtemelen sonsuz) tembel listeler olarak uygulanır. Ayrıca, yeni yapı tanımları, diziler olarak nasıl kullanılabileceğini belirten bir özelliğe sahip olabilir.

Ancak daha doğrudan, Racket daha geleneksel bir jeneratör spesifikasyonu için bir jeneratör kitaplığı ile birlikte gelir. Örneğin,

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

Raket çekirdeğinin, oluşturulabilir genel (yeniden giren) devamlılıklar ve ayrıca sınırlandırılmış devamlılıklar sağlayan güçlü devam özellikleri uyguladığını unutmayın. Bunu kullanarak, üreteç kitaplığı Racket'te uygulanır.

PHP

PHP topluluğu, PHP 5.5'te oluşturucuları uyguladı. Ayrıntılar, orijinal Yorum İsteğinde bulunabilir : Jeneratörler .

Sonsuz Fibonacci dizisi:

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

Limitli Fibonacci dizisi:

function fibonacci(int $limit):generator 
{
    yield $a = $b = $i = 1;
 
    while (++$i < $limit) {
        yield $a = ($b = $a + $b) - $a;
    }
}

foreach (fibonacci(10) as $number) {
    echo "$number\n";
}

Bir getiri ifadesi içeren herhangi bir işlev , otomatik olarak bir oluşturucu işlevidir.

yakut

Ruby, yerleşik Enumerator sınıfı biçimindeki oluşturucuları (sürüm 1.9'dan başlayarak) destekler.

# Generator from an Enumerator object
chars = Enumerator.new(['A', 'B', 'C', 'Z'])

4.times { puts chars.next }

# Generator from a block
count = Enumerator.new do |yielder|
  i = 0
  loop { yielder.yield i += 1 }
end

100.times { puts count.next }

Java

Java, ilk günlerinden beri yineleyicileri uygulamak için standart bir arabirime sahiptir ve Java 5'ten bu yana "foreach" yapısı, java.lang.Iterablearabirimi sağlayan nesneler üzerinde döngü oluşturmayı kolaylaştırır . ( Java koleksiyonları çerçevesi ve diğer koleksiyon çerçeveleri, genellikle tüm koleksiyonlar için yineleyiciler sağlar.)

Ancak, Java'nın dilde yerleşik oluşturucuları yoktur. Bu, yineleyici oluşturmanın, özellikle üretim mantığı karmaşık olduğunda, yerleşik oluşturuculara sahip dillerden genellikle çok daha zor olduğu anlamına gelir. Bir yineleyiciden bir öğe elde edilecek her zaman tüm durum kaydedilmeli ve geri yüklenmelidir, oluşturucular kullanılabilir olduğunda olduğu gibi, durumu yerel değişkenlerde depolamak veya yerleşik döngü rutinlerini kullanmak mümkün değildir; bunun yerine, tüm bunların yerel durumu ve döngü sayaçlarını tutmak için nesne alanları kullanılarak manuel olarak simüle edilmesi gerekir.

Bu şekilde oluşturulan basit yineleyiciler bile, çok sayıda ortak kod içeren jeneratör kullananlardan önemli ölçüde daha hacimli olma eğilimindedir .

Yukarıdaki orijinal örnek Java 5'te şu şekilde yazılabilir :

// Iterator implemented as anonymous class.  This uses generics but doesn't need to.
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);
}

Sonsuz bir Fibonacci dizisi, Java 5'te yineleyici olarak da yazılabilir :

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;
                a = b;
                b = a + temp;
                return temp;
            }

            @Override
            public void remove() {
                throw new UnsupportedOperationException();
            }
        };
    }
};
// this could then be used as...
for (int f: fibo) {
    System.out.println("next Fibonacci number is " + f);
    if (someCondition(f)) break;
}

Ayrıca Java 8 Stream arabirimi kullanılarak sonsuz bir Fibonacci dizisi de yazılabilir :

Iterable<Integer> myIterable = Stream
        // Generates Fib sequence
        .iterate(new Integer[]{ 1, 1 }, x -> new Integer[] { x[1], x[0] + x[1] })
        .map(x -> x[0])::iterator;
myIterable.forEach(System.out::println);

Veya Java 8 süper arabirimi BaseStream of Stream arabiriminden bir Yineleyici edinin .

// Save the iterator of a stream that generates fib sequence
Iterator<Integer> myGenerator = Stream
        // Generates Fib sequence
        .iterate(new Integer[]{ 1, 1 }, x -> new Integer[] { x[1], x[0] + x[1] })
        .map(x -> x[0]).iterator();

// Print the first 5 elements
for (int i = 0; i < 5; i++) {
    System.out.println(myGenerator.next());
}

System.out.println("done with first iteration");

// Print the next 5 elements
for (int i = 0; i < 5; i++) {
    System.out.println(myGenerator.next());
}

/* Output:
1
1
2
3
5
done with first iteration
8
13
21
34
55 */

C#

Örnek bir C# 2.0 oluşturucu ( yieldC# sürüm 2.0'dan beri mevcuttur): Bu örneklerin her ikisi de jenerik kullanır, ancak bu gerekli değildir. verim anahtar sözcüğü, bu tartışmada tartışıldığı gibi bir koleksiyon üzerinde özel durum bilgili yinelemelerin uygulanmasına da yardımcı olur.

// Method that takes an iterable input (possibly an array)
// and returns all even numbers.
public static IEnumerable<int> GetEven(IEnumerable<int> numbers)
{
    foreach (int number in numbers)
    {
        if ((number % 2) == 0)
        {
            yield return number;
        }
    }
}

Birden çok yield returnifade kullanmak mümkündür ve bunlar her yinelemede sırayla uygulanır:

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

XL

Gelen XL , yinelemeler döngüler için '' temelini oluşturur:

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

// 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 # yoluyla jeneratörleri sağlayan dizi ifadeleri , sürümü 1.9.1 beri. Bunlar aracılığıyla bir dizi (tembelce değerlendirilen, sıralı erişim) seq { ... }, bir liste (hevesle değerlendirilen, sıralı erişim) aracılığıyla [ ... ]veya [| ... |]değerler üreten kodu içeren bir dizi (hevesle değerlendirilen, dizine alınmış erişim) tanımlayabilir . Örneğin,

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

0'dan 25'e kadar olan sayı aralığındaki sayıları filtreleyerek 0'dan 14'e kadar sayıların karelerinden oluşan bir dizi oluşturur.

piton

2001'de Python'a 2.2 sürümünde jeneratörler eklendi . Örnek bir jeneratör:

from typing import Iterator

def countfrom(n: int) -> Iterator[int]:
    while True:
        yield n
        n += 1

# Example use: printing out the integers from 10 to 20.
# Note that this iteration terminates normally, despite
# countfrom() being written as an infinite loop.

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:
        # If dividing n by all the numbers in p, up to and including sqrt(n),
        # produces a non-zero remainder then n is prime.
        if all(n % f > 0 for f in itertools.takewhile(lambda f: f*f <= n, p)):
            yield n
            p.append(n)
        n += 2

Python'da bir üreteç, donmuş bir yığın çerçevesi içeren bir yineleyici olarak düşünülebilir . Yineleyicide her çağrıldığında, Python, bir sonraki ifadeye ulaşılana kadar normal olarak yürütülen donmuş çerçeveyi sürdürür . Jeneratörün çerçevesi daha sonra tekrar dondurulur ve elde edilen değer arayan kişiye döndürülür. next()yield

PEP 380 (Python 3.3'te uygulanmış) yield fromifadeyi ekleyerek bir oluşturucunun işlemlerinin bir kısmını başka bir oluşturucuya devretmesine veya yinelenebilir hale getirmesine olanak tanır.

Jeneratör ifadeleri

Python'da, oluşturucuların oluşturulmasına yardımcı olan bir oluşturucu ifadesi adı verilen , liste kavrayışlarınınkine göre modellenmiş bir sözdizimi vardır . Aşağıdaki, oluşturucu countfromişlevinden kareleri hesaplamak için bir oluşturucu ifadesi kullanarak yukarıdaki ilk örneği genişletir :

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

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

ECMAScript

ECMAScript 6 (aka Harmony) oluşturucu işlevlerini tanıttı.

Bir fonksiyon üreteci kullanılarak sonsuz bir Fibonacci dizisi yazılabilir:

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

// manually iterating
let fibGen = fibonacci();
console.log(fibGen.next().value); // 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

// picks up from where you stopped
for (const n of fibGen) {
    console.log(n);
    if (n > 10000) break;
}

r

Yineleyiciler paketi bu amaç için kullanılabilir.

library(iterators)

# Example ------------------
abc <- iter(c('a','b','c'))
nextElem(abc)

küçük konuşma

Pharo Smalltalk'ta örnek :

Aşağıdaki Altın oran oluşturucu , her 'goldenRatio next' çağrısına, Altın Oran'a daha iyi bir yaklaşım getirir.

goldenRatio := Generator on: [ :g | | x y z r | 
	x := 0.
	y := 1.
	[  
		z := x + y.
		r := (z / y) asFloat.
		x := y.
		y := z.
		g yield: r
	] repeat	
].

goldenRatio next.

Aşağıdaki ifade sonraki 10 yaklaşımı döndürür.

Character cr join: ((1 to: 10) collect: [ :dummy | ratio next ]).

Pharo'da gizli bir mücevher: Jeneratör bölümünde daha fazlasını görün .

Ayrıca bakınız

• Bir dizi değer üreten başka bir yapı için liste anlama
• Her seferinde bir öğe liste üretme kavramı için yineleyici
• Bir alternatif için yinelenen
• Gerektiğinde değer üretmek için tembel değerlendirme
• Corecursion yerine yineleme ile potansiyel olarak sonsuz veriler için verim
• Alt programdan daha fazla genelleme için eşyordam
• Kontrol akışının genelleştirilmesine devam

Notlar

Referanslar

• Stephan Murer, Stephen Omohundro David Stoutamire ve Clemens Szyperski yer: Yineleme soyutlama Sather . Programlama Dilleri ve Sistemlerinde ACM İşlemleri , 18(1):1-15 (1996) [1]