Python: lru_cache make leetcode's dungeon game more slower

Question

I'm trying to implement a recursive+momoize version for leetcode's dungeon game question.

I tried to use @lru_cache():

________________________________________________________
Executed in   14.22 secs    fish           external
   usr time   14.13 secs  101.00 micros   14.13 secs
   sys time    0.04 secs  498.00 micros    0.04 secs

And comment it to make it unavailable:

________________________________________________________
Executed in   11.73 secs    fish           external
   usr time   11.65 secs  123.00 micros   11.65 secs
   sys time    0.04 secs  556.00 micros    0.04 secs

It sounds a lot like the lru_cache won't help in this case, just wondering if anything that I'd missed?

from typing import List
from functools import lru_cache

class Solution:
    def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:
        height = len(dungeon)
        width = len(dungeon[0])

        @lru_cache()
        def helper(start_x, start_y, acc, min):
            cur = dungeon[start_y][start_x]

            acc = cur + acc
            if cur < 0 and acc < min:
                min = acc

            if start_x == width - 1 and start_y == height - 1:
                return min

            if start_x < width - 1:
                right_res = helper(start_x+1, start_y, acc, min)
            else:
                right_res = float("-inf")

            if start_y < height - 1:
                down_res = helper(start_x, start_y+1, acc, min)
            else:
                down_res = float("-inf")

            ret = max(down_res, right_res)
            return ret


        res = helper(0,0,0,0)
        return 1 if res > 0 else abs(res)+1

def main():
    sol = Solution()
    long_case = [[2,-8,-79,-88,-12,-87,-5,-56,-55,-42,18,-91,1,-30,-36,42,-96,-26,-17,-69,38,18,44,-58,-33,20,-45,-11,11,15,-40,-92,-62,-51,-23,20,-86,-2,-90,-64,-100,-42,-16,-55,29,-62,-81,-60,7,-5,31,-7,40,19,-53,-81,-77,42,-87,37,-43,37,-50,-21,-86,-28,13,-18,-65,-76],
[-67,-23,-62,45,-94,-1,-95,-66,-41,37,33,-96,-95,-17,12,30,-4,40,-40,-89,-89,-25,-62,10,-19,-53,-36,38,-21,1,-41,-81,-62,3,-96,-17,-75,-81,37,32,-9,-80,-41,-13,-58,1,40,-13,-85,-78,-67,-36,-7,48,-16,2,-69,-85,9,15,-91,-32,-16,-84,-9,-31,-62,35,-11,28],
[39,-28,1,-31,-4,-39,-64,-86,-68,-72,-68,21,-33,-73,37,-39,2,-59,-71,-17,-60,4,-16,-92,-15,10,-99,-37,21,-70,31,-10,-9,-45,6,26,8,30,13,-72,5,37,-94,35,9,36,-96,47,-61,15,-22,-60,-96,-94,-60,43,-48,-79,19,24,-40,33,-18,-33,50,42,-42,-6,-59,-17],
[-95,-40,-96,42,-49,-3,6,-47,-38,31,-25,-61,-18,-52,-80,-55,29,27,22,6,29,-89,-9,14,-77,-26,-2,-7,-2,-64,-100,40,-52,-15,-76,13,-27,-83,-70,13,-62,-54,-92,-71,-65,-18,26,37,0,-58,4,43,-5,-33,-47,-21,-65,-58,21,2,-67,-62,-32,30,-4,-46,18,21,2,-5],
[-5,34,41,11,45,-46,-86,31,-57,42,-92,43,-37,-9,42,-29,-3,41,-71,13,-8,37,-36,23,17,-74,-12,-55,-18,-17,-13,-76,-18,-90,-5,14,7,-82,-19,-16,44,-96,-88,37,-98,8,17,9,-2,-29,11,-39,-49,-95,20,-33,-37,-42,42,26,-28,-21,-44,-9,17,-26,-27,24,-60,-19]]
    print(sol.calculateMinimumHP(long_case))


if __name__ == '__main__':
    main()

Answer 1

With your example input, the function helper gets called with 400568 different parameters. According to its documentation lru_cache by default caches the parameters and results of the last 128 function calls.

Try setting maxsize to something more reasonable, or use a non-lru cache (@lru_cache(maxsize=None), or simply @cache).