I’ve created a memoized function of the recursive version of fibonacci.
I use this as an example for other kinds of functions that would use memoization.
My implementation is bad since if I include it in a library, that means that the global
variable is still seen..
This is the original recursive fibonacci function:
function fibonacci($n) { if($n > 1) { return fibonacci($n-1) + fibonacci($n-2); } return $n; }
and I modified it to a 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; } }
I purposely didn’t use the iterative method in implementing fibonacci.
Is there any better ways to memoize fibonacci function in php? Can you suggest me better improvements? I’ve seen func_get_args()
and call_user_func_array
as another way but I can’t seem to know what is better?
So my main question is: How can I memoize fibonacci function in php properly? or What is the best way in memoizing fibonacci function in php?
Advertisement
Answer
Well, Edd Mann shows an excellent way to implement a memoize
function in php in His post
Here is the example code (actually taken from Edd Mann’s 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); });
Notice that the global
definition it’s replaced thanks to function clousure and PHP’s first-class function support.
Other solution:
You can create a class
containing as static members: fibonnacciMemo
and $memo
. Notice that you don’t longer have to use $memo
as a global variable, so it won’t give any conflict with other namespaces.
Here is the example:
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("%fn", microtime(true) - $start); //outputs 0.000249 $start = microtime(true); Fib::fibonacciMemo(10); echo sprintf("%fn", microtime(true) - $start); //outputs 0.000016 (now with memoized fibonacci) //Cleaning $memo Fib::$memo = array(); $start = microtime(true); Fib::fibonacciMemo(10); echo sprintf("%fn", microtime(true) - $start); //outputs 0.000203 (after 'cleaning' $memo)
Using this, you avoid the use of global
and also the problem of cleaning the cache. Althought, $memo
is not thread save and the keys stored are no hashed values.
Anyways, you can use all the php memoize utilites such as memoize-php