Subj : Re: best data structure for LRU cache?
To   : alt.comp.lang.learn.c-c++,comp.programming
From : Willem
Date : Mon Aug 08 2005 04:02 pm

Digital wrote:
) Can someone recommend the best data structure to implement
) an LRU cache? I was thinking perhaps a priority queue,
) but that requires globally unique timestamps for
) each item that passes through the cache. I was thinking
) something simpler, as you would only need to know the
) ordering of items inside the cache, not globally.

I assume a LRU cache is like a list of objects with a certain maximum size,
that holds objects for quick retrieval, and if an object would be added to
it that would grow it too large, the 'oldest' one (least recently used) is
removed from the cache.

A priority queue seems pointless because the item you add will always have
to be on top of the queue, sometimes moving it from the middle to the top,
but never adding anything in the middle, which is what priority queues are
for.

I'd say make a linked list structure, with the most recently used item at
the tail, and the least recently used at the top.  Keep a pointer to the
tail to add new items, and keep a list size to know when to drop the head
item.  Maybe make it a double linked list if you want to be able to search
most-recently-used first, which might be more efficient.  Or not, depending
on the data distribution and whatever.


SaSW, Willem
-- 
Disclaimer: I am in no way responsible for any of the statements
            made in the above text. For all I know I might be
            drugged or something..
            No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT

.