Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- from collections import deque
- class LFUCache(object):
- def __init__(self, capacity):
- self.value = {}
- self.resque = {}
- self.capacity = capacity
- self.evictionQueue = deque()
- def get(self, key):
- ret = -1
- if key in self.value:
- ret = self.value[key]
- self.resque[key] = self.resque.get(key, 0)+1
- return ret
- def set(self, key, value):
- if self.capacity == 0:
- return
- # Eviction is needed
- if key not in self.value and self.capacity == len(self.value):
- eviction = False
- while not eviction:
- key2evict = self.evictionQueue.popleft()
- if self.resque.get(key2evict, 0) > 0:
- self.resque[key2evict] -= 1
- self.evictionQueue.append(key2evict)
- else:
- eviction = True
- if key2evict in self.value:
- self.value.pop(key2evict)
- if key2evict in self.resque:
- self.resque.pop(key2evict)
- self.value[key] = value
- self.resque[key] = 0
- self.evictionQueue.append(key)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement