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?
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("%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)
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
i think... this should to to memoize a 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];
}
some 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
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With