PHP中的递归生成器

Question

介绍

从PHP 5.5版开始,就像生成器一样出色.我不会重复官方手册页,但它们对于迭代器的简短定义是很好的.最着名的样本是:

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
}

和生成器实际上不是一个函数,而是一个具体类的实例:

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

问题

完成RTM的东西,现在继续我的问题.想象一下,我们想要创建Fibonacci数的生成器.通常,为了获得这些,我们可以使用简单的功能:

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或重写我的函数以避免递归.但我想用发电机实现这一目标.这可能吗？这是否值得努力使用这种方式？

Answer 1

因此,在尝试创建递归生成器函数时遇到的问题是,一旦超过第一个深度级别,每个后续的yield都会屈服于其父调用而不是迭代实现(循环).

从php 7开始,添加了一个新功能,允许您从后续的生成器函数中获取.这是新的生成器委派功能:https://wiki.php.net/rfc/generator-delegation

这允许我们从后续的递归调用中产生,这意味着我们现在可以使用生成器有效地编写递归函数.

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

这给出了以下输出..

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

Answer 2

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

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

搜索位于指定边界框内的位置时,搜索例程从顶级节点开始,测试该存储桶中的所有位置; 然后递归到子节点,测试它们是否与边界框相交,或者是否被边界框包围,测试该集合中的每个QuadTree节点,然后再次通过树再次递归.每个节点可以返回任何一个或多个位置.

我在PHP中实现了一个基本的QuadTree,旨在返回一组结果; 然后意识到它可能是一个递归生成器的有效用例,所以我实现了一个可以在foreach()循环中访问的GeneratorQuadTree,每次迭代都会产生一个结果.

对于递归生成器来说,这似乎是一个更有效的用例,因为它是一个真正的递归搜索函数,并且因为每个生成器可能不返回一个或多个结果而不是单个结果.实际上,每个嵌套生成器都在处理搜索的一部分,通过其父级将结果反馈到树中.

这里的代码太多了,无法发布; 但你可以看看github上的实现.

它比非生成器版本慢一点(但不是很明显):主要的好处是内存减少,因为它不是简单地返回一个可变大小的数组(根据返回的结果数量,这可能是一个显着的好处).最大的缺点是结果无法轻松排序(我的非生成器版本在返回后对结果数组执行了usort()).