English version
Accueil     À propos     Téléchargement     Ressources     Contactez-nous    

Ce site est rarement mis à jour. Pour les informations les plus récentes, rendez-vous sur le nouveau site OCaml à l'adresse ocaml.org.

Browse thread
Cache algorithms: implementation or library available?
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: 2009-09-22 (11:33)
From: Martin Jambon <martin.jambon@e...>
Subject: Re: [Caml-list] Cache algorithms: implementation or library available?
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):