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 LAA25779 for caml-redist@pauillac.inria.fr; Sat, 13 May 2000 11:38:58 +0200 (MET DST) Resent-Message-Id: <200005130938.LAA25779@pauillac.inria.fr> 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 TAA14704 for ; Fri, 12 May 2000 19:46:12 +0200 (MET DST) Received: from csla.csl.sri.com (csla.csl.sri.com [192.12.33.2]) by nez-perce.inria.fr (8.10.0/8.10.0) with ESMTP id e4CHk8b05320 for ; Fri, 12 May 2000 19:46:09 +0200 (MET DST) Received: from cylinder.csl.sri.com (IDENT:filliatr@cylinder.csl.sri.com [130.107.15.112]) by csla.csl.sri.com (8.9.1/8.9.1) with ESMTP id KAA12608 for ; Fri, 12 May 2000 10:46:07 -0700 (PDT) Received: (from filliatr@localhost) by cylinder.csl.sri.com (8.9.3/8.8.7) id KAA25727; Fri, 12 May 2000 10:46:06 -0700 X-Authentication-Warning: cylinder.csl.sri.com: filliatr set sender to filliatr@cylinder.csl.sri.com using -f From: Jean-Christophe Filliatre MIME-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: 8bit Message-ID: <14620.17246.749382.470268@cylinder.csl.sri.com> Date: Fri, 12 May 2000 10:46:06 -0700 (PDT) To: caml-list@inria.fr Subject: Sets and maps over integers implemented as Patricia trees X-Mailer: VM 6.62 under Emacs 20.4.1 Reply-To: filliatr@csl.sri.com (Jean-Christophe Filliatre) Resent-From: weis@pauillac.inria.fr Resent-Date: Sat, 13 May 2000 11:38:57 +0200 Resent-To: caml-redist@pauillac.inria.fr Hello ocamlers, I recently implemented sets and maps over integers as Patricia trees, following a paper by Chris Okasaki. (http://www.cs.columbia.edu/~cdo/papers.html#ml98maps) These are much more efficient than the standard library AVLs regarding accesses and merges. (Only a sequential insertion of elements is slower, actually.) The code is available here, under LGPL: http://www.lri.fr/~filliatr/software.en.html == francais ================================================================ Je mets à disposition une implantation efficace d'ensembles et de dictionnaires sur le type int, réalisée à partir d'arbres de Patricia, selon un papier de Chris Okasaki. (http://www.cs.columbia.edu/~cdo/papers.html#ml98maps) Le code, distribué sous licence LGPL, est disponible ici: http://www.lri.fr/~filliatr/software.fr.html -- Jean-Christophe Filliatre Computer Science Laboratory Phone (650) 859-5173 SRI International FAX (650) 859-2844 333 Ravenswood Ave. email filliatr@csl.sri.com Menlo Park, CA 94025, USA web http://www.csl.sri.com/~filliatr