English version
Accueil     À propos     Téléchargement     Ressources     Contactez-nous    

Ce site est rarement mis à jour. Pour les informations les plus récentes, rendez-vous sur le nouveau site OCaml à l'adresse ocaml.org.

Browse thread
[Caml-list] Map efficiency?
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: 2003-11-04 (09:26)
From: Jean-Christophe Filliatre <Jean-Christophe.Filliatre@l...>
Subject: Re: [Caml-list] Map efficiency?

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