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 PAA08632; Fri, 13 Jul 2001 15:10:23 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id PAA08580 for ; Fri, 13 Jul 2001 15:10:23 +0200 (MET DST) Received: from smtp1.cswv.com (smtp1.cswv.com [4.17.129.17]) by concorde.inria.fr (8.11.1/8.10.0) with ESMTP id f6DDAMT12575 for ; Fri, 13 Jul 2001 15:10:22 +0200 (MET DST) Received: from smtp1.cswv.com ([4.17.129.17]) by smtp1.cswv.com with Microsoft SMTPSVC(5.5.1877.197.19); Fri, 13 Jul 2001 09:10:52 -0400 Received: FROM exchange1.cswv.com BY smtp1.cswv.com ; Fri Jul 13 09:10:51 2001 -0400 Received: by exchange1.cswv.com with Internet Mail Service (5.5.2653.19) id ; Fri, 13 Jul 2001 09:13:06 -0400 Message-ID: From: "Krishnaswami, Neel" To: caml-list@inria.fr Subject: Re: [Caml-list] A G'Caml question" + additional info Date: Fri, 13 Jul 2001 09:12:56 -0400 MIME-Version: 1.0 X-Mailer: Internet Mail Service (5.5.2653.19) Content-Type: text/plain; charset="iso-8859-1" Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk Markus Mottl [mailto:markus@mail4.ai.univie.ac.at] wrote: > > Having tried RedBlackSet as presented in Okasaki's book a while ago, > I was rather disappointed. It didn't perform faster (rather slower) > than the Set-module (balanced binary trees) on some quick > examples that I had tried. But maybe my simple tests were not > representative. 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.) I've been curious about implementing randomized treaps and seeing how well they do, since they seem simpler than any other balanced binary tree implementation. > > > Note that the non-polymorphic version also has advantages for > > > users: e.g. they don't have to pass around comparison functions > > > all the time. > > > > ??? I don't understand this. In both the object version I posted > > and the functorial version that Brian Rogoff posted, a hacker > > only needs to mention the comparison function when creating the > > type, and then never again when making or using trees. > > In the functorial version you naturally have to use a functor > application. I meant a polymorphic implementation without functors, > since I think you had complained somewhere about having to apply > functors. This was probably not obvious from my text. Applying a functor doesn't bother me. What I find annoying is the need to functorize my own code if I want to write functions that work independently of the element type. It doesn't take very many of these before my source contains more functor declarations than actual code. A sufficiently powerful include facility for G'Caml can make this problem go away, since you could define a generic and have each functor instantiation add its specialized methods automatically to the generic. > > In fact, my first experiment along these lines was to use a record > > with a tree and a comparison function in it. But even there, one > > could use currying to mention the function comparison only once. > > (I rejected it because it permitted trees with different but type- > > compatible comparison functions to intermix.) > > But you have to manually curry every Set-function you want to use at > least once. The functor application creates the closures for the whole > Set-module at once. Oh, I see what you mean. That's true but since I'd only implement the Set once I don't much care. I tend to worry more about cruft associated with code that uses the library. -- Neel Krishnaswami neelk@cswcasa.com ------------------- 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