Re: [Caml-list] Cache algorithms: implementation or library available?

[Martin Jambon <martin.jambon@ens-lyon.org>]

Hugo Ferreira wrote:
> Hello,
> 
> I would like to know if anyone has or knows of an Ocaml
> library or open-source code implementation of some cache
> algorithms (example: least recently used).
> 
> Basically I need to cache a function that maps a list
> of ordered integers into a value (float, integer). I
> would like something that allows setting a maximum size
> of the map and automatically discards the data.

There are so many possible access patterns and trade-offs:

- speed requirements?
- memory requirements?
- constant size or just bounded?
- is the probability of accessing an element a function of time?

I see two frequent use cases:

a.  some elements are accessed more frequently than others regardless of time
b.  recently-accessed elements have a higher probability of being accessed

Alain Frisch provides an implementation of roughly a hash table in which
buckets hold only one element, which looks great at least for case (a):

  http://alain.frisch.fr/soft.html#memo



Martin

-- 
http://mjambon.com/