Remembering the fibonacci function in php

Question

I created the memoized function of the recursive version of fibonacci. I use this as an example for other kinds of functions that will use memoization. My implementation is bad, because if I include it in the library, it means that the global variable is still visible.

This is the original recursive fibonacci function:

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

and I changed it to the 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 intentionally did not use the iterative method when implementing fibonacci. Is there a better way to memoize the fibonacci function in php? Can you suggest me an improvement? I saw func_get_args() and call_user_func_array as another way, but I can't figure out which is better?

So, my main question is: How can I remember the fibonacci function in php correctly? or What is the best way to memoizing fibonacci functions in php?

Answer 1

Well, Edd Mann shows a great way to implement memoize function in php in His post

Here is a sample code (actually taken from a post by 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); }); 

Note that the global definition that it replaced is thanks to the clousure function and support for PHP first-class functions.

Another solution:

You can create a class containing both static elements: fibonnacciMemo and $memo . Note that you no longer need to use $memo as a global variable, so it will not conflict with other namespaces. Here is an 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 using global , as well as the problem of clearing the cache. Although tt $memo not a stream preservation, and stored keys do not have hashed values. In any case, you can use all memoize php utilities like memoize-php

Answer 2

I think ... this should memoize for memoacci:

 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