Memo Fibonacci-Funktion in PHP

Question

Ich habe eine Memo-Funktion der rekursiven Version von Fibonacci erstellt. Ich verwende dies als ein Beispiel für andere Arten von Funktionen, die Memoization verwenden würde. Meine Umsetzung ist schlecht, da, wenn ich es in einer Bibliothek enthalten, bedeutet dies, dass die global Variable noch ..

gesehen wird

Dies ist die ursprüngliche rekursive Fibonacci-Funktion ist:

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

und ich modifiziert es ein memoized Version:

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

ich die iterative Methode verwenden Fibonacci bei der Umsetzung absichtlich nicht. Gibt es bessere Möglichkeiten, Fibonacci-Funktion in PHP Memo zu machen? Können Sie mir bessere Verbesserungen vorschlagen? Ich habe func_get_args() und call_user_func_array als eine andere Möglichkeit gesehen, aber ich kann nicht scheinen zu wissen, was besser ist?

Also meine Hauptfrage ist: Wie kann ich Fibonacci-Funktion in PHP ordnungsgemäß memo? oder Was ist der beste Weg für das Memoisieren der Fibonacci-Funktion in PHP?

Answer 1

Nun, Edd Mann zeigt eine hervorragende Möglichkeit, eine memoize Funktion in php in His post

Hier ist der Beispielcode (tatsächlich genommen von Edd Manns post) zu implementieren:

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

Beachten Sie, dass die global Definition es ist ersetzt durch Funktion Clousure und PHP's First-Class-Funktion Unterstützung.

Andere Lösung:

können Sie erstellen ein class enthält als statische Mitglieder: fibonnacciMemo und $memo. Beachten Sie, dass Sie $memo nicht mehr als globale Variable verwenden müssen, damit es keinen Konflikt mit anderen Namespaces gibt. Hier ist das Beispiel:

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) 

diese verwenden, können Sie die Verwendung von global vermeiden und auch das Problem der Reinigung des Cache. Allerdings ist $memo nicht Thread speichern und die gespeicherten Schlüssel sind keine Hashwerte. Anyways , können Sie alle php memoize utilites verwenden wie memoize-php

Answer 2

ich denke ... Dies sollte zu einer Fibonacci memoize:

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

einige Test

$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