PHP中的递归生成器 [英] Recursive generators in PHP

问题描述

从PHP版本5.5开始，生成器 .我不会重复官方手册页，但是对于迭代器的简短定义来说，它们是很棒的事情.最著名的示例是:

Since version 5.5 in PHP there's such great thing as generators. I will not repeat official manual page, but they are great thing for short definition of iterators. The most-known sample is:

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实际上不是函数，而是具体类的实例:

and generator is actually not a function, but an instance of a concrete class:

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

处理完RTM内容后，现在转到我的问题.假设我们要创建斐波那契数字的生成器.通常，要获得这些，我们可以使用简单的功能:

Done with RTM stuff, now moving on to my question. Imagine that we want to create generator of Fibonacci numbers. Normally, to get those, we can use simple function:

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

让我们将其转换为某种东西，它拥有序列，而不仅仅是它的最后一个成员:

Let's transform this into something, that holds sequence and not only it's last member:

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
}

我们现在有一个函数可以返回具有完整序列的数组

We have now a function that returns array with full sequence

最后，问题部分:如何转换最新的fibonacci函数，以使其屈服我的值，而不是将它们保存在数组中?我的$n可能很大，所以我想利用生成器的好处，例如在xrange样本中.伪代码为:

Finally, the question part: how can I transform my latest fibonacci function so it will yield my values, not holding them in an array? My $n can be big, so I want to use benefits of generators, like in xrange sample. Pseudo-code will be:

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值.

But this, obviously, is crap since we can't handle with it like this way because recursion will cause object of class Generator and not int value.

奖金:获得斐波那契数列只是一个更普遍的问题的样本:在常见情况下，如何在递归中使用生成器?当然，我可以使用标准的迭代器或重写我的函数避免递归.但是我想用生成器来实现.这可能吗?这样使用这种方法值得努力吗?

Bonus: getting fibonacci sequence is just a sample for more general question: how to use generators with recursion in common case? Of course, I can use standard Iterator for that or re-write my function to avoid recursion. But I want to achieve that with generators. Is this possible? Does this worth efforts to use this such way?

推荐答案

我终于确定了递归生成器的实际用法.

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

我最近一直在研究 QuadTree 数据结构.对于不熟悉QuadTree的人来说，它们是用于地理空间索引的基于树的数据结构，并允许在定义的边界框中快速搜索所有点/位置. QuadTree中的每个节点代表映射区域的一部分，并充当存储位置的存储桶...但存储桶的大小受限制.当存储桶溢出时，QuadTree节点会拆分4个子节点，分别代表父节点的西北，东北，西南和东南区域，并开始填充这些子节点.

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.

搜索位于指定边界框内的位置时，搜索例程将从顶层节点开始，测试该存储桶中的所有位置；然后递归到子节点，测试它们是否与边界框相交，或被边界框包围，测试该集中的每个QuadTree节点，然后再次向下遍历树.每个节点可能不返回任何一个或多个位置.

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.

我在PHP中实现了基本的 QuadTree ，旨在返回结果数组；然后意识到这可能是递归生成器的有效用例，因此我实现了一个 GeneratorQuadTree ，可以在foreach中对其进行访问( )循环，每次迭代都会产生一个结果.

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.

代码太多了，无法在此处发布；但是您可以在 github 上查看实现.

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

它比非生成器版本要慢一些(但不是很慢):主要好处是减少了内存，因为它不只是返回可变大小的数组(根据结果的数量，这可能是一个重要的好处)回来).最大的缺点是无法轻易对结果进行排序(我的非生成器版本在返回结果数组后会对结果数组进行usort()处理).

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

这篇关于PHP中的递归生成器的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！