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 IAA01181 for caml-redistribution; Thu, 4 Feb 1999 08:54:55 +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 FAA00694 for ; Thu, 4 Feb 1999 05:06:57 +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 FAA11706 for ; Thu, 4 Feb 1999 05:06:56 +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 XAA23026; Wed, 3 Feb 1999 23:06:55 -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 XAA13262; Wed, 3 Feb 1999 23:06:54 -0500 (EST) Sender: weis Message-ID: <36B91CD8.C1394F27@CS.Cornell.EDU> Date: Wed, 03 Feb 1999 23:06:48 -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 , OCAML Subject: Re: implementation of set (standard library) References: <199901260015.BAA17324@miss.wu-wien.ac.at> <36B73EDC.B823B4B@CS.Cornell.EDU> Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Alexey Nogin wrote: > 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. You may get the code from ftp://ftp.cs.cornell.edu/pub/nogin/sets/ (it's not there yet, but it should appear within an hour). 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)