32

序章

PHP のバージョン 5.5 以降、 generatorsなどの優れた機能があります。公式のマニュアル ページについては繰り返しませんが、イテレータを簡単に定義するには非常に便利です。最もよく知られているサンプルは次のとおりです。

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
}

generator は実際には関数ではなく、具象クラスのインスタンスです。

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


問題

RTM の作業は終わり、私の質問に移りましょう。フィボナッチ数のジェネレーターを作成したいとします。通常、それらを取得するには、単純な関数を使用できます。

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

これを、最後のメンバーだけでなく、シーケンスを保持するものに変換しましょう。

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
}

完全なシーケンスで配列を返す関数ができました


質問

fibonacci最後に、質問の部分: 最新の関数を変換して、配列に値を保持するのではなく、値を生成するにはどうすればよいですか? 私は大きくなる可能性があるので、サンプル$nのようにジェネレーターの利点を利用したいと考えています。xrange擬似コードは次のようになります。

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

しかし、再帰は値Generatorではなくクラスのオブジェクトを引き起こすため、このように処理することはできないため、これは明らかにがらくたです。int

ボーナス：フィボナッチ数列を取得することは、より一般的な質問のサンプルにすぎません：一般的なケースで再帰を伴うジェネレーターを使用する方法は？もちろん、標準のIteratorを使用することも、再帰を避けるために関数を書き直すこともできます。しかし、私はジェネレーターでそれを達成したいと考えています。これは可能ですか？これをそのように使用する価値はありますか?

4

8 に答える 8

9

I've finally identified a real-world use for recursive generators.

I've been exploring QuadTree datastructures recently. For those not familiar with QuadTrees, they're a tree-based datastructure use for geospatial indexing, and allowing a fast search lookup of all points/locations within a defined bounding box. Each node in the QuadTree represents a segment of the mapped region, and acts as a bucket in which locations are stored... but a bucket of restricted size. When a bucket overflows, the QuadTree node splits off 4 child nodes, representing the North-west, North-east, South-west and South-east areas of the parent node, and starts to fill those.

When searching for locations falling within a specified bounding box, the search routine starts at the top-level node, testing all the locations in that bucket; then recurses into the child nodes, testing whether they intersect with the bounding box, or are encompassed by the bounding box, testing each QuadTree node within that set, then recursing again down through the tree. Each node may return none, one or many locations.

I implemented a basic QuadTree in PHP, designed to return an array of results; then realised that it might be a valid use case for a recursive generator, so I implemented a GeneratorQuadTree that can be accessed in a foreach() loop yielding a single result each iteration.

It seems a much more valid use-case for recursive generators because it is a truly recursive search function, and because each generator may return none, one or many results rather than a single result. Effectively, each nested generator is handling a part of the search, feeding its results back up through the tree through its parent.

The code is rather too much to post here; but you can take a look at the implementation on github.

It's fractionally slower than the non-generator version (but not significantly): the main benefit is reduction in memory because it isn't simply returning an array of variable size (which can be a significant benefit depending on the number of results returned). The biggest drawback is the fact that the results can't easily be sorted (my non-generator version does a usort() on the results array after it's returned).

于 2013-12-06T19:04:38.357 に答える
1

最初にジェネレーターを作成したい場合は、フィボナッチの反復バージョンを使用することもできます。

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 " 
}
于 2013-11-07T14:52:58.970 に答える
0

組み合わせの再帰的なジェネレーターを次に示します (順序は重要ではなく、置換なし)。

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

出力:

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

同じことの非降伏。

于 2016-02-09T09:51:52.017 に答える
0

最近、「再帰的」ジェネレーターまたはジェネレーター委任が必要な問題に遭遇しました。最終的に、委任されたジェネレーター呼び出しを単一のジェネレーターに変換する小さな関数を作成しました。

それをパッケージに変えたので、composer でそれを要求するか、ここでソースをチェックアウトできます: hedronium/generator-nest。

コード：

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

次のように使用します。

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

上記のリンクをチェックしてください。例があります。

于 2016-12-22T11:38:24.903 に答える
-1

フィボナッチ数に対して、再帰ありとなしの 2 つのソリューションを提供しています。

function fib($n)
{
    return ($n < 3) ? ($n == 0) ? 0 : 1 : fib($n - 1) + fib($n - 2);
}
function fib2()
{
    $a = 0;
    $b = 1;
    for ($i = 1; $i <= 10; $i++)
    {
        echo $a  . "\n";
        $a = $a + $b;
        $b = $a - $b;
    }
}

for ($i = 0; $i <= 10; $i++)
{
    echo fib($i) . "\n";
}

echo fib2();
于 2013-11-15T08:34:23.223 に答える