рекурсия — Мемоизация функции Фибоначчи в переполнении стека

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?

4

fibonacci memoization php recursion

Решение

Другие решения

я думаю … это должно запоминать фибоначчи

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

2

Источник

Accepted Answer

Ну, Эдд Манн показывает отличный способ реализовать memoize функция в PHP в Его пост

Вот пример кода (на самом деле взят из поста Эдда Манна):

$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 а также проблема очистка кеша. Althought, $memo не является сохранить поток и ключи хранятся нет хешированные значения.
В любом случае, вы можете использовать все утилиты php memoize, такие как memoize-PHP

6