logo标签列表

在PHP中对斐波那契函数进行记忆化

phprecursionfibonaccimemoization
6
我创建了一个斐波那契递归函数的记忆化版本。 我将其用作其他需要使用记忆化的函数的示例。 我的实现很差，因为如果我将其包含在库中，那么就意味着全局变量仍然可见。 这是原始的递归斐波那契函数：
function fibonacci($n) {
  if($n > 1) {
    return fibonacci($n-1) + fibonacci($n-2);
  }
  return $n;
}

我将其修改为一个记忆化版本：

$memo = array();
function fibonacciMemo($n) {
  global $memo;
  if(array_key_exists($n, $memo)) {
    return $memo[$n];
  }
  else {
    if($n > 1) {
      $result = fibonacciMemo($n-1) + fibonacciMemo($n-2);
      $memo[$n] = $result;
      return $result;
    }
    return $n;
  }
}

我在实现斐波那契数列时故意没有使用迭代方法。有没有更好的方法来记忆化php中的斐波那契函数？你能给我提供更好的改进建议吗？我看到了func_get_args()和call_user_func_array作为另一种方式，但我似乎不知道哪种更好？

所以我的主要问题是：如何正确地在php中进行斐波那契函数的记忆化？或者在php中记忆化斐波那契函数的最佳方法是什么？

将$memo作为fibonacciMemo的参数传递？虽然不太优雅 :( - Robin Curbelo
好的，我认为这也是可能的，但我正在寻找迄今为止最好的此函数实现.. :) - catzilla
请查看来自 Nspl 的 memoized 函数。 - Ihor Burlachenko
5个回答
6

嗯，Edd Mann在他的文章中展示了一种在PHP中实现memoize函数的优秀方法。

这是示例代码（实际上来自Edd Mann的文章）：

$memoize = function($func)
{
    return function() use ($func)
    {
        static $cache = [];

        $args = func_get_args();

        $key = md5(serialize($args));

        if ( ! isset($cache[$key])) {
            $cache[$key] = call_user_func_array($func, $args);
        }

        return $cache[$key];
    };
};

$fibonacci = $memoize(function($n) use (&$fibonacci)
{
    return ($n < 2) ? $n : $fibonacci($n - 1) + $fibonacci($n - 2);
});

请注意，由于函数闭包和PHP的一级函数支持，全局定义被替换了。 其他解决方案： 您可以创建一个包含静态成员fibonnacciMemo和$memo的类。请注意，您不再需要将$memo用作全局变量，因此它不会与其他命名空间产生冲突。 以下是示例：
class Fib{
    //$memo and fibonacciMemo are static members
    static $memo = array();
    static function fibonacciMemo($n) {
      if(array_key_exists($n, static::$memo)) {
        return static::$memo[$n];
      }
      else {
        if($n > 1) {
          $result = static::fibonacciMemo($n-1) + static::fibonacciMemo($n-2);
          static::$memo[$n] = $result;
          return $result;
        }
        return $n;
      }
    }
}

//Using the same method by Edd Mann to benchmark 
//the results

$start = microtime(true);
Fib::fibonacciMemo(10);
echo sprintf("%f\n", microtime(true) - $start);
//outputs 0.000249

$start = microtime(true);
Fib::fibonacciMemo(10);
echo sprintf("%f\n", microtime(true) - $start);
//outputs 0.000016 (now with memoized fibonacci)

//Cleaning $memo
Fib::$memo = array();
$start = microtime(true);
Fib::fibonacciMemo(10);
echo sprintf("%f\n", microtime(true) - $start);
//outputs 0.000203 (after 'cleaning' $memo)

使用此方法，您可以避免使用global以及清除缓存的问题。尽管如此，$memo并不是线程安全的，并且存储的键不是哈希值。无论如何，您可以使用所有的php记忆化实用工具，例如memoize-php。
是的，我也看到了这篇文章，非常详细和有用。但是它调用函数的方式不同：$fibonacci(10)... 这会对通常的函数调用 fibonacci(10) 产生重大的改变或差异吗？我认为这个实现实际上并不是记忆化，而是一般的缓存，这也得到了你分享的帖子中的一个评论的支持：同时在维基百科上也有提到：虽然与缓存相关，但记忆化是指此优化的特定情况，将其与缓存形式（如缓冲或页面替换）区分开来。 - catzilla
$fibonacci(10)和fibonacci(10)之间没有区别，前者是一个对象，其值是一个匿名函数（不像后者是一个函数声明）。我在帖子上看到了这个评论，问题出在内存：没有办法清除缓存并且占用了大量的内存。虽然它既不是缓冲也不是页面置换。 - Robin Curbelo
谢谢提供的信息，你的第二个解决方案对我很有效。我只是不太方便在斐波那契问题中使用静态类方法。但我认为使用静态属性可以大大减少前面调用的计算时间。至于第一个解决方案，我想试着测试和研究一下。我认为你的答案值得投票支持。无论如何，还是非常感谢。 :) - catzilla
3
我认为...这应该是用记忆化来实现斐波那契数列：
function fib($n, &$computed = array(0,1)) {
    if (!array_key_exists($n,$computed)) {
        $computed[$n] = fib($n-1, $computed) + fib($n-2, $computed);   
    }
    return $computed[$n];
}

有些测试

$arr =  array(0,1);
$start = microtime(true);
fib(10,$arr);
echo sprintf("%f\n", microtime(true) - $start);
//0.000068

$start = microtime(true);
fib(10,$arr);
echo sprintf("%f\n", microtime(true) - $start);
//0.000005

//Cleaning $arr
$arr =  array(0,1);
$start = microtime(true);
fib(10,$arr);
echo sprintf("%f\n", microtime(true) - $start);
//0.000039
嗨，是的，这种方法也可以运行，而且它也有好处。但是问题在于你需要在每个fib()函数的声明中包含参数$arr。最好在使用fib()函数时隐藏$arr参数。 - catzilla
不是真的，如果你看函数签名，数组在那里声明了，如果你不把数组传递给函数，它会在每次调用时重新初始化，所以它是隐藏的，但是，如果你计划多次使用该函数，那么你可以声明你的数组并使用它，你甚至可以将其序列化、存储和稍后重新加载，使用相同的函数而不进行修改... - Javier Neyra
嗨，我尝试了这个方法，是的，它非常好用。也许我误解了$computed参数的使用方式，但它确实很好用！到目前为止，这是我遇到的最简单的记忆化斐波那契函数..！我将尝试对比这个函数与其他斐波那契实现的性能，并比较结果...感谢您的回答！ - catzilla
1
这是一个记忆化斐波那契数列的实现：
function fib(int $n, array &$memo = [0,1,1]) : float {

    return $memo[$n] ??  $memo[$n] = fib($n-1, $memo) + fib($n-2, $memo);

}

调用

echo fib(20); // 6765
很酷的是看到使用最新 PHP 特性的答案；写这个问题时，最新的 PHP 版本是 5.7，它没有这个 null 合并运算符。 - catzilla
0

另一种解决方案：

function fib($n, &$memo = []) {

    if (array_key_exists($n,$memo)) {
        return $memo[$n];
    }

    if ($n <=2 ){
        return 1;
    }

    $memo[$n] = fib($n-1, $memo) + fib($n-2, $memo);

    return $memo[$n];
}

性能：

$start = microtime(true);
fib(100);
echo sprintf("%f\n", microtime(true) - $start);
// 0.000041
-1
            function fibMemo($n)
            {

                static $cache = [];
                //print_r($cache);
                if (!empty($cache[$n])) {
                    return $cache[$n];
                } else {
                    if ($n < 2) {
                        return $n;
                    } else {
                        $p   = fibMemo($n - 1) + fibMemo($n - 2);
                        $cache[$n]  = $p;
                        return $p;
                    }
                }
            }
            echo fibMemo(250);
1
请在您的答案中添加一些解释，以便其他人可以从中学习。此外，请分享一下您的解决方案为什么值得成为一个超过七年的问题的答案。 - Nico Haase
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接