class LRU_Cache: def __init__(self, user_function, maxsize=1024): # Link layout: [PREV, NEXT, KEY, RESULT] self.root = root = [None, None, None, None] self.user_function = user_function self.cache = cache = {} last = root for i in range(maxsize): key = object() cache[key] = last[1] = last = [last, root, key, None] root[0] = last def __call__(self, *key): cache = self.cache root = self.root link = cache.get(key) if link is not None: link_prev, link_next, _, result = link link_prev[1] = link_next link_next[0] = link_prev last = root[0] last[1] = root[0] = link link[0] = last link[1] = root return result result = self.user_function(*key) root[2] = key root[3] = result oldroot = root root = self.root = root[1] root[2], oldkey = None, root[2] root[3], oldvalue = None, root[3] del cache[oldkey] cache[key] = oldroot return result if __name__ == '__main__': p = LRU_Cache(ord, maxsize=3) for c in 'abcdecaeaa': print(c, p(c))