How to implement memoization in a PHP function?

Question

How to implement memoization in a PHP function?

Navigation

#1 by (16 votes)

18

I saw today at answer 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 to the last number. I know solve this problem in other languages using memoization detalhes in en - a kind of internal cache function. Is it possible to do the same in PHP? How?

php design-pattern

asked by anonymous 15.12.2015 / 17:45

1 answer

Query indexes in MySQL How to undo a "git add" before a commit?

score 16 · Accepted Answer

It is possible to cache the data, which is the basic principle of memoization, something like this:

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;
}

See working on ideone .

The static local variable was used to maintain the between the function calls. While the code is running it maintains its value. It works similarly to a global variable, ie its lifetime is global. But its scope is local .

This solution is simplified and naive, does not have any type of persistence and does not scale well. It would have to do something much more elaborate to meet other not so trivial demands. But it resolves legal for most.

If the concern is performance, in this type of algorithm, it is interesting to pre-calculate a large sequence of most likely numbers of use and allocate in the array already in the code. Of course you could have a higher memory consumption. To some extent it pays off.

This technique does not work on all sorts of algorithms, especially in non-deterministic algorithms, which is not the if present.

But there is a way to make a good upgrade without pre-calculating at development time, even though 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];
}

See working on ideone .

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 that you will use a large sequence and know the highest value (even approximate) can help by running this larger number, so populate the cache.

The answer that originated this question now has a calculation variant that does not have to go through every sequence. This reduces the need for caching.

You have a module to help cache more intensively. They probably thought of a lot that could happen in this situation and tested well. But it could be a cannon to kill bird.

I found this other solution .

Particularly I prefer the solution using loop because it is more natural in sequence of data. Recursion is for trees and the like.