lru cache

lru_cache.py

# lru cache implementation
# as params (can) require number of elements to keep in cache
# as requirement input data for effective caching should be hashable and comparable ie. able to be used as dict key

# 1. build in cache
from functools import lru_cache

# 2. OrderedDict
from collections import OrderedDict
from functools import wraps


def lru_cache_ordered_dict(maxsize=128):
    cache = OrderedDict()

    def decorator(func):
        @wraps(func)
        def wrapper(*args, **kwargs):
            key = (tuple(args), tuple(sorted(kwargs.items())))
            if key in cache:
                cache.move_to_end(key)
            else:
                if len(cache) >= maxsize > 0:
                    cache.popitem(last=False)
                cache[key] = func(*args, **kwargs)
            return cache[key]

        return wrapper

    return decorator


# 3. hash and linked list implementation
from dataclasses import dataclass
from typing import Any, Optional


@dataclass(slots=True)
class Node:
    key: Any
    value: Any
    prev: Optional[Node] = None
    next: Optional[Node] = None

    def add_after(self, fifo_tail: Optional[Node]) -> Node:
        if fifo_tail is not None:
            fifo_tail.next = self
            self.prev = fifo_tail
        return self

    def remove(self) -> Node:
        if self.prev is not None:
            self.prev.next = self.next
        if self.next is not None:
            self.next.prev = self.prev
        self.next = self.prev = None
        return self


def lru_cache_dict_and_double_linked_list(maxsize=128):
    cache = {}
    fifo_head = fifo_tail = None

    def decorator(func):
        @wraps(func)
        def wrapper(*args, **kwargs):
            nonlocal fifo_head
            nonlocal fifo_tail

            key = (tuple(args), tuple(sorted(kwargs.items())))
            if key in cache:
                if cache[key] is fifo_head:
                    fifo_head = fifo_head.next
                if fifo_tail is not cache[key]:
                    fifo_tail = cache[key].remove().add_after(fifo_tail)
            else:
                if len(cache) >= maxsize > 0:
                    if fifo_head is not None:
                        del cache[fifo_head.key]
                    if fifo_head is fifo_tail:
                        fifo_head = fifo_tail = None
                    else:
                        next_fifo_head = fifo_head.next if fifo_head is not None else None
                        fifo_head.remove()
                        fifo_head = next_fifo_head
                fifo_tail = cache[key] = Node(key=key, value=func(*args, **kwargs)).add_after(fifo_tail)
                if fifo_head is None:
                    fifo_head = fifo_tail
            return cache[key].value

        return wrapper

    return decorator