def __init__(self, capacity):
self.dic = collections.OrderedDict()
self.remain = capacity
def get(self, key):
if key not in self.dic:
return 1
v = self.dic.pop(key)
self.dic[key] = v # set key as the newest one
return v
def set(self, key, value):
if key in self.dic:
self.dic.pop(key)
else:
if self.remain > 0:
self.remain = 1
else: # self.dic is full
self.dic.popitem(last=False)
self.dic[key] = value
Python concise solution with comments (Using OrderedDict).


Another solution by using dictionary and deque in Python:
def __init__(self, capacity): self.deque = collections.deque([]) self.dic = {} self.capacity = capacity def get(self, key): if key not in self.dic: return 1 self.deque.remove(key) self.deque.append(key) return self.dic[key] def set(self, key, value): if key in self.dic: self.deque.remove(key) elif len(self.dic) == self.capacity: v = self.deque.popleft() # remove the Least Recently Used element self.dic.pop(v) self.deque.append(key) self.dic[key] = value

@caikehe Hey I don't think this is the better than OrderedDict you posted, since removing from Queue will be O(n) while removing from OrderedDict will be O(1) complexity. What do you think?

@caikehe Can anyone clarify the implementation/performance of deque?
As far from what I know the implementation of deque in python is indeed doublylinked list. But the accessing time to the middle is roughlyO(n)
.

Just using a list instead of deque or orderedDict will also do the work:
class LRUCache(object): def __init__(self, capacity): """ :type capacity: int """ self.cap = capacity self.order = [] self.cache = {} def get(self, key): """ :rtype: int """ if key in self.cache: self.order.remove(key) self.order.append(key) return self.cache[key] else: return 1 def set(self, key, value): """ :type key: int :type value: int :rtype: nothing """ if key in self.cache: self.order.remove(key) elif len(self.order) == self.cap: self.cache.pop(self.order[0]) self.order.pop(0) self.order.append(key) self.cache[key] = value


@abyellow7511 said in Python concise solution with comments (Using OrderedDict).:
Just using a list instead of deque or orderedDict will also do the work:
Depends on how you define "do the work". If we use OrderedDict, both operations would be O(1) on average. And when we use deque instead, at least for
set
operation, whencapacity
is full and thekey
we want to push is not incache
, we get O(1) on average. And in your case, both operations take O(n).
