CODEWITHSUNDEEP
pythonstringdictionaryrecursionmemoization
Marcel
Marcel

Reputation: 381

Memoization and strings

I have two strings X1 and X2 and a lambda_ parameter and I want to compute a function by recursion on the size of the two strings with my following code :

def Bk_function(X1,X2,lambda_,k):
    #lambda=0.01
    #k=5
    if k==0:
        return 1
    if min(len(X1),len(X2))<k:
        return 0
    else:
        return (lambda_*Bk_function(X1[:-1],X2,lambda_,k) + lambda_*Bk_function(X1,X2[:-1],lambda_,k)
                + lambda_**2*(-Bk_function(X1[:-1],X2[:-1],lambda_,k) + (X1==X2)*Bk_function(X1[:-1],X2[:-1],lambda_,k-1)))

Nevertheless, as the computation time is too important, I plan to go through a memoization step with the following code :

def Bk_function(X1,X2,lambda_,k):
    if not (bool(memo.get(k))):
        if k==0:
            memo[k] = 1
        if min(len(X1),len(X2))<k:
            memo[k] = 0
        else:
            memo[k] = (lambda_*Bk_function(X1[:-1],X2,lambda_,k) + lambda_*Bk_function(X1,X2[:-1],lambda_,k)
                    + lambda_**2*(-Bk_function(X1[:-1],X2[:-1],lambda_,k) + (X1==X2)*Bk_function(X1[:-1],X2[:-1],lambda_,k-1)))
    return memo[k]

i.e. we keep in memory the values already calculated in an associative array/dictionary. But I do not know if I should define the memo dictionary as a global variable, or pass it as an argument to the function Bk_function(X1,X2,lambda_,k, memo={}) or write memo={} at the beginning of the program. Thanks !

Upvotes: 0

Views: 258

Answers (1)

Ritwik G
Ritwik G

Reputation: 416

You can define the function as you mentioned in the question.

def Bk_function(X1,X2,lambda_,k, memo={})

But you don't need to pass it as argument when you call the function as the same dictionary from function definition will be used. Just to demonstrate try running the below sample code.

def test(k, v, data={}):
    data[k] = v
    print(data)
    return v


test('first', 1)
test('second', 2)
test('third', 1)

Upvotes: 1

Related Questions