From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id SAA21496; Mon, 5 Nov 2001 18:55:59 +0100 (MET) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f 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 SAA21477 for ; Mon, 5 Nov 2001 18:55:57 +0100 (MET) Received: from dpt-info.u-strasbg.fr (dpt-info.u-strasbg.fr [130.79.44.193]) by nez-perce.inria.fr (8.11.1/8.10.0) with ESMTP id fA5HtvX27355 for ; Mon, 5 Nov 2001 18:55:57 +0100 (MET) Received: (from luther@localhost) by dpt-info.u-strasbg.fr (8.9.3/8.9.3) id SAA07793; Mon, 5 Nov 2001 18:54:39 +0100 Date: Mon, 5 Nov 2001 18:54:39 +0100 From: Sven To: Florian Hars Cc: Jean-Christophe Filliatre , "Marcin 'Qrczak' Kowalczyk" , caml-list@inria.fr Subject: Re: [Caml-list] Specialized dictionaries Message-ID: <20011105185439.A7781@dpt-info.u-strasbg.fr> References: <15334.27347.973997.129488@pc803> <20011105183653.A15329@hars> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Mailer: Mutt 1.0.1i In-Reply-To: <20011105183653.A15329@hars>; from florian@hars.de on Mon, Nov 05, 2001 at 06:36:54PM +0100 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk On Mon, Nov 05, 2001 at 06:36:54PM +0100, Florian Hars wrote: > On Mon, Nov 05, 2001 at 11:32:51AM +0100, Jean-Christophe Filliatre wrote: > > Marcin 'Qrczak' Kowalczyk writes: > > > I need dictionaries indexed by ints which must be very fast. > > > > To be even more efficient, I'm afraid you have to follow your idea, > > that is to inline this hash function in your own copy of hashtbl.ml. > > Wouldn't the Patricia Trees (from the > "the-name-of-the-author-currently-escapes-me"-department :-)) mentioned on > http://www.lri.fr/~filliatr/software.en.html be useful in this case (unless > the problem needs the in-place update available with Hashtbl)? > The documentation claims that "The > performances are always better than the standard library's module > [Set], except for linear insertion (building a set by insertion of > consecutive integers)." The standard library [Set] is a functional B tree, if i am not wrong, it is quite fast, but depending on the apps, it will not be faster than the hashtable, that's why we have the hashables. Sven Luther ------------------- Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/ To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr