Subj : Re: best data structure for LRU cache?
To   : comp.programming
From : Jon Harrop
Date : Tue Aug 09 2005 02:22 pm

Willem wrote:
> Jon wrote:
> ) I can't think why not, it just isn't fast. 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.
> 
> Well, okay, but a linked list structure would be a lot more natural for
> this.  Arrays do have the advantage of memory-use efficiency/speed though.

Yes, I was going to post a simple LRU cache based on singly linked lists in
OCaml (about 20 LOC!) but I thought I'd get panned for using OCaml
again. :-)

Interestingly, you can have a nice API in functional languages, where the
"fetch" function is passed two functions: comparison and creation. The
latter creates the desired value and inserts it into the cache if the value
was not already be available. Also, you don't need both key and value with
a custom comparison function.

Hmm, I might actually use this in my own code...

-- 
Dr Jon D Harrop, Flying Frog Consultancy
http://www.ffconsultancy.com

.