From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: weis Received: (from weis@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id QAA25688 for caml-redistribution; Wed, 3 Feb 1999 16:43:45 +0100 (MET) 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 TAA16106 for ; Tue, 2 Feb 1999 19:07:34 +0100 (MET) Received: from simon.cs.cornell.edu (SIMON.CS.CORNELL.EDU [128.84.154.10]) by nez-perce.inria.fr (8.8.7/8.8.7) with ESMTP id TAA05782 for ; Tue, 2 Feb 1999 19:07:32 +0100 (MET) Received: from cloyd.cs.cornell.edu (CLOYD.CS.CORNELL.EDU [128.84.227.15]) by simon.cs.cornell.edu (8.8.8/8.8.8/R-1.11) with ESMTP id NAA03366; Tue, 2 Feb 1999 13:07:31 -0500 (EST) Received: from CS.Cornell.EDU (nogin@GULAG.CS.CORNELL.EDU [128.84.248.53]) by cloyd.cs.cornell.edu (8.8.8/8.8.8/M-1.12) with ESMTP id NAA15350; Tue, 2 Feb 1999 13:07:29 -0500 (EST) Sender: weis Message-ID: <36B73EDC.B823B4B@CS.Cornell.EDU> Date: Tue, 02 Feb 1999 13:07:24 -0500 From: Alexey Nogin Organization: Cornell University, department of Computer Science X-Mailer: Mozilla 4.08 [en] (X11; U; Linux 2.0.36 i686) MIME-Version: 1.0 To: Markus Mottl CC: OCAML Subject: Re: implementation of set (standard library) References: <199901260015.BAA17324@miss.wu-wien.ac.at> Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Hi, Markus Mottl wrote: > I have taken a look at the implementation of sets in the standard library > and thought that the "add" function could be implemented differently > (possibly faster). Our group wrote several implementation of sets - based on splay trees, red-black trees, etc. Implementation based on the splay trees turned out to be much faster than the OCAML Set module when the "mem" operation is more frequent than add/union/remove/inter/diff operations. But on our usage pattern it turned out that red-black trees are much faster than both Set and SplaySet. If somebody is interested, I can put the code on ftp. Alexey -------------------------------------------------------------- Home Page: http://www.cs.cornell.edu/nogin/ E-Mail: nogin@cs.cornell.edu (office), ayn2@cornell.edu (home) Office: Upson 4139, tel: 1-607-255-4934 ICQ #: 24708107 (office), 24678341 (home)