python dictionary.get vs in dictionary

user_4510252 0
Viewed 53

Considering leetcode 1155

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.

time-complexity algorithm python
3 Answers

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.)

user_17398840

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.

user_33614620

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.

user_20996080
Related