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 KAA03911; Tue, 4 Nov 2003 10:26:33 +0100 (MET) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id KAA03969 for ; Tue, 4 Nov 2003 10:26:32 +0100 (MET) Received: from lri.lri.fr (lri.lri.fr [129.175.15.1]) by concorde.inria.fr (8.11.1/8.11.1) with ESMTP id hA49QV102383 for ; Tue, 4 Nov 2003 10:26:31 +0100 (MET) Received: from pc8-123 (pc8-123 [129.175.8.123]) by lri.lri.fr (8.12.10/jtpda-5.4) with ESMTP id hA49BpUV007175 ; Tue, 4 Nov 2003 10:11:52 +0100 (MET) Received: from filliatr by pc8-123 with local (Exim 3.35 #1 (Debian)) id 1AGxE7-0008C4-00; Tue, 04 Nov 2003 10:11:51 +0100 From: Jean-Christophe Filliatre MIME-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: 8bit Message-ID: <16295.27991.49290.47666@gargle.gargle.HOWL> Date: Tue, 4 Nov 2003 10:11:51 +0100 To: Dustin Sallings Cc: caml-list@inria.fr Subject: Re: [Caml-list] Map efficiency? In-Reply-To: References: X-Mailer: VM 7.03 under Emacs 20.7.2 Reply-To: Jean-Christophe.Filliatre@lri.fr (Jean-Christophe Filliatre) X-MailScanner: Found to be clean X-Loop: caml-list@inria.fr X-Spam: no; 0.00; filliatre:01 filliatre:01 lri:01 caml-list:01 hashtbl:01 hashtbl:01 hash:01 hash:01 okasaki's:01 beginners:01 generic:01 map's:01 ord:01 pervasives:01 generic:01 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk Dustin Sallings writes: > > Should I expect Hashtbl to be more efficient than Map with the same > key type? I'm taking a small performance hit in a log processing app > after turning a Hashtbl into a Map. Hashtbl.add runs in O(1) and Hashtbl.find can be so (or almost) when the hash function is good enough. Map.add and Map.find are always in O(ln n) where n is the total number of keys. The main interest of maps wrt hash tables is to be persistent (in the sense of Okasaki's book, not of the PERSIL library). > Also, is there a particular reason Map is so, um, inaccessible to > beginners? Hashtbl's generic interface is much more inviting than > Map's functorial-only interface, especially to those not terribly > familiar with the module system. Just copy the body of Map.Make and replace Ord.compare by Pervasives.compare and you'll get a polymorphic version of Map, as easy to use as Hashtbl's generic interface. But I agree: it's a shame ocaml does not provide it. -- Jean-Christophe Filliātre (http://www.lri.fr/~filliatr) ------------------- To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/ Beginner's list: http://groups.yahoo.com/group/ocaml_beginners