CODEWITHSUNDEEP
pythonrecursion
Shri
Shri

Reputation: 19

How to create a dictionary to cache values in python?

I am trying to improve the recursive function for Collatz sequence in Python as my teacher mentioned to make it more efficient. I am storing calculations in a dictionary which repeats in other sequences, for example: if you calculate the collatz of 4 we realize it's 4,2,1

If we then calculate the collatz of 7 it's a bunch of numbers but the important part is that it eventually has a "4" in the sequence. which means we are going to be calculating the collatz(4) twice, once for the "4" value and again for the "7" value. if we could for example reuse the 4 value we could prevent this computation from happening twice. For some reason, my code is only printing 2,1,1 and throws an error after that. Can someone please help with this (sorry for the bad indentation, stack overflow didn't let me indent it properly)? I tried the lru cache method, it works but my teacher expects to create the dictionary by ourselves instead of using lru cache

def collatz_up_to_n(n):
   for i in range(n):
   better_collatz_up_to_n(i+1)
   print("\n")
def better_collatz_up_to_n(n):
    print(n, " ", end="")
    a_list = [n]
    if n == 1:
        return [1]
    elif n % 2 == 0:
        a_list.extend(better_collatz_up_to_n(n // 2))
    if n in a_list == collatz_up_to_n(n):
        values = {n}
    else:
        a_list.extend(better_collatz_up_to_n(n * 3 + 1))
    if n in a_list == collatz_up_to_n(n):
        valuesOdd = {n}
    return a_list,values,valuesOdd
    print (n)
print("The Collatz sequence up to 10 is: ")
collatz_up_to_n(10)

Upvotes: 0

Views: 2176

Answers (1)

Stef
Stef

Reputation: 15525

If you want to save the dict between uses of your function, you can't define it as a local variable. Otherwise, it disappears when the function ends, and is created all-new at the next call, without saving previously encountered values.

Here are three ways to do this, using an object attribute, a default argument, or a decorator from module functools. I used the Fibonacci function rather than the Collatz sequence, so as not to spoil the problem completely for you. I tested the cached Fibonacci functions by trying to compute fib(40). A bad implementation of Fibonacci without caching would take an awfully long time to compute fib(40); the three functions below return the result immediately.

# FIRST WAY: using an object attribute
def fib1(n):
    if n in fib1.cache:
        return fib1.cache[n]
    else:
        fib1.cache[n] = fib1(n-2) + fib1(n-1)
        return fib1.cache[n]

fib1.cache = {0: 0, 1: 1}

print(fib1(11))
# 89
print(fib1(40))
# 102334155

# SECOND WAY: using a default argument
def fib2(n, cache={0: 0, 1: 1}):
    if n in cache:
        return cache[n]
    else:
        cache[n] = fib2(n-2) + fib2(n-1)
        return cache[n]

print(fib2(11))
# 89
print(fib2(40))
# 102334155

However, there is a third way. Since caching values is not particularly original and is often useful, you can use functools.cache to automatically cache the outputs of a function:

import functools

@functools.cache
def fib3(n):
    if n == 0 or n == 1:
        return n
    else:
        return fib3(n-2) + fib3(n-1)

print(fib3(11))
# 89
print(fib3(40))
# 102334155

For contrast, here is the bad way that doesn't properly save the cache from one call to the next:

# BAD WAY: Don't do this. The cache is local to each call, and erased as soon as the function returns.
def fib0(n):
    cache = {0: 0, 1: 1}
    if n in cache:
        return cache[n]
    else:
        cache[n] = fib0(n-2) + fib0(n-1)
        return cache[n]

print(fib0(11))
# 89
print(fib0(40))
# TAKES AWFULLY LONG TIME

Upvotes: 1

Related Questions