[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-lis...@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
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-lis...@inria.fr Archives: http://caml.inr=
ia.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr=
Richard Jones
> 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-lis...@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Alex Baretta
> 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
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
Issac Trotts
> > 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-lis...@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Nicolas Cannasse
> > 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
Jean-Christophe Filliatre
Alex Baretta writes:
> > Map depends on keys to be ordered. This in turn requires to allow fo=
r a
> > user-defined order: assume sets as keys that are implemented by
it
> > must be possible to provide a user-defined order that would treat th=
ose
> > lists as equal. The functor argument of Map contains the compare() w=
hich
> > does just that.
>
> The order function could just as easily be passed as a parameter to al=
l
> 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-lis...@inria.fr Archives: http://caml.inr=
ia.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr=
Yaron M. Minsky
> [ 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
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-lis...@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Michael Hicks
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 <m...@cs.umd.edu>
Fernando Alegre
> 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
Florian Hars
> (But the functorial interface is definitely the best, of course.)
For perl evangelism, sure.
Yours, Florian.
-------------------
To unsubscribe, mail caml-lis...@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/