[Caml-list] Map efficiency?

[Caml-list] Map efficiency?

[Dustin Sallings]

	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.

	This was a sample of 340,720 records.  There were that many finds and 
1,440 adds.  Since the Hashtbl is mutable, the add is in place and the 
usage is pretty straightforward.  In order to get Map to work the same 
way, I am using a reference to it everywhere.

	The times were actually very similar between the two, but I was kinda 
hoping Map would be faster.  :)

	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.

-- 
Dustin Sallings

-------------------
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

Re: [Caml-list] Map efficiency?

[Jean-Christophe Filliatre]

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

Re: [Caml-list] Map efficiency?

[Christian Lindig]

On Mon, Nov 03, 2003 at 11:59:24PM -0800, Dustin Sallings wrote:
> 	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.

Map depends on keys to be ordered. This in turn requires to allow for a
user-defined order: assume sets as keys that are implemented by
unordered lists. Different lists can represent the same set. Hence, it
must be possible to provide a user-defined order that would treat those
lists as equal. The functor argument of Map contains the compare() which
does just that.

-- Christian

-------------------
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

Re: [Caml-list] Map efficiency?

[Richard Jones]

On Tue, Nov 04, 2003 at 10:11:51AM +0100, Jean-Christophe Filliatre wrote:
> 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.

It would be good to document a few example usages in the map.mli file.

Rich.

-- 
Richard Jones. http://www.annexia.org/ http://freshmeat.net/users/rwmj
Merjis Ltd. http://www.merjis.com/ - all your business data are belong to you.
MAKE+ is a sane replacement for GNU autoconf/automake. One script compiles,
RPMs, pkgs etc. Linux, BSD, Solaris. http://www.annexia.org/freeware/makeplus/

-------------------
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

Re: [Caml-list] Map efficiency?

[Alex Baretta]

> Map depends on keys to be ordered. This in turn requires to allow for a
> user-defined order: assume sets as keys that are implemented by
> unordered lists. Different lists can represent the same set. Hence, it
> must be possible to provide a user-defined order that would treat those
> lists as equal. The functor argument of Map contains the compare() which
> does just that.

The order function could just as easily be passed as a parameter to all
functions working on the map. There is no reason not to have a
polymorphic version of the Map module in the standard library. Am I
wrong in believing that someone out there wrote such a module already?

Alex


-------------------
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

Re: [Caml-list] Map efficiency?

[Dustin Sallings]

On Nov 4, 2003, at 1:39, Christian Lindig wrote:

>> 	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.
>
> Map depends on keys to be ordered. This in turn requires to allow for a
> user-defined order: assume sets as keys that are implemented by
> unordered lists. Different lists can represent the same set. Hence, it
> must be possible to provide a user-defined order that would treat those
> lists as equal. The functor argument of Map contains the compare() 
> which
> does just that.

	I'm not suggesting doing away with the functorial interface, just 
providing an additional one that is more accessible.  I mean, something 
like this would be cool (excuse my abuse of syntax):

Map.create ('a -> 'a -> int)

	Then my app would just do this:

Map.create compare;;

-- 
Dustin Sallings

-------------------
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

Re: [Caml-list] Map efficiency?

[Issac Trotts]

>  > 	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.

Thanks for the idea.  Here is the modified code:

  http://redwood.ucdavis.edu/~issac/map2.tar.gz

# #load "map2.cmo";;
# let map = ref Map2.empty;;
val map : ('_a, '_b) Map2.t ref = {contents = <abstr>}
# map := Map2.add "foo" 23 !map;;
- : unit = ()
# map := Map2.add "bar" 42 !map;;
- : unit = ()
# Map2.iter (fun key v -> Printf.printf "%s : %i\n" key v) !map;;
bar : 42
foo : 23
- : unit = ()

-- 
Issac Trotts

-------------------
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

Re: [Caml-list] Map efficiency?

[Nicolas Cannasse]

> > Map depends on keys to be ordered. This in turn requires to allow for a
> > user-defined order: assume sets as keys that are implemented by
> > unordered lists. Different lists can represent the same set. Hence, it
> > must be possible to provide a user-defined order that would treat those
> > lists as equal. The functor argument of Map contains the compare() which
> > does just that.
>
> The order function could just as easily be passed as a parameter to all
> functions working on the map. There is no reason not to have a
> polymorphic version of the Map module in the standard library. Am I
> wrong in believing that someone out there wrote such a module already?
>
> Alex

There is one : module PMap , which is part of the ExtLib CVS :
http://sourceforge.net/projects/ocaml-lib
Since it's been added recently, there is no mli yet.

Nicolas Cannasse

-------------------
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

Re: [Caml-list] Map efficiency?

[Jean-Christophe Filliatre]

Alex Baretta writes:
 > > Map depends on keys to be ordered. This in turn requires to allow for a
 > > user-defined order: assume sets as keys that are implemented by
 > > unordered lists. Different lists can represent the same set. Hence, it
 > > must be possible to provide a user-defined order that would treat those
 > > lists as equal. The functor argument of Map contains the compare() which
 > > does just that.
 > 
 > The order function could just as easily be passed as a parameter to all
 > functions working on the map. 

This is not a good idea,  because elements could be inserted using one
ordering function  and looked for  using a different one,  with tragic
consequences.

A slightly better  approach would be to pass  the ordering function to
Map.empty only, which  would store it inside the  data structure. This
is  exactly what was  done in  Caml Light,  when Caml  did not  have a
module system yet. 
(see http://camlcvs.inria.fr/cgi-bin/cvsweb.cgi/camllight/src/lib/map.mli?rev=1.3&content-type=text/x-cvsweb-markup)

(But the functorial interface is definitely the best, of course.)

-- 
Jean-Christophe Filliâtre

-------------------
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

Why are functors better? (Re: [Caml-list] Map efficiency?)

[Yaron M. Minsky]

On Fri, 2003-11-07 at 03:27, Jean-Christophe Filliatre wrote:
> [ Some discussion of methods for building maps without functors ]
>
> (But the functorial interface is definitely the best, of course.)

I don't understand this perspective at all.  Functors seem like a fairly
problematic corner of the language.  In this case, except for some
possible efficiency issues, it seems clear that a non-functorial map is
preferable, for simplicity and ease-of-use issues, and performance
aside, I can't see much to recommend the current functorial approach.

Functors would be a lot more useful if they could be used as a
large-scale structural tool.  Sadly, the current implementation makes
this quite difficult, since there's no good way of parameterizing
multiple modules at once (as noted in a previous thread.  See

http://groups.google.com/groups?q=group%3Afa.caml+functors+yminsky&ie=UTF-8&oe=UTF-8&hl=en&btnG=Google+Search

for details.)  For most situations where you'd really need them, they're
not powerful enough.  And for the situations where they're powerful
enough, they're usually overkill.  Map and Set are examples where they
almost strictly get in the way.

y

-- 
|--------/            Yaron M. Minsky              \--------|
|--------\ http://www.cs.cornell.edu/home/yminsky/ /--------|

Open PGP --- KeyID B1FFD916
Fingerprint: 5BF6 83E1 0CE3 1043 95D8 F8D5 9F12 B3A9 B1FF D916



-------------------
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

Re: Why are functors better? (Re: [Caml-list] Map efficiency?)

[Michael Hicks]

Benjamin Pierce did a nice talk at ICFP a couple of years ago about
sophisticated module systems, examining where (or if) they are really
needed.  The slides are at

http://www.cis.upenn.edu/~bcpierce/papers/modules-icfp.ps

This is not exactly on target for your point about ease-of-use, but it's
related.
Mike


On Fri, 2003-11-07 at 06:39, Yaron M. Minsky wrote:
> On Fri, 2003-11-07 at 03:27, Jean-Christophe Filliatre wrote:
> > [ Some discussion of methods for building maps without functors ]
> >
> > (But the functorial interface is definitely the best, of course.)
> 
> I don't understand this perspective at all.  Functors seem like a fairly
> problematic corner of the language.  In this case, except for some
> possible efficiency issues, it seems clear that a non-functorial map is
> preferable, for simplicity and ease-of-use issues, and performance
> aside, I can't see much to recommend the current functorial approach.
> 
> Functors would be a lot more useful if they could be used as a
> large-scale structural tool.  Sadly, the current implementation makes
> this quite difficult, since there's no good way of parameterizing
> multiple modules at once (as noted in a previous thread.  See
> 
> http://groups.google.com/groups?q=group%3Afa.caml+functors+yminsky&ie=UTF-8&oe=UTF-8&hl=en&btnG=Google+Search
> 
> for details.)  For most situations where you'd really need them, they're
> not powerful enough.  And for the situations where they're powerful
> enough, they're usually overkill.  Map and Set are examples where they
> almost strictly get in the way.
> 
> y
-- 
Michael Hicks <mwh@cs.umd.edu>

-------------------
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

Re: Why are functors better? (Re: [Caml-list] Map efficiency?)

[Fernando Alegre]

On Fri, Nov 07, 2003 at 06:39:41AM -0500, Yaron M. Minsky wrote:

> Functors would be a lot more useful if they could be used as a
> large-scale structural tool.  Sadly, the current implementation makes
> this quite difficult, since there's no good way of parameterizing
> multiple modules at once (as noted in a previous thread.  See


This seems to be related to the fact that modules are not first class objects. If they
were, you could easily parametrize across modules:

In file x.ml:

module type SIGX = sig ... end
type x_module = SIGX

module X = struct ... end

let x = module (X:SIGX) (* type of x is x_module *)

In file a.ml:

module A = struct

  let f x = let module X = x in X.do_something()

In file b.ml:

module B = struct

  let f x = let module X = x in X.do_something() + A.do_something()

end

This code, of course, cannot be compiled. However, the corresponding version with
classes is trivial to do. This fact seems to be one of the strong reasons why people
prefer them over modules, despite the tendency of classes to become long spaghetti.

Fernando

-------------------
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

Re: [Caml-list] Map efficiency?

[Florian Hars]

Jean-Christophe Filliatre wrote:
> (But the functorial interface is definitely the best, of course.)

For perl evangelism, sure.

Yours, Florian.

-------------------
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