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
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                                   
Austrian Research Institute
for Artificial Intelligence        
Bug reports:  FAQ:
To unsubscribe, mail  Archives: