Einführung

Seit Version 5.5 in PHP gibt es so tolle Sachen wie Generatoren. Ich werde die offizielle Handbuchseite nicht wiederholen, aber sie sind eine großartige Sache für die kurze Definition von Iteratoren. Das bekannteste Beispiel ist:

function xrange($from, $till, $step)
{
   if ($from>$till || $step<=0)
   {
      throw new InvalidArgumentException('Invalid range initializers');
   }

   for ($i = $from; $i < $till; $i += $step)
   {
      yield $i;
   }
}

//...

foreach (xrange(2, 13, 3) as $i)
{
   echo($i.PHP_EOL); // 2,5,8,11
}

und Generator ist eigentlich keine Funktion, sondern eine Instanz einer konkreten Klasse:

get_class(xrange(1, 10, 1)); // Generator

Das Problem

Fertig mit RTM-Zeug, jetzt weiter zu meiner Frage. Stellen Sie sich vor, wir möchten einen Generator von erstellen Fibonacci-Zahlen. Um diese zu erhalten, können wir normalerweise eine einfache Funktion verwenden:

function fibonacci($n)
{
   if(!is_int($n) || $n<0)
   {
      throw new InvalidArgumentException('Invalid sequence limit');
   }
   return $n < 2 ? $n : fibonacci($n-1) + fibonacci($n-2);
}

var_dump(fibonacci(6)); // 8

Verwandeln wir das in etwas, das hält Reihenfolge und nicht nur das letzte Mitglied:

function fibonacci($n)
{
   if (!is_int($n) || $n<0)
   {
      throw new InvalidArgumentException('Invalid sequence limit');
   }
   if ($n<2)
   {
      return range(0, $n);
   }
   $n1 = fibonacci($n-1);
   $n2 = fibonacci($n-2);
   return array_merge($n1, [array_pop($n1)+array_pop($n2)]);
}

//...

foreach (fibonacci(6) as $i)
{
   echo($i.PHP_EOL); // 0,1,1,2,3,5,8
}

Wir haben jetzt eine Funktion, die ein Array mit vollständiger Sequenz zurückgibt

Die Frage

Zum Schluss noch der Frageteil: wie kann ich mein neustes transformieren fibonacci funktionieren, so wird es Ertrag meine Werte, ohne sie in einem Array zu halten? Mein $n kann groß sein, also möchte ich die Vorteile von Generatoren nutzen, wie in xrange Probe. Pseudo-Code wird sein:

function fibonacci($n)
{
   if (!is_int($n) || $n<0)
   {
      throw new InvalidArgumentException('Invalid sequence limit');
   }

   if ($n<2)
   {
      yield $n;
   }

   yield fibonacci($n-2) + fibonacci($n-1);
}

Aber das ist offensichtlich Mist, da wir damit nicht so umgehen können, weil die Rekursion ein Objekt der Klasse verursachen wird Generator und nicht int Wert.

Bonus: Das Erhalten einer Fibonacci-Folge ist nur ein Beispiel für eine allgemeinere Frage: Wie werden Generatoren mit Rekursion im allgemeinen Fall verwendet? Natürlich kann ich Standard verwenden Iterator dafür oder meine Funktion umschreiben, um Rekursion zu vermeiden. Aber das will ich mit Generatoren erreichen. Ist das möglich? Lohnt sich die Mühe, dies so zu verwenden?

Das Problem, auf das ich gestoßen bin, als ich versuchte, eine rekursive Generatorfunktion zu erstellen, ist, dass, sobald Sie Ihre erste Tiefenstufe überschritten haben, jeder nachfolgende Ertrag seinem übergeordneten Aufruf und nicht der Iterationsimplementierung (der Schleife) nachgibt.

Ab PHP 7 wurde eine neue Funktion hinzugefügt, die es Ihnen ermöglicht Ertrag aus eine nachfolgende Generatorfunktion. Das ist das Neue Generatordelegierung Besonderheit: https://wiki.php.net/rfc/generator-delegation

Dies ermöglicht es uns, aus nachfolgenden rekursiven Aufrufen nachzugeben, was bedeutet, dass wir jetzt rekursive Funktionen mithilfe von Generatoren effizient schreiben können.

$items = ['what', 'this', 'is', ['is', 'a', ['nested', 'array', ['with', 'a', 'bunch',  ['of', ['values']]]]]];

function processItems($items)
{
    foreach ($items as $value)
    {
        if (is_array($value))
        {
            yield from processItems($value);
            continue;
        }
        yield $value;
    }
}

foreach (processItems($items) as $item)
{
    echo $item . "\n";
}

Dies ergibt die folgende Ausgabe..

what
this
is
is
a
nested
array
with
a
bunch
of
values

Ich habe endlich eine reale Verwendung für rekursive Generatoren identifiziert.

Ich habe nachgeforscht QuadTree Datenstrukturen vor kurzem. Für diejenigen, die mit QuadTrees nicht vertraut sind, handelt es sich um eine baumbasierte Datenstruktur, die für die Geodatenindizierung verwendet wird und eine schnelle Suche nach allen Punkten/Standorten innerhalb eines definierten Begrenzungsrahmens ermöglicht. Jeder Knoten im QuadTree stellt ein Segment der kartierten Region dar und fungiert als Bucket, in dem Standorte gespeichert werden … aber ein Bucket mit begrenzter Größe. Wenn ein Bucket überläuft, spaltet der QuadTree-Knoten 4 untergeordnete Knoten ab, die die nordwestlichen, nordöstlichen, südwestlichen und südöstlichen Bereiche des übergeordneten Knotens darstellen, und beginnt, diese zu füllen.

Bei der Suche nach Orten, die in einen bestimmten Begrenzungsrahmen fallen, beginnt die Suchroutine am Knoten der obersten Ebene und testet alle Orte in diesem Bucket; kehrt dann in die untergeordneten Knoten zurück und testet, ob sie sich mit dem Begrenzungsrahmen schneiden oder von dem Begrenzungsrahmen eingeschlossen sind, testet jeden QuadTree-Knoten innerhalb dieses Satzes und wiederholt sich dann erneut nach unten durch den Baum. Jeder Knoten kann keinen, einen oder viele Orte zurückgeben.

Ich habe eine grundlegende implementiert QuadTree in PHP, entworfen, um ein Array von Ergebnissen zurückzugeben; Dann erkannte ich, dass dies ein gültiger Anwendungsfall für einen rekursiven Generator sein könnte, also implementierte ich a GeneratorQuadTree auf die in einer foreach () -Schleife zugegriffen werden kann, die bei jeder Iteration ein einzelnes Ergebnis liefert.

Es scheint ein viel gültigerer Anwendungsfall für rekursive Generatoren zu sein, da es sich um eine wirklich rekursive Suchfunktion handelt und weil jeder Generator möglicherweise kein, ein oder viele Ergebnisse anstelle eines einzelnen Ergebnisses zurückgibt. Tatsächlich behandelt jeder verschachtelte Generator einen Teil der Suche und speist seine Ergebnisse durch den Baum durch seinen Elternteil zurück.

Der Code ist ziemlich viel, um ihn hier zu posten; aber man kann sich die implementierung mal anschauen github.

Es ist geringfügig langsamer als die Nicht-Generator-Version (aber nicht wesentlich): Der Hauptvorteil ist die Reduzierung des Arbeitsspeichers, da es nicht einfach ein Array variabler Größe zurückgibt (was je nach Anzahl der zurückgegebenen Ergebnisse ein erheblicher Vorteil sein kann). Der größte Nachteil ist die Tatsache, dass die Ergebnisse nicht einfach sortiert werden können (meine Nicht-Generator-Version führt ein usort() auf dem Ergebnisarray aus, nachdem es zurückgegeben wurde).

function fibonacci($n)
{
    if($n < 2) {
        yield $n;
    }

    $x = fibonacci($n-1);
    $y = fibonacci($n-2);
    yield $x->current() + $y->current();
}


for($i = 0; $i <= 10; $i++) {
    $x = fibonacci($i);
    $value = $x->current();
    echo $i , ' -> ' , $value, PHP_EOL;
}

Wenn Sie zuerst einen Generator erstellen möchten, können Sie auch die iterative Version von Fibonacci verwenden:

function fibonacci ($from, $to)
{
  $a = 0;
  $b = 1;
  $tmp;
  while( $to > 0 ) {
    if( $from > 0 )
      $from--;
    else
      yield $a;

    $tmp = $a + $b;
    $a=$b;
    $b=$tmp;
    $to--;
  }
}

foreach( fibonacci(10,20) as $fib ) {  
    print "$fib "; // prints "55 89 144 233 377 610 987 1597 2584 4181 " 
}

Hier ist ein rekursiver Generator für Kombinationen (Reihenfolge unwichtig, ohne Ersatz):

<?php

function comb($set = [], $size = 0) {
    if ($size == 0) {
        // end of recursion
        yield [];
    }
    // since nothing to yield for an empty set...
    elseif ($set) {
        $prefix = [array_shift($set)];

        foreach (comb($set, $size-1) as $suffix) {
            yield array_merge($prefix, $suffix);
        }

        // same as `yield from comb($set, $size);`
        foreach (comb($set, $size) as $next) {
            yield $next;
        }
    }
}

// let's verify correctness
assert(iterator_to_array(comb([0, 1, 2, 3, 4], 3)) == [
    [0, 1, 2], [0, 1, 3], [0, 1, 4], [0, 2, 3], [0, 2, 4],
    [0, 3, 4], [1, 2, 3], [1, 2, 4], [1, 3, 4], [2, 3, 4]
]);

foreach (comb([0, 1, 2, 3], 3) as $combination) {
    echo implode(", ", $combination), "\n";
}

Ausgänge:

0, 1, 2
0, 1, 3
0, 2, 3
1, 2, 3

Dasselbe nicht nachgebend.

Kürzlich stieß ich auf ein Problem, das „rekursive“ Generatoren oder Generatordelegierung benötigte. Am Ende habe ich eine kleine Funktion geschrieben, die delegierte Generatoraufrufe in einen einzigen Generator umwandelt.

Ich habe es in ein Paket umgewandelt, damit Sie es einfach mit dem Komponisten anfordern oder die Quelle hier auschecken können: Hedronium/Generator-Nest.

Code:

function nested(Iterator $generator)
{
    $cur = 0;
    $gens = [$generator];

    while ($cur > -1) {
        if ($gens[$cur]->valid()) {
            $key = $gens[$cur]->key();
            $val = $gens[$cur]->current();
            $gens[$cur]->next();
            if ($val instanceof Generator) {
                $gens[] = $val;
                $cur++;
            } else {
                yield $key => $val;
            }
        } else {
            array_pop($gens);
            $cur--;
        }
    }
}

Sie verwenden es wie:

foreach (nested(recursive_generator()) as $combination) {
    // your code
}

Überprüfen Sie diesen Link oben. Es hat Beispiele.

Kurze Antwort: Rekursive Generatoren sind einfach. Beispiel für das Gehen durch einen Baum:

class Node {

    public function getChildren() {
        return [ /* array of children */ ];
    }

    public function walk() {
        yield $this;

        foreach ($this->getChildren() as $child) {
            foreach ($child->walk() as $return) {
                yield $return;
            };
        }
    }
}

Es ist alles.

Lange Antwort zu Fibonacci:

Generator ist etwas, das mit verwendet wird foreach (generator() as $item) { ... }. Aber OP will fib() Funktion zurückzugeben intaber gleichzeitig will er, dass es zurückkommt generator darin verwendet werden foreach. Es ist sehr verwirrend.

Es ist möglich, eine rekursive Generatorlösung für Fibonacci zu implementieren. Wir müssen nur etwas hineinstecken fib() Eine Schleife, die in der Tat funktionieren wird yield jedes Mitglied der Sequenz. Da der Generator mit foreach verwendet werden soll, sieht es wirklich seltsam aus, und ich glaube nicht, dass es effektiv ist, aber hier ist es:

function fibGenerator($n) {
    if ($n < 2) {
        yield $n;
        return;
    }

    // calculating current number
    $x1 = fibGenerator($n - 1);
    $x2 = fibGenerator($n - 2);
    $result = $x1->current() + $x2->current();

    // yielding the sequence
    yield $result;
    yield $x1->current();
    yield $x2->current();

    for ($n = $n - 3; $n >= 0; $n--) {
        $res = fibGenerator($n);
        yield $res->current();
    }
}

foreach (fibGenerator(15) as $x) {
    echo $x . " ";
}