From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id PAA09053; Fri, 13 Jul 2001 15:35:10 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id PAA09197 for ; Fri, 13 Jul 2001 15:35:10 +0200 (MET DST) Received: from fichte.ai.univie.ac.at (fichte.ai.univie.ac.at [131.130.174.156]) by nez-perce.inria.fr (8.11.1/8.10.0) with ESMTP id f6DDZ8j14804 for ; Fri, 13 Jul 2001 15:35:09 +0200 (MET DST) Received: (from markus@localhost) by fichte.ai.univie.ac.at (8.9.3/8.9.3/Debian 8.9.3-21) id PAA04626; Fri, 13 Jul 2001 15:35:05 +0200 Date: Fri, 13 Jul 2001 15:35:05 +0200 From: Markus Mottl To: "Krishnaswami, Neel" Cc: caml-list@inria.fr Subject: Re: [Caml-list] A G'Caml question" + additional info Message-ID: <20010713153505.A20569@fichte.ai.univie.ac.at> References: Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline User-Agent: Mutt/1.2.5i In-Reply-To: ; from neelk@cswcasa.com on Fri, Jul 13, 2001 at 09:12:56 -0400 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk 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... ;) Regards, 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