LRU/MRU list

[Greg Menke]

Hi,

I have a hash-table I use for random, keyed lookups, it works fine. I also
want to maintain a most recently used list of accesses to the table;
whenever an entry is accessed from the hash-table, update a corresponding
item in some other data construct such that the least frequently accessed
items can be removed from the hash-table at some later time.

My first idea (so far only..) is the obvious inefficient one, keep a list of
the hash-table keys. Whenever an item in the hash-table is accessed, move
its entry in the list to the head. Least used items are then found at the
end of the list. I imagine its expensive to find & delete particular items
within the list, so I was wondering if anyone could supply a hint for an
approach which might be more efficient.

Thanks,

Gregm

[ro...@corman.net]

In article <8eur09$88u$1...@bob.news.rcn.net>,

"Greg Menke" <nos...@erols.com> wrote:
> Hi,
>
> I have a hash-table I use for random, keyed lookups, it works fine.

>... stuff deleted

>I imagine its expensive to find & delete particular items
> within the list, so I was wondering if anyone could supply a hint for
> an approach which might be more efficient.
>
> Thanks,
> > Gregm

I would not use another data structure (list or otherwise).
I would add a "last touched" variable to the value you are storing
(add a wrapper struct if necessary), and whenever that value is
retrieved, update that variable.
When the hash-table gets too full, and you want to delete some
things, use iteration (maphash or with-hash-table-iterator) to
create a temp data structure of the values, sort them, and remove the
LRU items. This means you are only doing this work when you purge,
if ever, not every time you retrieve an item.
The "last touched" variable can be set to the system time
(get-internal-run-time) but it can just as easily be an integer
variable that you increment each time you touch something. As
long as it creates an ordered series you can sort on.
I recently converted a caching module that used the algorithm
you mentioned to the method explained here, and it made it faster.
However, that was in java, and list handling is not as efficient
in java.

Roger Corman

Sent via Deja.com http://www.deja.com/
Before you buy.

[David Hanley]

Greg Menke wrote:

> Hi,
>

> I have a hash-table I use for random, keyed lookups, it works fine. I also
> want to maintain a most recently used list of accesses to the table;
> whenever an entry is accessed from the hash-table, update a corresponding
> item in some other data construct such that the least frequently accessed
> items can be removed from the hash-table at some later time.
>
> My first idea (so far only..) is the obvious inefficient one, keep a list of
> the hash-table keys. Whenever an item in the hash-table is accessed, move
> its entry in the list to the head. Least used items are then found at the

> end of the list. I imagine its expensive to find & delete particular items

> within the list, so I was wondering if anyone could supply a hint for an
> approach which might be more efficient.

Well, I have done this myself. They way I did it was to have the real data
items stored in a doubly linked list. The hash table's values were the
individual nodes of the list. Popping a node to the head of the list or moving
it up a slot are trivial, though in the second case, it might be more efficient
and simpler to just store the indices of an array, though that's not as
"correct."

The advantage of this approach is that there's never a halting operation..

dave