python dictionary.get vs in dictionary-CodePudding

This piece of code exceeds the time limit.

class Solution:
    def numRollsToTarget(self, dices: int, faces: int, target: int) -> int:
        
        dp = {}
        def ways(t, rd):
            if t == 0  and rd == 0: return 1
            if t <= 0 or rd <= 0: return 0
            if  dp.get((t,rd)): 
                return dp[(t,rd)]
            dp[(t,rd)] = sum(ways(t-i, rd-1) for i in range(1,faces 1))
            return dp[(t,rd)]
        
        return ways(target, dices) % (10**9   7)

While this does not:

class Solution:
    def numRollsToTarget(self, dices: int, faces: int, target: int) -> int:
        
        dp = {}
        def ways(t, rd):
            if t == 0  and rd == 0: return 1
            if t <= 0 or rd <= 0: return 0
            if  (t,rd) in dp: 
                return dp[(t,rd)]
            dp[(t,rd)] = sum(ways(t-i, rd-1) for i in range(1,faces 1))
            return dp[(t,rd)]
        
        return ways(target, dices) % (10**9   7)

Only difference is dp.get(tuple) vs tuple in dp. AFAIK, both operations are O(1) in terms of time complexity. What is causing the difference here.

One reason i can think of is that in case of dp.get() call, if there is lot of hash conflicts, it might have to internally traverse the linked list to get the None. But i am not sure how in call will avoid that linked list traversal either.

Any way to debug?

[Edit]

To confirm, tuple is not causing any problem, I converted tuple to "-" separated string also. Still the same behaviour.

CodePudding user response：

I tested your program a bit and indeed it's a problem with zero values. Notice that all rows where target < n will be zeroed, which has an impact for bigger n. If you change your code that way:

    if dp.get((t, rd)) is not None:

It will work.

CodePudding user response：

Well the code is not semantically equivalent.

if get(dp, key):
   ...

is actually

if (dp[key] if key in dp else None):
   ...

and not just

if key in dp:
   ...

So it also tests whether the value in dp[key] is non-zero when key is present in dp. It seems that this additional code either adds to the running time, or, perhaps, it even changes the algorithm semantics (Not sure if dp[key] is guarantueed to be always non-zero.)

CodePudding user response：

A generally good technique of dynamic programming in Python is using lru_cache(maxsize=None) your first example gets accepted and in fact gets on the 73th percentile when I just removed your dictionary and used lru_cache(maxsize=None) like this:

class Solution:
    def numRollsToTarget(self, dices: int, faces: int, target: int) -> int:
        from functools import lru_cache
        @lru_cache(maxsize=None)
        def ways(t, rd):
            if t == 0  and rd == 0: return 1
            if t <= 0 or rd <= 0: return 0
            return sum(ways(t-i, rd-1) for i in range(1,faces 1))
        return ways(target, dices) % (10**9   7)

It is neater and quiet fast(implemented in C and by experts).
The maxsize=None is important since you don't want LRU to evict results, the maxsize=None disables LRU and just works as a dictionary, just as you like.

Another advice is to mod the sum term also, since the intermediate results can get arbitrarily big, and while you don't get overflow error in python, you do get a big decrease in performance when the numbers gets too big for 64-bit integers. Because the modulus operator is distributive on sum, it doesn't change the answer.