Solving Problems Using Data Structures

http://variadic.me/posts/2013-03-06-solving-problems-data-structures.html

by variadic • 13 years ago

20 14 13 years ago

iand• 13 years ago

Wouldn't this be better implemented using a standard priority queue where the score is related to the timestamp of insertion?

shintoist2• 13 years ago

A queue implies the items leave the data structure, that doesn't fit the use case.

grapjas• 13 years ago

Can't items leave when getting kicked out by a new item?

ohwp• 13 years ago

My thought exactly. I don't get his example. But maybe it's a speed issue. Adding items to a Dictionary might be faster than updating a timestamp on an object.

shintoist2• 13 years ago

That doesn't make sense. The fundamental operations on a queue is push and pop. If you pop from the queue, you remove it from the queue. So on page reload, the 5 latest viewed entries would be gone. You popped them.

A queue is fundamentally wrong for this type of use case.

ianbishop• 13 years ago

There is actually an LRU map implemented in Java, though it is sort of hidden in the LinkedHashMap using a special constructor.

http://docs.oracle.com/javase/1.4.2/docs/api/java/util/Linke...

jwn• 13 years ago

One issue with that is that it doesn't expel older entries. The capacity specified in the constructor is just the initial capacity.

jehud• 13 years ago

Why not use a Set and a doubly linked list?

vemv• 13 years ago

I'd use a sorted set.

headfake• 13 years ago

from collections import deque

class LRUDict(dict):

    """ 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):
        dict.__init__(self)
        self.queue = deque()
        self.size_max = size_max-1

    def append(self, value):
        self.queue.append(value)
        if len(self) >= self.size_max:
            self.append = self._full_append

    def _full_append(self, value):
        self.queue.append(value)
        return super(LRUDict, self).__delitem__(self.queue.popleft())

    def __repr__(self):
        return "%s(%s)" % (self.__class__.__name__, dict.__repr__(self))

    def __setitem__(self, key, value):
        if key not in self:
            self.append(key)
        return super(LRUDict, self).__setitem__(key, value)

    def __delitem__(self, key):
        pass

Solving Problems Using Data Structures

Related Stories