On Fri, 4 Feb 2005 10:26:55 +0000, Jon Harrop <jon@jdh30.plus.com> wrote:

> The code to implement a simple tree is unwieldy in C++ (e.g. 1975 LOC
> in stl_tree.h and stl_map.h vs 198 LOC in map.ml).

The implementation in stl_tree is not a "simple" tree. The difference
in size is also because the STL implementation is more efficient. For
one thing RB trees are better balanced than HB(2) trees. Another
observation is that fold on maps is not tail recursive. True, the
stack will probably never go above 40 calls but it is a problem if you
want to accumulate large structures. Yet another problem is the
missing cardinal function. I have a StringMap with about 200000: it
takes about 3 minutes (!!!) to get its length using a fold. That would
take something like 1 millisecond in C++.

I'm a bit annoyed right now with OCaml's Map because I'm writting a
tool where I need to construct big associative tables from strings to
other data. An implementation with Hashtbl makes the program work in 1
minute. The problem is that the next execution phase needs to fold
over the tables in increasing order of keys. Simple, no? Switch from
Hashtbl to Map. Right. Now the same program doesn't finish executing
in 3 hours. I would have expected a running time of about 20-30
minutes.

Maybe a hand-written lexical-tree will be good enough.

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