Version française
Home     About     Download     Resources     Contact us    

This site is updated infrequently. For up-to-date information, please visit the new OCaml website at

Browse thread
Impact of GC on memoized algorithm
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: 2005-04-14 (09:52)
From: Damien Doligez <damien.doligez@i...>
Subject: Re: [Caml-list] Impact of GC on memoized algorithm
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