如何让 Python 记住在函数内部创建的列表以备将来使用

Question

下面是Fibonacci Sequence的迭代计算。

def fibonacci(n):
    if n < 0:
            raise ValueError("invalid index!")
    if n==0:
            return 0
    if n==1:
            return 1

    f = [0,1]
    for i in range(2,n+1):
            f.append(f[i-1] + f[i-2])
    return f[n]

Code Source: brilliant.org

实际上，列表 f 是函数内部的局部变量，每次调用 fibonacci 函数时都会重新创建和重新填充。如何重写此代码片段，以便 Python 在调用后不需要重新计算 fibonacci(5) 并且可以在下次调用 fibonacci(5) 或更高版本时使用它？我知道全局变量是一种选择，但最 "Pythonic" 的方法是什么？

Answer 1

您可以使用闭包来记忆结果：在这种情况下，备忘录字典是在函数首次执行时创建的（通常是在加载模块时）；它是持久的，并在调用函数时填充。

def fibonacci(n, memo={}):
    try: 
        return memo[n]
    except KeyError:
        pass
    if n < 0:
            raise ValueError("fibonacci must be called with positive numbers")
    if n == 0:
        memo[n] = 0 
        return 0
    if n == 1:
        memo[n] = 1
        return 1
    memo[n] = fibonacci(n-1) + fibonacci(n-2)
    return memo[n]

Answer 2

您可以将 f 存储在 函数范围 之外的变量中。例如：

def memoize_fibonacci():
    f = [0,1]
    def inner_fibonacci(n):
        if n < 0:
                raise ValueError("invalid index!")
        for i in range(len(f),n+1):
                f.append(f[i-1] + f[i-2])
        return f[n]
    return inner_fibonacci

所以每次我们检查f的长度。如果我们还没有生成请求的索引，我们会生成直到我们获得索引。不管我们是否扩展列表，我们最终都可以 return f[n].

现在我们可以提取 fibonacci 函数，其中：

fibonacci = memoize_fibonacci()

如果我们现在为第 200'000 个元素查询两次，第二次会更快。

Answer 3

使用 python 字典并检查密钥是否存在以及 return 来自字典的结果，或者在 returning 之前计算并将结果添加到字典中。

fib_dict = {};

def fibonacci(n):
    if n in fib_dict:
        return fib_dict[n];
    else:
        if n < 0:
            raise ValueError("invalid index!")
        if n==0:
            return 0
        if n==1:
            return 1

        f = [0,1]
        for i in range(2,n+1):
            f.append(f[i-1] + f[i-2])

        fib_dict[n] = f[n];
        return f[n];

如何让 Python 记住在函数内部创建的列表以备将来使用

How to Make Python remember a list created inside a function for future use

python

scope

memoization

fibonacci