I wrote code to (naively) perform lru memoisation. I tried to write it in a functional programming style, and so did not make use of any global variables.

My Code

from collections import deque, defaultdict as dd

def naive_lru(mx=None):
        *   Closure that returns a memoiser.

        *   Params:
            *   `mx`: (`int`) The maximum size of the cache of the returned memoiser.
        *   Return:
            *   `memoise`: (`function`) A memoiser.
        *   Vars:
            *   `caches`: (`defaultdict`) stores the caches for the various functions.
            *   `lim`: (`bool`) set to `True` if `mx` isn't `None`. It is used to indicate that the size of the cache should be tracked.
            *   `ln`: (`int`) that tracks the cache size.
            *   `deck`: (`deque`) used for administrating the cache. Elements in the deque are ordered according to when they were last accessed.
            *   `lengths`: (`defaultdict`) stores the lengths of the caches for the various functions.
            *   `lims`: (`defaultdict`) stores whether a given cache has a maximum size.
            *   `decks`: (`defaultdict`) stores the deques of the caches for the various functions.
            *   `maxes`: (`defaultdict`) stores the maximum size of the caches for the various functions.
    caches, lim = dd(lambda: dd(lambda: None)), False
    if mx is not None:
        lim, ln = True, 0
        deck = deque()
    lengths, lims, decks, maxes = dd(lambda: 0), dd(lambda: False), dd(lambda: deque()), dd(lambda: None)
    def memoise(mxsize=None, lst=False, idx=None, init=0):
            *   Returns a memoisation decorator for a given function.

            *   Params:
                *   `mxsize` (`int`): The maximum size of the cache for the memoised variant of the input function.
                *   `lst` (`list`): A boolean variable that determines whether a list would be used for the function cache. For functions with domains that can be mapped onto a dense set, using a list for caching would be more efficient (and faster) than using a dict.
                    *   The cache would only be set to a list if `mxsize` is `None` as implementing lru functionality with a list is quite nontrivial — and more importantly very messy — frequent deletions would destroy the dense property that was a prerequisite for using the list as a cache, so lru functionality is only provided when the cache is a dict.
                *   `idx` (`function`): The transformation function that maps input data unto their corresponding index in the cache.
                *   `init` (`int`): The initial size of the cache list. If an upper bound on the size of the function's domain is known, a list of that size can be created at initialisation. This is more efficient than repeatedly appending to or extending the list. 
            *   Return:
                *   `memoised`: (`function`) A memoisation decorator.
        def memoised(f):
                *   Memoisation function that returns a memoised variant of a given input function.

                *   Params:
                    *   `f`: (`function`) The function to be memoised.
                *   Return:
                    *   `mem_f`: (`function`) Memoised variant of the input function.
            nonlocal lst
            if lim:
                ln += 1
                if ln > mx:
                    del caches[deck.pop()]  #Remove the least recently used function cache.
            if mxsize is not None:
                lims[f], lst, maxes[f] = True, False, mxsize
                if lst:
                    caches[f] = [None]*init
            def mem_f(*args, **kwargs):
                tpl = (args, frozenset(kwargs))
                index = tpl if idx is None else idx(tpl)
                if caches[f][index] is None:
                    caches[f][index] = f(*args, **kwargs)
                    if lims[f]:
                        lengths[f] += 1
                        if lengths[f] > maxes[f]:
                            del caches[f][decks[f].pop()]  #Remove the least recently used argument cache.
                return caches[f][index]
            return mem_f
        return memoised
    return memoise

Sample Usage

mem = naive_lru()

@mem(lst=True, init=10000, idx=lambda x: x[0][0])
def fib(n):
    if n in [0, 1]:
        return n
    return  fib(n - 2) + fib(n - 1)

print(fib(500))    #Outputs "139423224561697880139724382870407283950070256587697307264108962948325571622863290691557658876222521294125".

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.