up vote 1 down vote favorite
1

Here is my simple code for LRU cache in Python 2.7. Appreciate if anyone could review for logic correctness and also potential performance improvements.

A confusion want to ask for advice is, I am using a list to track access time, the first element of the list the is least time accessed, and the last element is the most recent accessed element. And I am using remove method of list, for example, statement accessQueue.remove(key), wondering what is the time complexity of list.remove, is it linear or log(N)?

from collections import defaultdict
kvStore = defaultdict(str)
accessQueue = []
maxSize = 10

def cacheSet(key, value):
        kvStore[key] = value
        if key in accessQueue:
            accessQueue.remove(key)
            accessQueue.append(key)
        else:
            accessQueue.append(key)
        if len(accessQueue) > maxSize:
            accessQueue.pop(0)
def cacheGet(key):
    if key in kvStore:
        accessQueue.remove(key)
        accessQueue.append(key)
        return kvStore[key]
    else:
        return None
def cachePrint():
    for k,v in kvStore.items():
        print k,v

if __name__ == "__main__":
    for i in range(10):
        cacheSet(i, "value " + str(i))
    for i in range(10):
        print cacheGet(i)

    cacheSet(11, "value " + str(11))
    cachePrint()
share|improve this question
up vote 3 down vote accepted

This should be a class - this is what OOP exists to do, abstract away details like this and contain them all in an object. You'll want to subclass collections.MutableMapping. You can also use an ordered dict to combine the lru behavior with the normal dict behavior. Below is my class implementation. I've left out a lot of the details, but most of the methods you can just delegate to the internal ordered dict self.store. You'll probably want to make sure you implement all of the dict methods, which you can find here.

from collections import MutableMapping, OrderedDict

class LruCache(MutableMapping):

    def __init__(self, max_size=10, *args, **kwargs):
        self.max_size = max_size
        self.store = OrderedDict()
        self.update(dict(*args, **kwargs))

    def __getitem__(self, key):
        # Move the key to the end of the cache
        try:
            self.store[key] = self.store.pop(key)
            return self.store[key]
        except KeyError:
            if not hasattr(self, '__missing__'):
                raise
            else:
                return self.__missing__(key)

    def get(self, key, default=None):
        try:
            return self[key]
        except KeyError:
            return default

    def __setitem__(self, key, value):
        try:
            self.store.pop(key)
        except KeyError:
            # We just want to move it to the back, so ignore it
            pass

        self.store[key] = value

        while len(self) > self.max_size:
            self.store.popitem(last=False)

    def __delitem__(self, key):
        del self.store[key]

    def __iter__(self):
        return iter(self.store)

    def __len__(self):
        return len(self.store)
share|improve this answer
    
Thanks Dannnno, vote up. Your code is much better. Wondering what is the time complexity for adding element (your code of self.store[key] = value) and remove element (your code of self.store.popitem(last=False))? – Lin Ma Jul 23 '16 at 6:22
    
BTW, also for my original implementation, what is the time complexity of list.remove by a given value, it is O(n) or O(logN)? Thanks. – Lin Ma Jul 23 '16 at 6:23
    
Hi Dannnno, if you could comment on my above questions, it will be great. :) – Lin Ma Jul 27 '16 at 23:21
1  
@LinMa No clue. Those are things you could find out by reading the documentation or looking at the source code. I would assume that most of those are not guaranteed by the language, and could vary across Python implementation – Dannnno Jul 27 '16 at 23:26
    
Thanks Dannnno, mark your reply as answer. – Lin Ma Jul 27 '16 at 23:29

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.