使用递归和缓存的最长递增子序列

Question

我一直在尝试在我的递归 LIS 函数中实现缓存，因此它不会两次计算相同的值。如果有人能告诉我我哪里出错了，我真的很感激。

这是returns 工作正常的LIS数组的递归函数：

import numpy as np

def lgs(l):
    return lgsRecursive(np.NINF,l,0)
    
def lgsRecursive(x,l,i):
    print(x,i)
    
    if i >= len(l):
        return[]
        
    else:
        list1 = lgsRecursive(x,l,i+1)
        if l[i] > x:
            list2 = [l[i]] + lgsRecursive(l[i],l,i+1)
            if len(list1) < len(list2):
                list1 = list2
                
    return list1

assert(lgs([1, 20, 3, 7, 40, 5, 2]) == [1,3,7,40])

这是相同的功能，但实现了缓存，它会重复给出错误的答案（在前面的断言中 returns [1, 20, 40, 40, 40, 40, 40] ):

import numpy as np
cache = {}

def lgs(l):
    return lgsMemo(np.NINF,l,0)

def lgsMemo(x,l,i):
    global cache
    
    key = (x,i)
    
    if key in cache:
        return cache[(x,i)]
    
    if i >= len(l):
        return []
    
    else:
        list1 = lgsMemo(x,l,i+1)
        if l[i] > x:
            list2 = [l[i]] + lgsMemo(l[i],l,i+1)
            if len(list1) < len(list2):
                list1 = list2
                cache[(l[i],i+1)] = list1
            else:
                cache[(x,i+1)] = list1                  
    return list1

我认为错误可能是缓存 [l[i]] + lgsMemo(l[i],l,i+1) 而不是 lgsMemo(l[i],l,i+1).

Answer 1

为什么要这样折磨自己？你可以只有两个功能。如果您需要实际计算事物，您会调用一个，而您会在其中检查您是否将其存储在内存中，并在必要时委托给另一个。请注意，我必须稍微编辑您的递归函数，以便尽可能使用缓存。

import numpy as np
cache = {}

def lgs(l):
    return lgsMemo(np.NINF,l,0)
    
def lgsRecursive(x,l,i):
    print(x,i)
    
    if i >= len(l):
        return[]
        
    else:
        list1 = lgsMemo(x,l,i+1)
        if l[i] > x:
            list2 = [l[i]] + lgsMemo(l[i],l,i+1)
            if len(list1) < len(list2):
                list1 = list2
                
    return list1


def lgsMemo(x,l,i):
    global cache
    if (x,i) not in cache:
        cache[(x,i)] = lgsRecursive(x,l,i)
    return cache[(x,i)]


assert(lgs([1, 20, 3, 7, 40, 5, 2]) == [1,3,7,40])

Answer 2

嗯，我没有刷新这个页面，也没有看到@user2640045的回答，和我的基本一样。我只是在需要时缓存 lgsMemo 的最终结果。

import numpy as np
cache = {}

def lgs(l):
    return lgsMemo(np.NINF,l,0)

def lgsMemo(x,l,i):
    global cache
    if i >= len(l):
        return []

    key = (x,i)
    if key in cache:
        return cache[key]
    else:
        list1 = lgsMemo(x,l,i+1)
        if l[i] > x:
            list2 = [l[i]] + lgsMemo(l[i],l,i+1)
            if len(list1) < len(list2):
                list1 = list2

    cache[key] = list1
    return list1

assert(lgs([1, 20, 3, 7, 40, 5, 2]) == [1,3,7,40])

使用递归和缓存的最长递增子序列

Longest Increasing Subsequence using recursion and cache

python

caching

lis