在 php 中记忆斐波那契函数

Question

我创建了斐波那契递归版本的记忆函数。我用这个作为其他类型的使用记忆功能的例子。我的实现很糟糕，因为如果我将它包含在库中，这意味着仍然可以看到 global 变量..

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

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?

Answer 1

好吧，Edd Mann 在 His post

中展示了在 php 中实现 memoize 函数的绝佳方法

这是示例代码（实际上取自 Edd Mann 的post）：

$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 定义已被替换，这要归功于函数闭包和 PHP 的第一个 class 函数支持。

其他解决方案：

您可以创建一个包含以下静态成员的 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 以及 清理缓存 的问题。虽然，$memo 不是 线程保存 并且存储的密钥不是 散列值 。无论如何，您可以使用所有 php memoize 实用程序，例如 memoize-php

Answer 2

我认为...这应该是为了记住斐波那契数列：

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

Answer 3

另一个解决方案：

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

在 php 中记忆斐波那契函数

Memoizing fibonacci function in php

php

recursion

memoization

fibonacci