Subj : Re: best data structure for LRU cache? To : comp.programming From : CBFalconer Date : Thu Aug 11 2005 11:16 pm Jon Harrop wrote: > Alex Fraser wrote: >> "Jon Harrop" wrote in message >> >>> 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). > > Yes and the OP specifically asked for a simple implementation > rather than a fast implementation. > >>> 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). > > Yes. I chose arrays for brevity in C. You don't need the complexity. Look up heaps. Fast and simple. -- "If you want to post a followup via groups.google.com, don't use the broken "Reply" link at the bottom of the article. Click on "show options" at the top of the article, then click on the "Reply" at the bottom of the article headers." - Keith Thompson .