CODEWITHSUNDEEP
pythonpython-2.7memoization
Daniel
Daniel

Reputation: 2459

Difference between Memoization Implementations - Python

What is the difference (if any exists) between these memoization implementations? Is there a use case where one is preferable to the other? (I included this Fibo recursion as an example)

Put another way: is there a difference between checking if some_value in self.memo: and if some_value not in self.memo:, and if so, is there a case where one presents a better implementation (better optimized for performance, etc.)?

class Fibo:
    def __init__(self):
        self.memo = {}

    """Implementation 1""" 
    def fib1(self, n):
        if n in [0,1]:
            return n

        if n in self.memo:
            return self.memo[n]

        result = self.fib1(n - 1) + self.fib1(n - 2)

        self.memo[n] = result

        return result

    """Implementation 2"""
    def fib2(self, n):
        if n in [0,1]:
            return n

        if n not in self.memo:
            result = self.fib2(n - 1) + self.fib2(n - 2)

            self.memo[n] = result

        return self.memo[n]

# Fibo().fib1(8) returns 21
# Fibo().fib2(8) returns 21

Upvotes: 1

Views: 65

Answers (1)

wim
wim

Reputation: 362587

There is no significant performance difference in these implementations. In my opinion fib2 is a more readable/pythonic implementation, and should be preferred.

One other recommendation I would make, is to initialise the memo in __init__ like this:

self.memo = {0:0, 1:1}

This avoids the need to make a conditional check inside each and every call, you can simply remove the first two lines of the fib method now.

Upvotes: 2

Related Questions