记忆 Usage/Cache 存储

Question

我正在编写一个程序来计算两个变量的 Pascal 恒等式，硬编码到程序中，因为我是 Python 的新手，正在尝试缓存和记忆。这是我目前所拥有的：

counter = 0

call_cacheK = {}
   def callTest(n, k):
   global counter

   if n in call_cacheK:
       return call_cacheK[n]  
   if k == 0:
       return 1
   elif k == n:
       return 1 
   elif (1 <= k) and (k <= (n-1)):
       counter += 1
       #call_cacheK[n] = result
       result = ((callTest(n-1, k) + callTest(n-1, k-1)))
   print(result)
   return result

callTest(20, 11)
#167,960

我的函数将输出最终的真实答案，但输出的答案很多。我似乎不知道如何正确存储要在缓存中使用的值。

如何正确使用 call_cacheK 来存储我已经使用过的 result 值？

谢谢。

Answer 1

让我们看看。首先，您有一个包含两个变量的函数，但仅通过一个参数将结果存储在缓存中。因此 callTest(20, 11)、callTest(20, 10)、callTest(20, 9) 将在您的缓存中有一个结果。让我们稍微重写一下您的函数：

call_cacheK = {}

def callTest(n, k):
    if (n, k) in call_cacheK:
        return call_cacheK[(n, k)]  
    if k == 0:
        return 1
    elif k == n:
        return 1 
    elif (1 <= k) and (k <= (n-1)):
        result = ((callTest(n-1, k) + callTest(n-1, k-1)))
        call_cacheK[(n, k)] = result
    print(result)
    return result

是的，没有计数器变量，因为我不知道你为什么需要它:)

另外，根据我使用print(result)的判断，你可能使用Python3.x。如果是这样，您可以使用 standard cache implementing:

from functools import lru_cache

@lru_cache(maxsize=None)
def callTest2(n, k):  
    if k == 0:
        return 1
    elif k == n:
        return 1 
    elif (1 <= k) and (k <= (n-1)):
        result = ((callTest2(n-1, k) + callTest2(n-1, k-1)))
    print(result)
    return result

祝你好运！ :)

记忆 Usage/Cache 存储

Memoization Usage/Cache Storing

python

caching

memoization