पायथन:एलआरयू कैश का निर्माण

LRU कैश Python3.3 में O(1) प्रविष्टि, विलोपन और खोज है।

डिज़ाइन व्यक्तिगत लिंक का पता लगाने के लिए प्रविष्टियों की एक गोलाकार डबल-लिंक्ड सूची (सबसे पुराने से नवीनतम की व्यवस्था) और एक हैश तालिका का उपयोग करता है। कैश हिट प्रासंगिक लिंक खोजने और सूची के शीर्ष पर ले जाने के लिए हैश तालिका का उपयोग करते हैं। कैश सबसे पुराने लिंक को हटाना भूल जाता है और लिंक की गई सूची के शीर्ष पर एक नया लिंक बनाता है।

यहां बहुत ही बुनियादी पायथन (केवल सरल शब्दकोश और सूची संचालन का उपयोग करके) की 33 पंक्तियों में एक सरलीकृत (लेकिन तेज़) संस्करण है। यह Python2.0 और बाद के संस्करण (या PyPy या Jython या Python3.x) पर चलता है:

class LRU_Cache:

    def __init__(self, original_function, maxsize=1024):
        # Link structure: [PREV, NEXT, KEY, VALUE]
        self.root = [None, None, None, None]
        self.root[0] = self.root[1] = self.root
        self.original_function = original_function
        self.maxsize = maxsize
        self.mapping = {}

    def __call__(self, *key):
        mapping = self.mapping
        root = self.root
        link = mapping.get(key)
        if link is not None:
            link_prev, link_next, link_key, value = 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 value
        value = self.original_function(*key)
        if len(mapping) >= self.maxsize:
            oldest = root[1]
            next_oldest = oldest[1]
            root[1] = next_oldest
            next_oldest[0] = root
            del mapping[oldest[2]]
        last = root[0]
        last[1] = root[0] = mapping[key] = [last, root, key, value]
        return value


if __name__ == '__main__':
    p = LRU_Cache(ord, maxsize=3)
    for c in 'abcdecaeaa':
        print(c, p(c))

पायथन 3.1 में शुरू, OrderedDict LRU कैश को लागू करना और भी आसान बनाता है:

from collections import OrderedDict

class LRU_Cache:

    def __init__(self, original_function, maxsize=1024):
        self.original_function = original_function
        self.maxsize = maxsize
        self.mapping = OrderedDict()

    def __call__(self, *key):
        mapping = self.mapping
        try:
            value = mapping[key]
            mapping.move_to_end(key)
        except KeyError:
            value = self.original_function(*key)
            if len(mapping) >= self.maxsize:
                mapping.popitem(False)
            mapping[key] = value
        return value