""" LRU queue with dictionary lookups based on the Python Cookbook RingBuffer recipe.
A deque-based ringbuffer expires entries past size_max.
Doesn't allow deletion for obvious reasons.
def __init__(self, size_max):
self.queue = deque()
self.size_max = size_max-1
def append(self, value):
if len(self) >= self.size_max:
self.append = self._full_append
def _full_append(self, value):
return super(LRUDict, self).__delitem__(self.queue.popleft())
return "%s(%s)" % (self.__class__.__name__, dict.__repr__(self))
def __setitem__(self, key, value):
if key not in self:
return super(LRUDict, self).__setitem__(key, value)
def __delitem__(self, key):
A queue is fundamentally wrong for this type of use case.
See here for a very good writeup of priority queues and variants.
(not hugely familiar with Java so this stuff might be wrong)
The implementation presented has some bad timing issues (List.Contains is a linear search). I think List.Remove is also a linear search. As well this implementation doesn't seem to do Point (1).
This is a valid min-heap: (5 ((7 (9, 10)), (8 (11, 12)))). Where in (a (b, c)) b and c are children of a.
If you want to peek(5) you have to:
1. peek 5
2. peek the min of 7 and 8 (7)
3. now you have to peek the min of 9, 10 and 8.
4. it's 8, now you have to peek the min of 9,10,11 and 12
The thing is, the only guarantee you have is that a root node of a tree or subtree is smaller than its children. You know nothing of a sibling subtree.
I think maintaining a simple list is the simplest way of doing that, and to speed up lookups for existing items, an index (map item->index) can be maintained. Or the other way around, keep the objects in a map and the keys in the order list. Considering a size n=5 it might even be reasonable to do everything with a simple array and iterate over it.