Re: implementation of set (standard library)

From: Alexey Nogin (
Date: Tue Feb 02 1999 - 19:07:24 MET

Date: Tue, 02 Feb 1999 13:07:24 -0500
From: Alexey Nogin <>
To: Markus Mottl <>
Subject: Re: implementation of set (standard library)


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.

Home Page:
E-Mail: (office), (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