Re: [Caml-list] Map efficiency?

[Jean-Christophe Filliatre <Jean-Christophe.Filliatre@lri.fr>]

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