Subj : Re: best data structure for LRU cache? To : comp.programming From : Jon Harrop Date : Thu Aug 11 2005 06:41 pm Alex Fraser wrote: > "Jon Harrop" wrote in message > news:42f89a89$0$17487$ed2e19e4@ptn-nntp-reader04.plus.net... >> 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. > 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) 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). -- Dr Jon D Harrop, Flying Frog Consultancy http://www.ffconsultancy.com .