On Thu, 5 May 2005, Alain Frisch wrote:
> Dear Ext-lib developers,
>
> This tiny module:
> http://www.eleves.ens.fr/home/frisch/soft.html#memo
>
> implements memoization tables with bounded size. Such a table can be
> used to memoize a function without using a lot of memory. A hash
> function is used to retrieve a previously computed value for a given
> key. The implementation uses a nice and simple heuristic to choose what
> to do in case of collision on the hash value for two keys.
>
> Feel free to add this module to ext-lib if you think it can be useful.
On a related topic: the Hashtbl module
Would it be a good thing to add functions which do not require to
recompute the hashed key (with Hashtbl.hash), for efficiency purposes:
val unsafe_find : ('key, 'data) t -> int -> 'key -> 'data
val unsafe_mem : ('key, 'data) t -> int -> 'key -> bool
val unsafe_add : ('key, 'data) t -> int -> 'key -> 'data -> unit
...
For instance, we could write:
let get tbl key lazy_data =
let h = Hashtbl.hash key in
try Hashtbl.unsafe_find tbl h key
with Not_found ->
let data = Lazy.force lazy_data in
Hashtbl.unsafe_add tbl h key data;
data
Martin
--
Martin Jambon, PhD
http://martin.jambon.free.fr
|
