On Sun, 06 Feb 2005 09:32:19 -0800 (PST), Jon <jdh30@cam.ac.uk> wrote:

> Thus, I would consider the ability of the
> (functional) ocaml Set and Map to fork lineages to be more important.

By "fork lineages" you mean keeping "old" versions of the map around?
I never needed that but I agree it is cute and that it is likely that
I'll need it sometime soon.

> > True, the
> > stack will probably never go above 40 calls but it is a problem if you
> > want to accumulate large structures.
> 
> I would like to think that your stack will be big enough to fit 40
> recursive calls if you expect your computer to handle trillion-element
> maps!

In the worst case (most unbalanced) 40 corresponds to a few million
keys, not trillions. If I haven't made a mistake the minimum number of
keys in a (OCaml) Map with height h is given by the recurrence:
T(h)=1+T(h-1)+T(h-3).

> > Yet another problem is the missing cardinal function.
> An arbitrary number of functions are "missing". You can't expect INRIA to
> implement all infinity of them for you! :-)

Considering the fact that the code in set.ml and map.ml looks like it
is copy&pasted I guess asking for some consistency in the interface is
not unreasonable. In any case copy&pasting the cardinal function
wouldn't provide better performance (I think).

> The STL will probably take <<1ms because the STL's size() is probably O(1)
> whereas Map's fold is O(n). In contrast, forking lineages is probably O(n)
> with the STL (requiring a copy) and O(1) with ocaml's Map.

I haven't actually tested with STL but the implementation of size() is
indeed a simple return. Do you have an example where forking lineages
is useful? As I said, I don't doubt there are situations where it is
useful; just that right now I'm having trouble coming up with a
realistic example.

> You seem to be complaining about poor performance when you know you are
> using the wrong data structure. Talk about unreasonable expectations. :-)

I am exploring possibilities right now. My only "complaint" is that
switching from Hashtbl to Map for a dictionary of about 200000 keys
decreases the performance a LOT! I would have expected a factor of
20-30 but it seems to be a lot more: probably due to memory management
(as Gerd Stolpmann notices) due to the functional nature of Map.

> IIRC, the exact data structure you want is already on the hump. HTH.

Thanks, I'll search for it.

-- 
regards,
 radu
http://rgrig.idilis.ro/