Re: [Caml-list] Impact of GC on memoized algorithm

[Damien Doligez <damien.doligez@inria.fr>]

On Apr 11, 2005, at 17:48, Alex Baretta wrote:

> No, I don't, so the cost of memoization should only impact the 
> multiplicative constant and not the complexity class of my algorithm. 
> This is good. Now I'll have to experiment with Maps and Hashtbls with 
> and without custom hash functions to find the most efficient caching 
> scheme. Any suggestions?

Assuming you are going to use hash tables:

In my experience, it is important to pay attention to the cost of the
hashing function.  If you can avoid going through the whole structure to
compute the hash, you'll save a lot of time.

It may also be a good idea to limit the number of cache entries, instead
of just letting the cache grow arbitrarily large.  I've had good results
by deleting some entries at random when the cache gets too big.

-- Damien