You can cache the data, which is the basic principle of memoization, something like that:
function fibonacci($n) {
static $cache = array();
if (isset($cache[$n])) return $cache[$n];
$a = 0;
$b = 1;
$c = 1;
for ($i = 1; $i < $n ; $i++) {
$c = $a + $b;
$a = $b;
$b = $c;
}
$cache[$n] = $c;
return $c;
}
Behold working in the ideone. And in the repl it.. Also put on the Github for future reference.
To static local variable was used to keep the status between function calls. While the code is running it retains its value. It works similarly to a global variable, i.e., its lifetime is global. But its scope is local.
This solution is simplified and naive, has no type of persistence and does not scale well. It would have to do something well more elaborate to meet other not so trivial demands. But it solves legal for most.
If the concern is performance, in this type of algorithm, it is interesting to pre-calculate a large sequence of numbers more likely to use and allocate in the array already in the code. Of course you may have a higher memory consumption. To some extent it pays off.
This technique does not work in every type of algorithm, especially in nondeterministic algorithms, what is not the present case.
But there is a way to get a good improvement without pre-calculating at development time, even if it will consume more memory without potentially needing all the values.
function fibonacci($n) {
static $cache = array();
static $prox = 3;
$cache[0] = 0;
$cache[1] = 1;
$cache[2] = 1;
if ($n < $prox) {
echo "cache -> "; //está aqui só para mostrar que entrou aqui
return $cache[$n];
}
for ($i = $prox; $i <= $n; $i++) $cache[$i] = $cache[$i - 1] + $cache[$i - 2];
echo $i - $prox . " passos -> "; //está aqui só para mostrar que entrou aqui
$prox = $n + 1;
return $cache[$n];
}
Behold working in the ideone. And in the repl it.. Also put on the Github for future reference.
If you want to optimize at development time, you can add $cache[3] = 2;
, $cache[3] = 3;
, $cache[4] = 5;
, etc. The gain will be small.
If you know you’re going to use it in a large sequence and you know the highest value (even approximate) can help by having it run this higher number, so populate the cache.
To answer that originated this question now has a calculation variation that does not need to go through every sequence. This decreases the need for the cache.
Has a module to help caching more intensively. Probably they have thought about a lot that can happen in this situation and tested well. But it can be a cannon to kill bird.
I found this another solution.
I particularly prefer the solution using loop because it is more natural in data sequence. Recursion is for trees and similar.
It would be possible to explain briefly what memoization is?
– rray
@rray Defini very briefly, the answers can explain more :)
– bfavaretto
Already helped a little, can tweet this explanation :D
– rray
+1 for the question, and two comments: 1) this function has no recursive calls, so it would not benefit from memoization; 2) this implementation is reasonably good for computing a single element of the sequence (linear with input)only if several are calculated is there processing waste (i.e. without seeing the linked question this is not clear).
– mgibsonbr
I found an interesting article on the subject: http://eddmann.com/posts/implementing-and-using-memoization-in-php/
– Wallace Maxters
@mgibsonbr Putz, I was stupid not to see that this function was not recursive. I heard "Fibonacci" and immediately came to mind the ideas of recursion and memoization. And I left asking without having read the code carefully :P
– bfavaretto