Subj : Re: best data structure for LRU cache?
To   : comp.programming
From : Alex Fraser
Date : Fri Aug 12 2005 04:07 pm

"Jon Harrop" <usenet@jdh30.plus.com> wrote in message
news:42fb8f31$0$17477$ed2e19e4@ptn-nntp-reader04.plus.net...
> Alex Fraser wrote:
[snip]
> > Indeed. Although it may not be too bad if the number of items is
> > relatively small (and either the items are small or the array contains
> > pointers to items).
>
> Yes and the OP specifically asked for a simple implementation rather than
> a fast implementation.

Actually, the OP asked for recommendations for "the best data structure",
whatever that means...

[snip]
> > It was the choice of array over list that I was getting at. I think a
> > linked list is the natural choice because of the need to move items
> > from the middle/end to the beginning, to maintain LRU ordering.
>
> I think that is quite a small discrepancy. If you use C++ and the STL
> then the list allocator is likely to make efficient use of an array for
> you (avoiding big allocation and deallocation costs)

I'd like to think so but I wouldn't bet on it.

> but if you use an FPL like OCaml then the cost of cons may well outweight
> the cost of looping over a small array (sequential access).

I'm not sure what you mean here.

The sequential access of the array is the advantage compared to a list; the
disadvantage is the need to move chunks of the array around. The catch with
using an array is that while you can mitigate that disadvantage by storing
pointers to items in the array, in doing so you lose the advantage of
sequential access.

Alex

.