CODEWITHSUNDEEP
pythonnumpyrecursionmemoization
johntfoster
johntfoster

Reputation: 361

Memoize a single argument in Python method

I've written a Numpy implementation that uses the Cox-de Boor recursive algorithm to compute B-spline basis functions. I would like to memoize the object instance for a given order, but leave the function callable with respect to xi.

In other words, after the object is instantiated, the recursive function should be "set", but remain callable at xi. I really need this for speed, as I will be calling the function many times and do not want to reconstruct the recursive function over-and-over.

Here is the current implementation:

import numpy as np

#Turn off divide by zero warning because we explicitly check for it
np.seterr(divide='ignore')

class Bspline():

    def __init__(self, knot_vector, order):

        self.knot_vector = knot_vector
        self.p = order


    def __basis0(self, xi):

        return np.where(np.all([self.knot_vector[:-1] <=  xi, 
                            xi < self.knot_vector[1:]],axis=0), 1.0, 0.0)

    def __basis(self, xi, p):

        if p == 0:
            return self.__basis0(xi)
        else:
            basis_p_minus_1 = self.__basis(xi, p - 1)

            first_term_numerator = xi - self.knot_vector[:-p] 
            first_term_denominator = self.knot_vector[p:] - self.knot_vector[:-p]

            second_term_numerator = self.knot_vector[(p + 1):] - xi
            second_term_denominator = self.knot_vector[(p + 1):] - self.knot_vector[1:-p]

            first_term = np.where(first_term_denominator > 1.0e-12, 
                              first_term_numerator / first_term_denominator, 0)
            second_term = np.where(second_term_denominator > 1.0e-12,
                               second_term_numerator / second_term_denominator, 0)

            return  first_term[:-1] * basis_p_minus_1[:-1] + second_term * basis_p_minus_1[1:]


    def __call__(self, xi):

        return self.__basis(xi, self.p)

and is used as

knot_vector = np.array([0,0,0,0,0,1,2,2,3,3,3,4,4,4,4,5,5,5,5,5])
basis = Bspline(knot_vector,4)
basis(1.2)

which returns the basis functions evaluated at 1.2. However, I need to call this function many times and as it is written now, the recursive function is reconstructed for every call, and this is not necessary as the recursion level is set at instantiation as 4

Upvotes: 2

Views: 325

Answers (2)

Ami Tavory
Ami Tavory

Reputation: 76307

It's very easy to memoize anything using functools.lru_cache in Python3, or, in Python2.7 using something like this:

class Bspline(object):
    ...

    # Python2.7
    @memoize
    # or, Python3*
    @functools.lru_cache()
    def op(self, args):
        return self._internal_op(xi)

Upvotes: 3

kylieCatt
kylieCatt

Reputation: 11039

Create a dictionary that saves the results of the function and then check to see if that value is in the dict before calling the function again. Something similar to this should work depending on your setup.

results = {}
for value in values:
    if results.get(value):
        answer = results[value]
    else:
        answer = basis(value)
        results[value] = answer
        print(answer)  # or just display the results dict once you are done

Upvotes: 0

Related Questions