CODEWITHSUNDEEP
pythoncachingmemoization
Jeremy
Jeremy

Reputation: 2044

Memoization Usage/Cache Storing

I am writing a program that calculates the Pascal Identity of two variables, hard coded into the program, as I am new into Python and trying out caching and memoization. Here is what I have so far: 

counter = 0

call_cacheK = {}
   def callTest(n, k):
   global counter

   if n in call_cacheK:
       return call_cacheK[n]  
   if k == 0:
       return 1
   elif k == n:
       return 1 
   elif (1 <= k) and (k <= (n-1)):
       counter += 1
       #call_cacheK[n] = result
       result = ((callTest(n-1, k) + callTest(n-1, k-1)))
   print(result)
   return result

callTest(20, 11)
#167,960

My function will output the final real answer with what it has now, but with a lot of outputted answers. I cannot seem to get how to properly store the values to be used in the cache.

How do I properly use call_cacheK to store the result values I have already used?

Thank you.

Upvotes: 1

Views: 240

Answers (1)

Alex Belyaev
Alex Belyaev

Reputation: 1445

Lets see. First, you have a function of two variables, but store result in cache only by one parameter. So callTest(20, 11), callTest(20, 10), callTest(20, 9) will have one result in your cache. Lets rewrite your function a little:

call_cacheK = {}

def callTest(n, k):
    if (n, k) in call_cacheK:
        return call_cacheK[(n, k)]  
    if k == 0:
        return 1
    elif k == n:
        return 1 
    elif (1 <= k) and (k <= (n-1)):
        result = ((callTest(n-1, k) + callTest(n-1, k-1)))
        call_cacheK[(n, k)] = result
    print(result)
    return result

Yes there is no counter variable because I didn't realize why do you need it :)

Also, as far as I can judge by the use of print(result), you probably use the Python3.x. If so, you can use standard cache implementing:

from functools import lru_cache

@lru_cache(maxsize=None)
def callTest2(n, k):  
    if k == 0:
        return 1
    elif k == n:
        return 1 
    elif (1 <= k) and (k <= (n-1)):
        result = ((callTest2(n-1, k) + callTest2(n-1, k-1)))
    print(result)
    return result

Good luck! :)

Upvotes: 1

Related Questions