Longest Increasing Subsequence using recursion and cache

user_12097928 0
Viewed 54

i've been trying to implement a cache in my recursive LIS function so it doesn't calculate the same value twice. I would really aprecciate if someone can give me a hint of what im getting wrong.

This is the recursive function that returns the LIS array that works fine:

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])

This is the same function but implementing a cache, it gives wrong answers with repetition(in the case of the previous assert it 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

I think maybe the error is caching [l[i]] + lgsMemo(l[i],l,i+1) instead of lgsMemo(l[i],l,i+1).

lis caching python
2 Answers

Why make it so hard on yourself? You can just have two functions. One you call if you need to actually calculate things and one where you check if you have it in memory and delegate to the other if necessary. Notice that I had to slightly edit your recursive function so it uses the cache if possible.

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])
user_26400450

Well I didn't refresh this page and didn't see @user2640045's answer, which is basically the same as mine. I just cache the final result from lgsMemo when required.

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])
user_46291250
Related