I've found examples such as factorial calculation to explain memoization. These are helpful but I'm looking for a deeper understanding.

I'm wondering if someone can describe a real world application of this technique and why they used it instead of recursion or whatever else they felt using memoization might help them optimize.

I've found examples such as factorial calculation to explain memoization. These are helpful but I'm looking for a deeper understanding.

I'm wondering if someone can describe a real world application of this technique and why they used it instead of recursion or whatever else they felt using memoization might help them optimize.

• php
• javascript
• recursion
• memoization

3 Answers 3

Memoization is a little more specific than just caching.

Think about searching for an element in the DOM using a selector, like you might with jQuery. Say, $('.some-selector'). In this context, I'm calling the function $, telling it to find for me all elements that have the CSS selector '.some-selector'. Let's say that the document is large, and I need to call $('.some-selector') many times.

You can make the assumption that every call to $('.some-selector') is going to return the same results, and therefore, doing the actual processing each time it is invoked is wasted effort. Therefore, $ could use the argument ('.some-selector', in this case) as a key in some lookup table or dictionary. The first time the function is invoked with that argument, it is processed normally, the results are placed in the dictionary using the argument as a key, and the results are returned. Subsequent calls will find that the key has a value in the dictionary representing the results that have already been calculated, so it just returns those previous results. The net effect is that you don't waste time finding results that you already know.

A little crude JavaScript example:

var _dictionary = {};

function $(selector) {
   if (_dictionary[selector]) return _dictionary[selector]; // lookup the results of the selector and return them if they exist

   // otherwise, execute the function's logic normally
   // TODO: search logic
   var results = doSearch();

   _dictionary[selector] = results;

   return results;

}

This link goes into more detail, and even includes a generic memoize JS function that could be used for any other function.

You could use memoization, for all kinds of caching. For example you could cache results of some ajax call.

Example:

var cache = new Array()

function memoized_ajax(url, callback) (
  if (cache[url]) {      
    callback(cache[url]);  // we already know the result for this url
  }
  else {
    $.ajax({
      url: url,
      success: function(data) {
        cache[url] = data;   // we will remember result for this url
        callback(data);
    });
  }
}

You can delete this if you want, since I can not really answer your question (that is give you an example of using memoization), but I would like to point out that memoization is meant to solve a pletely different type of problem than recursion. Memoization stores the output of a method invocation so that deriving the result of future identical method calls (same parameters and object bindings) is a lookup rather than a putation. Recursion is a type of function algorithm. This means that they are not opposed since you can memoize the output of a recursive function.