The World of Algorithms – Memoization

In the technology world, algorithms are very important and a very integral part of the computer science field. Without them we wouldn’t be able to have and enjoy the technology we have and enjoy today.

In today’s article, we are going to talk about algorithms, in particularly memoization, which is a technique used in recursive algorithms, to improve their performance.

An array is used, to store the answers found to problems, after a recursive algorithm is rewritten, with the addition of the memoization technique.

By keeping a record of the results of given inputs, the method of memoization is utilized to ensure that the same input is not used twice to run the code. To picture memoization, imagine a data structure that has a cache system, and every time the code run through the function, it checks to see if, the same input needs to be recalculated.

Values do not have to be recalculated, because the values that have already been generated can be used, and processing can continue with those calculated values. The performance gains can be seen, when a code reaches a point, where it needs to compute values, millions or even billions of times.

Memoization speed things up in code, by taking each iteration and saving it into an array, to avoid computing each one more than once. The performance of code, can dramatically be improved by using memoization; however, no language or library support for memoization has gained traction or acceptance, in the field of computer science.

The application of memoization is specific to the code that is using the technique, since memoization is all about performance.

The term memoization was coined by Donald Michie, who proposed, a new technique to evaluate functions, which looks up the results, this process is known as the rote part. The other part of code is known as the rule part, according to Donald Michie, the rule part is the conventional computational procedure of the code.

A function can be evaluated in the rule part or the rote part, or a mixture of the two according to Donald Michie. In the memoization technique, for particular inputs to a function, normal computation might be triggered, or look up can be triggered for other inputs.

By using a mixture of lookup and normal computation, we can account for cases when the lookup fails. Functions using the memoization technique, must be able to adapt, based on the previous evaluations. Various levels of execution, such as the instruction level, block level, trace level and function level, have used memoization.

When a value enters a function, the stored computed value of the input is returned instead, if the input was already entered into the function. The program will not recalculate results, for the same input; therefore, the performance of the program increases, by using the memoization technique.

Memory will be used, with this techniques, so it is ideal to use this technique when a function has a lot of heavy and repeated calculations.

The only downsides of memoization is that not only will you have to make sure that you have enough memory to apply memoization, if the values are in the millions or billion. But you also have to keep in mind that a function that uses memoization, is more complex, than a function that does not use this techniques. Below is a implementation of memoization in PHP.

<pre>

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

</pre>

Thank you for reading this article!!!