0

Is there a simple way to memoize results? my dynamic programming solution is potentially calling the same function, with the same parameters, multiple times.

I think memoizing would add speed. However, I'm not sure what the best approach is. Here's the original function, which works, albeit, it's not memoized:

def dim(M):
    rows = len(M)
    cols = len(M[0])
    return rows, cols

def minimumCostPath(matrix, i=0, j=0, total=0):
    r,c = dim(matrix)
    if i+1 < r and j+1 < c:
        down = matrix[i+1][j]
        right = matrix[i][j+1]
        return min(minimumCostPath(matrix, i+1, j, total+down),
                    minimumCostPath(matrix, i, j+1, total+right))
    elif i+1 < r:
        right = matrix[i+1][j]
        return minimumCostPath(matrix, i+1, j, total+right)
    elif j+1 < c: 
        down = matrix[i][j+1]
        return minimumCostPath(matrix, i, j+1, total+down)
    else:
        return total + matrix[0][0]       

test = [ [23,70,54], 
         [86,5,13], 
         [86,62,77], 
         [60,37,32], 
         [88,58,98] ]
total = minimumCostPath(test)
>>>
318

Below is my attempt to memoize this function with a matrix (nested list) of zeros.

def solution(matrix):
  cache = [[0 for j in range(len(matrix[0]))] for i in range(len(matrix))] 
  return helper(matrix, cache, i=0, j=0, total=0) 

def helper(matrix, cache, i=0, j=0, total=0):
    r,c = dim(matrix)
    if i+1 < r and j+1 < c:
        down = matrix[i+1][j]
        right = matrix[i][j+1]
        
        if cache[i+1][j] > 0:
          go_down = cache[i+1][j] + down
        else:
          go_down = helper(matrix, cache, i+1, j, total+down)
          cache[i+1][j] = go_down
        
        if cache[i][j+1] > 0 :
          go_right = cache[i][j+1] + right
        else:
          go_right = helper(matrix, cache, i, j+1, total+right)
          cache[i][j+1] = go_right 
        
        return min(go_down, go_right)
    elif i+1 < r:
        down = matrix[i+1][j]
        if cache[i+1][j] > 0:
          go_down = cache[i+1][j] + down
        else:
          go_down = helper(matrix, cache, i+1, j, total+down)
          cache[i+1][j] = go_down  
          return go_down     
    
    elif j+1 < c: 
        right = matrix[i][j+1]
        if cache[i][j+1] > 0 :
          go_right = cache[i][j+1] + right
        else:
          go_right = helper(matrix, cache, i, j+1, total+right)
          cache[i][j+1] = go_right         
        return go_right
    
    else:
        return total + matrix[0][0]


solution(test)

Two problems.

  1. I'm getting an error, TypeError: '<' not supported between instances of 'NoneType' and 'int' line 23 is evaluating either go_right or go_down as None, which is peculiar.
  2. It's not very succinct or pretty. Perhaps a better helper function would simplify the code.

Lastly, I do understand that there is the bottom-up approach, which does not use recursion but rather fills in table cells, iteratively. At this point, I'm wondering how the recursive solution could leverage memoization, not start from scratch on bottom up implementation.

Improve this question

3 Answers 3

Reset to default
1

Firstly, your bug: in one of the branches, return go_down is indented too far, so the non-recursive calculation of go_down won't return the value; instead, it'll fall off the end of the function and return the implicit None

As far as memoization is concerned, there are cache and lru_cache decorators in functools. Last I used it (about 5 years and many versions ago) it was a bit slow, only really useful for external data (disk or network); you'll have to measure whether it performs satisfactorily for you. It's probably improved a lot since then.

If you do need to implement a cache manually (if the functools.cache decorator proves to be too slow), a pattern with the caching separate is probably better, to avoid mixing of concerns:

minimumCostPath_cache = {}

def minimumCostPath(matrix, i=0, j=0):
    try:
        return minimumCostPath_cache[i, j]
    except KeyError:
        result = minimumCostPath_cache[i, j] = minimumCostPath_raw(matrix, i, j)
        return result

def minimumCostPath_raw(matrix, i=0, j=0):
   ...

To avoid global variables and calls with different matrices interfering with each other, you might do this in a class:

class MinimumCostPath:
    def __init__(self, matrix):
        self.cache = {}
        self.matrix = matrix

    def calculate(self, i=0, j=0):
        try:
            return self.cache[i, j]
        except KeyError:
            result = self.cache[i, j] = self.calculate_uncached(i, j)
            return result

    def calculate_uncached(self, i=0, j=0):
        ...
Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

As far as lru_cache goes, I tried using this and on the test problem, I observed 1 hit & 52 misses. I believe the issue to the function arguments. Matrix is constant, i & j will update but only have 20 unique combinations. Total, however, is very path dependent; thus caching on (matrix, i, j, total) in practice means that it's highly unlikely that the same function call be executed twice. Your answer seems to be aware of this as you have omitted total from your functions minimumCostPath and minimumCostPath_raw.
Yeah, need to cache only on what's relevant... I haven't traced through the code in detail, but I think instead of passing total into the recursive call, we could instead add it up on the returned result? That is, instead of using minimumCostPath(matrix, i+1, j, total+down) we could use minimumCostPath(matrix, i+1, j) + down which would be more cache-friendly?
0

If you have Python 3.9, get to know the @cache decorator in order to achieve worry free memoization

@cache
def factorial(n):
    return n * factorial(n-1) if n else 1

>>> factorial(10)      # no previously cached result, makes 11 recursive calls
3628800
>>> factorial(5)       # just looks up cached value result
120
>>> factorial(12)      # makes two new recursive calls, the other 10 are cached
479001600

source: https://docs.python.org/3/library/functools.html

Improve this answer

7 Comments

In older versions, you can use lru_cache which has been there at least since 2.7
yes as well as specify the maxsize argument or @lrucache(maxsize=None) however @cache is the new preferred way to achieve OP's intention
Yeah; just for anyone reading with older versions of Python
FYI, 'lists' are immutable so to use lru_cache or cache, I would need to pass tuple type arguments. Just a heads up for anyone else who is interested on using this decorator for a function which receives lists/tuples as argument.
OK. It's straight out now... ;-)
|
0 
from functools import lru_cache
@lru_cache(maxsize=None, typed=False)
def minimumCostPath(matrix, i=0, j=0):
    r,c = len(M), len(M[0])
    if i+1 < r and j+1 < c:
        down = matrix[i+1][j]
        right = matrix[i][j+1]
        return min(minimumCostPath(matrix, i+1, j) + down,
                    minimumCostPath(matrix, i, j+1) + right)
    elif i+1 < r:
        right = matrix[i+1][j]
        return minimumCostPath(matrix,i+1, j) + right
    elif j+1 < c: 
        down = matrix[i][j+1]
        return minimumCostPath(matrix,i, j+1) + down
    else:
        return matrix[0][0]

Moved the total parameter out and used lru_cache to save previous function calls. It had 8 hits, 15 misses and current size 15.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.