记忆化实现之间的差异 - 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 是一个更 readable/pythonic 的实现，应该是首选。

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

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

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

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

Difference between Memoization Implementations - Python

python

python-2.7

memoization