Memoization just adds a persistent map for the memoized function. It
stores mappings from tuples of function arguments to the corresponding
return value. Each time the function is called, its memoized version
first checks the map to see if a result has already been computed. If
so, it just returns the previously computed value. If not, it
computes the value and saves it in the map before returning it.
// Non-memoized version.
int fib(int n)
{
return (n <= 1) ? n : fib(n - 1) + fib(n - 2);
}
// Memoized version.
int fib_map[10000];
int fib(int n)
{
// Return cached value if there is one.
if (fib_map[n])
return fib_map[n] ;
// Otherwise find cache value and return it.
return fib_map[n] = (n <= 1) ? n : fib(n - 1) + fib(n - 2);
}
Of course if you have a function with complex arguments, the map must
become a real hash table or similar efficient lookup structure.
On Oct 10, 3:04 pm, arvind kumar <arvindk...@gmail.com> wrote:
> Can anyone tell me how to go about with the memorization technique to
> retrieve values from already stored values,in case of eveluating
> sequences(fibonacci series,etc).?
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
