Memoization

The term memoization was coined by Donald Michie (1968) to refer to the process by which a function is made to automatically remember the results of previous computations.

Memoization is a means of lowering a function’s time cost in exchange for space cost; that is, memoized functions become optimized for speed in exchange for a higher use of computer memory space.

Consider the below method to calculate the factorial of a number,


public int factorial(int input){

if(input == 0 || input == 1){

return 1; // as 0! = 1

}

return (input * (factorial(input-1)));

}

For a particular number factorial is same always. If n! = m, then how many times you call the factorial method, it always returns m. Every time the method does the same operation and returns the same value.

Using memoziation one can cache the already calculated factorial and return the same if same input given again.


private HashMap<Integer, Integer> cache = new HashMap<Integer, Integer>();

public int factorial (int input){

if(cache.containsKey(input)){

return cache.get(input);

}

if(input == 0 || input == 1){

cache.put(input, 1);

return 1; // as 0! = 1

}

int fact = input * (factorial(input-1));

cache.put(input, fact);

return fact;

}

References: WikiPedia | Memoization in Java Using Dynamic Proxy Classes | Techniques for Automatic Memoization with Applications to Context-Free Parsing

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s