python - 实现记忆化

Question

查看 RosettaCode 和 Literate Programming 中的代码示例后，我仍然对如何为我正在做的问题实现记忆化感到困惑。

在该问题中，我执行了 magic() 公式，类似于数字上的 Collat​​z 序列，最终该序列产生 1,2 或 3。

例如，它可能会这样:

123849 -> 2342453 -> 1233453 ->3

我想在计算后存储这些值，以便当我对越来越大的数字执行 magic() 时，运行时间会减少。例如，在执行 magic(123849) 之后，我想存储 123849、2342453 和 1233453。如果将来出现任何这些数字，则不必执行 magic 函数，它会立即输出 3。

ones=[]
twos=[] 
threes=[]
def magic(x):
    # Memoization
    if ones.count(x)>0: return 1
    if twos.count(x)>0: return 2
    if threes.count(x)>0: return 3 
    sequence=[]
    <generate magic sequence, add each value to sequence>
    # Add each sequence to the appropriate list
    if final_value==1: ones.extend(sequence)
    if final_value==2: twos.extend(sequence)
    if final_value==3: threes.extend(sequence)
    return final_value

我的问题:是否有更好(更有效/更快)的方法来实现这种内存？我可以使用列表而不是字典吗？

• 我读过这篇文章:What is memoization and how can I use it in Python?并了解您通常应该使用字典。我只是想知道使用列表和字典进行内存是否有很大区别。

Answer 1

一定要检查一下 functools.lru_cache，Python stdlib 的内存实现:http://docs.python.org/dev/library/functools.html#functools.lru_cach