Re: implementation of set (standard library)

From: Alexey Nogin (nogin@cs.cornell.edu)
Date: Thu Feb 04 1999 - 05:06:48 MET


Date: Wed, 03 Feb 1999 23:06:48 -0500
From: Alexey Nogin <nogin@cs.cornell.edu>
To: Markus Mottl <mottl@miss.wu-wien.ac.at>, OCAML <caml-list@inria.fr>
Subject: Re: implementation of set (standard library)

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)



This archive was generated by hypermail 2b29 : Sun Jan 02 2000 - 11:58:19 MET