[algogeeks] Re: Memorization

[Gene]

This is true when memoization is being used to merely improve
asymptotic efficiency of a single computation. (As you say, it's a
nice technique for DP, when you can often just remember one or a few
previous rows of results.)

However this is not the only use.  General memoization maintains
values persistently.  In this case memoized fib(n) will cost O(n) for
the first call.  Afterward any call for fib(i), i <= n will run in
constant time.  If there are many similar-valued calls to fib, this is
a big deal.

On Oct 11, 7:15 pm, Vandana Bachani  wrote:
> Hi Arvind,
> For the fibonacci series, we need to memoize only the the last 2 fibonacci
> numbers.
> We can even avoid recursion... So our regular fibonacci algorithm is the
> simplest example of a dynamic programming algorithm with memoization.
>
> To find nth fibonacci number:
>
> int p = 0, q = 1, f;
> for (int i  = 1; i <= n; i++)
> {
>   f = p + q;
>   p = q;
>   q = f;
>
> }
>
> But as gene mentioned, in complex programs involving dynamic programming we
> might need to access more than 1 or 2 previously obtained values. To reduce
> the burden of recalculating old values, we preserve them in a
> hash/table/array, as the case might be and access them directly from there.
> One of the most important properties of dynamic programming is that the
> solutions to sub-problems are reused, which can be achieved with
> memoization.
>
> -Vandana
>
>
>
> On Tue, Oct 11, 2011 at 3:17 AM, arvind kumar  wrote:
> > ya ya,realy sorry..typo!its MEMOIZATION.
>
> > On Mon, Oct 10, 2011 at 10:56 PM, Ankur Garg  wrote:
>
> >> Memoization ?
>
> >> On Mon, Oct 10, 2011 at 6:34 PM, arvind kumar 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.
>
> >> --
> >> 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.
>
> >  --
> > 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.- Hide quoted text -
>
> - Show quoted text -

-- 
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.

[algogeeks] Re: Memorization

[Gene]

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[1];

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  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.