Funkcja memoizing fibonacci w php

Question

Stworzyłem zapamiętaną funkcję rekurencyjnej wersji fibonacci. Używam tego jako przykładu dla innych rodzajów funkcji, które używają notowania. Moja implementacja jest złe, ponieważ jeśli umieścić go w bibliotece, co oznacza, że ​​zmienna global jest nadal postrzegane ..

Jest to oryginalna rekurencyjna funkcja Fibonacci:

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

i modyfikować go do wersja zapamiętana:

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

Celowo nie użyłem metody iteracyjnej w implementacji fibonacci. Czy istnieją lepsze sposoby na zapamiętanie funkcji fibonacci w php? Czy możesz zaproponować mi lepsze ulepszenia? Widziałem func_get_args() i call_user_func_array jako inny sposób, ale nie mogę wydawać się wiedzieć, co jest lepsze?

Moje główne pytanie brzmi: Jak mogę poprawnie zapamiętać funkcję fibonacci w php? lub Jaki jest najlepszy sposób na zapamiętanie funkcji fibonacci w php?

Answer 1

Cóż, Edd Mann pokazuje doskonały sposób zaimplementować memoize funkcję w php w His post

Oto przykładowy kod (w rzeczywistości pochodzi z postu EDD Manna):

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

Zauważ, że global Definicja jest zastąpiona dzięki funkcji clousure i obsłudze pierwszej klasy PHP.

Inne rozwiązanie:

Można utworzyć class zawierające członków jako statycznych: fibonnacciMemo i $memo. Zauważ, że nie musisz już używać $memo jako zmiennej globalnej, więc nie spowoduje to żadnego konfliktu z innymi obszarami nazw. Oto przykład:

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) 

Używanie tego uniknąć użycia global a także problem czyszczenie cache. Althought, $memo nie jest zapisanie wątku i przechowywane klucze nie są wartości mieszające. Tak czy inaczej, można korzystać z wszystkich programów narzędziowych, takich jak php memoize memoize-php

Answer 2

myślę ... to powinien się do memoize się Fibonacciego:

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]; 
} 

niektóre testy

$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