How to implement memoization in a PHP function?

Question

I saw it today in a reply the following code:

function fibonacci($n) {
    $a = 0;
    $b = 1;
    $c = 1;
    for ($i = 1; $i < $n ; $i++) { 
        $c = $a + $b;
        $a = $b;
        $b = $c;
    }
    return $c;
}
echo fibonacci(100) ."\n";

This function has a performance problem, because each call recalculates the entire Fibonacci sequence up to the last number. I know how to solve this problem in other languages using memoisation^{details in en} - a kind of internal cache of the function. Is it possible to do the same in PHP? How?

Answer 1

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.