Space-efficient Memoization with dicts

Python's not usually considered a good language for memory- or time-intensive tasks, but its extensive standard library and variety of built-ins make it an invaluable tool for algorithmic work.

Consider the task of memoizing a recursive function. Typically, a large d-dimensional array is used as a cache, where d is the number of parameters in the subproblem's state. This is great for bottom-up iterative dynamic programming, where the optimal solution for every state must be evaluated -- every cell of the array will be occupied, so there's no redundant space. However, many problems do not require that every state be examined. Consider a case of the unbounded knapsack problem where you have a knapsack of size 15 and 3 items available of costs 5, 7, and 11. The bottom-up approach will evaluate the optimal solution for states 1, 2, 3, 4, 6, 7, 8 and 9, none of which contribute at all to the final optimal selection of items; after all, there's no way to fill a knapsack of those sizes given those items. The top-down memoized recursion approach, on the other hand, will only evaluate states which can theoretically contribute to the optimal solution (even if they do not).

Despite the overhead created by recursive calls and a much higher proportion of cache misses, the top-down memoized approach is often a lot faster than the bottom-up dynamic programming solution. However, people will still generally use the d dimensional array for caching, even when memoizing. This leads to lots of unused cells and wasted space.

Python gives you another option: instead of an array, use a dictionary of {d-tuple representing state : optimal solution for state}. Dictionaries have extremely fast look-up times, and the amount of memory saved is substantial.

Consider the 'matrix sum' problem (as seen in Project Euler #345), a variant of the classic n-rooks problem. You're given a n x n grid (chessboard?) where each cell has a value associated with it. Your task is to place n rooks on the board such that none of them threaten another (no two rooks lie on the same row or column) and the sum of values in the cells they occupy is maximised.

This is an exponential dynamic programming problem, where the state of a subproblem has two parameters: the current row, and a binary string representing the columns that have already been occupied and cannot have rooks placed in them from now on. I don't want to elaborate too much on the solution because it's an interesting problem that's worth your attention. There are n possible values for the current row and 2ⁿ possible values for the binary string, so in total there should be n * 2ⁿ states. Let's work with n = 15. The total theoretical number of states should be 491,520, which would be the number of cells in the d-dimensional array.

However, in practice there are many states that are impossible to reach. For example, there is no state where you're on the very first row and yet all columns are already occupied. Similarly, there's no state where you're on the last row and no columns are occupied. It's possible to mathematically calculate the exact number of reachable solutions (I did it once, it's not very fun) but since this is a programming blog, I'd rather just demonstrate a solution that tells you exactly how many states must be cached.

N = 15
m = [map(int, line.split()) for line in open('matrix.txt')]

cache = {}
def dp(r, u):
    if (r,u) not in cache:
        cache[(r,u)] = 0 if r==N else max(dp(r+1, u|(1<<c)) + m[r][c] for c in xrange(N) if not u&(1<<c))
    return cache[(r, u)]

print dp(0,0), len(cache)

Output:

32768

That's right ladies and gentlemen, only 32768 states are reachable. That's 1/15th of the original memory usage. Obviously you could do the same thing in another language, but Python makes it so easy. Have fun implementing your own hash table in C :)