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.
TypeError: '<' not supported between instances of 'NoneType' and 'int' line 23 is evaluating either go_right or go_down as None, which is peculiar.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.
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):
...