0

So I am trying to do memoization in a python fibonacci(n) function.

def fib(n, memo = [None] * (fibn+1)):
    if memo[n] != None: return memo[n]
    if n <= 2: return 1
    memo[n] = fib(n-1) + fib(n-2)
    return memo[n]

I am trying to find a way to store the solutions of values, which I already computed. My temporary solution to that is to make a list memo = [None] * (fibn+1) and if a new value is computed: memo[n] = fib(n). The problem I have with this is that the list is mostly empty and is overall very inefficient. I want to go from this

memo = [None, 1, None, 2, None, None, etc...]

to something like this

memo = {
3: 2 
4: 3
7: 13
}

which is just like an object in Java.

BrokenBenchmark
  • 18,126
  • 7
  • 21
  • 33
Snopix
  • 29
  • 1
  • 4
  • 1
    It's a `dict`, and yes, that's typically what you would use to memoize a function. – chepner Jun 25 '22 at 18:20
  • You are currently just using a `list` to simulate (inefficiently, as you noticed) a `dict` with non-negative integer keys. – chepner Jun 25 '22 at 18:20
  • 1
    This sounds like you're thinking of *Javascript* objects. Java and Javascript are almost completely unrelated. – user2357112 Jun 25 '22 at 18:21
  • 3
    Also, the list is going to look like `[None, None, None, 2, 3, 5, 8, 13, 21, ...]`, not `[None, 1, None, 2, None, None, ...]`. – user2357112 Jun 25 '22 at 18:26
  • 1
    FWIW, a `list` would actually be the most efficient standard data structure for the memoization cache. The cache entries would *not* be sparse, unlike what the question implies. Starting at index 0 for `fib(0)`, the entries are `0, 1, 1, 2, 3, 5, 8, 13, ...` – MisterMiyagi Jun 25 '22 at 18:36
  • @MisterMiyagi No, the first three really are `None`. – Kelly Bundy Jun 25 '22 at 18:38
  • @KellyBundy With an inefficient implementation, yes. Pre-filling the cache for the first entries instead avoids the (incorrect!) special case for n<=2. – MisterMiyagi Jun 25 '22 at 18:40
  • 1
    @MisterMiyagi Ah, you mean a different implementation. Yes, I actually [did that](https://tio.run/##RY3BCsIwEETv@Yo9ZrGVpF5EaH@k9FDpRgN2E5Z48OtjEgvObWYeM/GTnoEv1yg5b@TA@bvmDnbaA4wwmw7sgjcFRd4BwzTCi1jX/oirqj2vMRJvui30FuH0G@sHxAYKpbdwY2delIriOTXcGlMYF6QceAZZ@UF6MMfBn2PEnL8). – Kelly Bundy Jun 25 '22 at 18:41

2 Answers2

8

Python provides decorators that can cache the results for you automatically in the functools module:

from functools import lru_cache

@lru_cache
def fib(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    return fib(n - 1) + fib(n - 2)
BrokenBenchmark
  • 18,126
  • 7
  • 21
  • 33
-1

A Python Dictionary can be used to store key-value pairs in this way (as chepner said in his comment on the question).

The functools module is also an option, but if you want to directly access the cache yourself you have to use a Dictionary.

luke
  • 465
  • 1
  • 14