Subj : Re: best data structure for LRU cache? To : comp.programming From : Alex Fraser Date : Tue Aug 09 2005 03:19 pm "Jon Harrop" wrote in message news:42f89a89$0$17487$ed2e19e4@ptn-nntp-reader04.plus.net... > Willem wrote: > > Jon wrote: > > ) Alex Fraser wrote: > > )> "Jon Harrop" wrote in message > > )> news:42f66c04$0$24029$ed2619ec@ptn-nntp-reader01.plus.net... > > )>> I've never done this before, but in the simplest case I think you > > )>> can just use an int index into an array. The int points to the > > )>> oldest entry. To insert you overwrite the array entry at the int > > )>> before incrementing it. To search, consider each entry in turn. > > )> > > )> You are taking the piss, right? > > ) > > ) What do you think is wrong with that? > > > > You can't remove items from the middle of the cache this way. > > I can't think why not, it just isn't fast. 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). > My point was simply that you don't need to use balanced binary trees or > hash tables if you don't mind a slow solution. The sole purpose of the tree/hash table in what I described is to improve search performance. But whether you use one is independent of whether you use an array or linked list to hold the items (or pointers to the items). 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. Alex .