python - 记忆化实现之间的差异 - Python

Question

这些内存实现之间有什么区别(如果存在)？是否存在一种用例比另一种更可取的情况？ (我以这个 Fibo 递归为例)

换句话来说:检查 if some_value in self.memo: 和 if some_value not in self.memo: 之间是否有区别，如果有，是否存在区别一种提出更好实现的情况(更好地优化性能等)？

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

Answer 1

这些实现没有显着的性能差异。在我看来，fib2 是一个更具可读性/Pythonic 的实现，应该是首选。

我提出的另一项建议是在 __init__ 中初始化备忘录，如下所示:

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

这避免了在每次调用中进行条件检查的需要，您现在可以简单地删除 fib 方法的前两行。