在php中记住斐波纳契函数

Question

我已经创建了斐波那契递归版的memoized函数.我将此作为使用memoization的其他类型函数的示例.我的实现很糟糕,因为如果我将它包含在库中,这意味着global仍然可以看到变量..

这是原始的递归斐波那契函数:

function fibonacci($n) {
  if($n > 1) {
    return fibonacci($n-1) + fibonacci($n-2);
  }
  return $n;
}

我把它修改为一个memoized版本:

$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中的fibonacci函数？你能建议我更好的改进吗？我见过func_get_args()和call_user_func_array的另一种方式,但我似乎无法知道什么是好？

所以我的主要问题是:我如何正确地在php中记住fibonacci函数？或者在php中记忆fibonacci函数的最佳方法是什么？

Answer 1

好吧,Edd Mann memoize在他的文章中展示了在php中实现一个函数的绝佳方法

这是示例代码(实际上取自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);
});

请注意,global由于函数clousure和PHP的一流函数支持,它被替换的定义.

其他方案:

您可以创建一个class包含为静态成员: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的问题.虽然,不是线程保存,并且存储的密钥不是散列值.无论如何,你可以使用所有的php memoize utilites,如memoize-php$memo