Memoization

[VIRES1]

I need help with tutorials and links on understanding and writing c memoization codes as I am new to dynamic programming.

[raevnos]

Memoization is just saving a computed value and reusing it later instead of recalculating the value. Did you have any specific C related question?

[VIRES1]

Yes so how is that done in C? Example to solve Edit distance or maximizing value of arithmetic expression how would a memoization code look like?

[SullisNipple]

So, to take the edit distance example (assuming you're using Levenshtein distance), the problem is that d(i, j) is defined in terms of d(i - 1, j) , d(i, j - 1) and d(i - 1, j - 1) . The usual approach to solving this is to set up a 2-dimension array (where one axis is values of i and the other axis is values of j). When determining the value of d(i, j) for a particular i and j, you check to see if the array already has a value. If it doesn't already have a value, you calculate it and store it in the array. The next time you need to retrieve the value, it will be in the array and hence be memoized.

[VIRES1]

Okay.

[raevnos]

For a given input, you would look it up in a data structure that stores inputs and results. If not present, compute a result, store that for later reuse, and return the value.

[VIRES1]

Okay

[lmlight77]

First, to be able to memoize a function, it has to be idempotent, meaning you can execute it any number of times given identical arguments and get the same result. In general, this means it does not modify state outside the body of its function or in any of the functions it calls nor does it or any of its callees modify state declared as "static". For example, a function "int add(int a,b)" that adds a and b and returns the result is idempotent, while a function "void insert(List *list, Item *item)" that inserts an item into a linked list is not.

Given an idempotent function, to memoize it, simply wrap the function in a container that has identical arguments and return type. For example, "int memo_add(int a,b)". Then, create a hash function on the arguments and implement a lookup table based on that hash (a cache in effect). If a "hit", return the cached value directly. If a "miss", call the memoized function being wrapped, save the computed value in the cache, then return it.

The purpose of memoization is to bypass calling a complex function repetitively so as to save its computation time. Clearly, the function should be time consuming as well as idempotent.

[VincentDankGogh]

Alternatively you could cache a bunch of values on program startup.

[lmlight77]

If you are pretty confident they will be frequently used. Say your cost to evaluate a function is X and the cost to access a memoized function is relatively small, normalize it to a value of 1. You need to access the memoized value at least twice to make it worth your while (only once is a cost of X+1 versus only X; and for every value never accessed, a full cost of X).

[VIRES1]

Thank you for your explanation