14
$\begingroup$

In Cormen et al.'s Introduction to algorithms, section 15.3 Elements of dynamic programming explains memoization as follow:

A memoized recursive algorithm maintains an entry in a table for the solution to each subproblem. Each table entry initially contains a special value to indicate that the entry has yet to be filled in. When the subproblem is first encountered as the recursive algorithm unfolds, its solution is computed and then stored in the table. Each subsequent time that we encounter this subproblem, we simply look up the value stored in the table and return it.

And it adds, as a footnote:

This approach presupposes that we know the set of all possible subproblem parameters and that we have established the relationship between table positions and subproblems. Another, more general, approach is to memoize by using hashing with the subproblem parameters as keys.

Is there any well-know DP problems that requires (or makes it easier) to store memoized values in a dictionary rather than in a (multi dimensional)array?


Background: if this is of any use, the reason for this question is that I'm trying to motivate the notion of (self-balanced) binary search trees to people that has just seen dynamic programming.

$\endgroup$
  • $\begingroup$ In the real software I work with, memoizing can make use of the fact that a relatively expensive function (like exp, log, or pow) can be called from many different places in the code, and is frequently called several times in order with the same value from each particular code location. In that case, the "dictionary" can be a single value stored in a code-location-specific variable. $\endgroup$ – Mike Dunlavey Nov 21 '16 at 22:57
5
$\begingroup$

There are probably better examples, but here is one, off the top of my head:

Let's say you want to check whether the edit distance between two strings $S,T$ is $\le d$, and if it is, compute the edit distance. You can use the standard dynamic programming algorithm to compute the edit distance, but "prune" the computation (stop the recursion) at any place where the edit distance is known to be $>d$. This means you probably won't need to fill in the entire table; you'll only need to fill in some of the entries. Thus, using a dictionary can give a performance boost.

$\endgroup$
3
$\begingroup$

I would like to provide 2 examples.

0-1 Knapsack problem

In case of the 0-1 Knapsack problem (where W is a capacity of the knapsack and N is an amount of items), sometimes it is better to use the top-down Dynamic Programming with memoization, instead of the systematic bottom-up enumeration of entire 2D array of size WxN (especially in a case when the capacity of the knapsack W is big, but the cardinality of the set of the allowed combinations of weights of items is much smaller than W).

In this case, for the sake of economy of a memory, one may choose to make use of the dictionary for memoization instead of the 2D array.

Earley parsing algorithm

Earley parsing algorithm can be used for the parsing of statements, which belong to a context-free grammar. As opposed to the CYK algorithm (which is based on the bottom-up DP approach, and uses 2D table for memoization) - Earley parser uses the top-down approach in combination with the parsing chart for memoization.

Parsing chart contains the partially parsed grammatical productions (e.g.: given the production X → A B, and after successful matching of the A part of this production, we store the partially matched production inside the parsing chart: X → A • B, where dot points to the already matched part).

The amount of columns inside the parsing chart equal to the amount of tokens. However, in general case it might be very tricky, to estimate the amount of partially parsed grammatic productions per column (it depends on the grammar and the particular sequence of tokens).

Hence, it is more convenient to implement the parsing chart based on the dictionary data structure.

In the Natural Language Processing domain, usually Earley pareser is more convenient choice, because it doesn't require the Chomsky normal form for the grammar (and CYK does have such requirement).

$\endgroup$
0
$\begingroup$

In my experience from competitive programming, using a hash table (Python's dict or similar) is often more convenient than using an array, because any hashable data type can be used as key, such as strings, sets (frozenset in Python) or tuples like (string, int) etc. If using an array you must manually translate all keys into integers (starting at 0), which takes extra work and, as your source notes, may not be possible if you don't know the space of keys in advance. So dictionaries are rather more general than arrays.

Of course, if you can get away with using arrays it is probably faster because it avoids repeatedly computing hashes (on the other hand it requires initialising the whole array first, which takes time and memory), but it may take longer to write the code because you have to do the extra work of translating all keys into integers.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.