English version
Accueil     À propos     Téléchargement     Ressources     Contactez-nous    

Ce site est rarement mis à jour. Pour les informations les plus récentes, rendez-vous sur le nouveau site OCaml à l'adresse ocaml.org.

Browse thread
Re: [Caml-list] A G'Caml question" + additional info
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: 2001-07-13 (13:35)
From: Markus Mottl <markus@m...>
Subject: Re: [Caml-list] A G'Caml question" + additional info
On Fri, 13 Jul 2001, Krishnaswami, Neel wrote:
> He has some timing data comparing splay trees, balanced binary 
> trees, Patricia tries, and red-black trees in his paper "Fast 
> Mergeable Integer Maps." To summarize, red-black trees were the 
> fastest on lookup, and second-fastest on insertion. But they don't
> perform very well on the merge operation. (These are all fairly
> tuned implementations, though.)

As usual, never trust statistics that you haven't faked yourself...

Such things can be pretty language and compiler dependent. At least
what concerns Patricia trees, I can assert that they really perform
very well in OCaml. This is obviously not true for red-black trees:
on my simple tests with random numbers, insertion took longer than with
balanced binary trees, and lookup also didn't seem competitive. Anyway,
I don't claim that my statistics are faked better than his... ;)

Markus Mottl

Markus Mottl                                             markus@oefai.at
Austrian Research Institute
for Artificial Intelligence                  http://www.oefai.at/~markus
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr