Memoizing funzione fibonacci in php

Question

Ho creato una funzione memoized della versione ricorsiva di Fibonacci. Lo uso come esempio per altri tipi di funzioni che utilizzerebbero la memoizzazione. mia implementazione è male perché se includo in una libreria, che significa che la variabile global è ancora visto ..

Questo è l'originale ricorsiva funzione di Fibonacci:

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

e ho modificato per un versione 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; 
    } 
} 

ho volutamente non ha utilizzato il metodo iterativo nell'attuazione Fibonacci. C'è qualche modo migliore per memorizzare la funzione Fibonacci in PHP? Puoi suggerirmi miglioramenti migliori? Ho visto func_get_args() e call_user_func_array come un altro modo, ma non riesco a capire cosa è meglio?

Quindi la mia domanda principale è: Come posso memorizzare correttamente la funzione Fibonacci in PHP? o Qual è il modo migliore per memorizzare la funzione Fibonacci in PHP?

Answer 1

Beh, Edd Mann mostra un ottimo modo per implementare una funzione memoize in php in His post

Ecco il codice di esempio (in realtà tratto da post di 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); 
}); 

Si noti che il La definizione global è stata sostituita grazie alla funzione clousure e al supporto delle funzioni di prima classe di PHP.

Altro soluzione:

È possibile creare un class contenente come membri statici: fibonnacciMemo e $memo. Si noti che non è più necessario utilizzare $memo come variabile globale, quindi non darà alcun conflitto con altri spazi dei nomi. Ecco l'esempio:

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) 

Usando questo, si evita l'uso di global e anche il problema della pulizia della cache . Anche se, $memo non è thread risparmi e le chiavi memorizzate non sono valori hash. In ogni modo, è possibile utilizzare tutti i programmi di utilità php Memoize come memoize-php

Answer 2

penso ... questo dovrebbe ad ad Memoize un Fibonacci:

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

qualche prova

$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