I actually used a string * int key initially, but I thought that it was
very silly to repeat the string a million times when once would suffice.
Anyhow, now Ashish and I have a full-fledged map of maps module.

I think I found the expensive operation -- I am trying to take the
average of some logged values that is associated with a string,int pair.
So, I am taking the log of some float and adding it to the accumulator
-- taking the log every time I insert a value is probably the culprit. I
suppose that one way to circumvent this problem would be to instead
multiply numbers into the accumulator and take the log at the end, since
log(a*b) = log(a) + log(b) but these numbers are pretty big so I am
afraid of overflow.

I guess I could use ocamlprof to make sure that the log is indeed the
culprit.

Thanks for your help, Richard!

David

Richard Jones wrote:
>
> On Fri, Oct 31, 2008 at 10:32:13AM -0400, David Koppstein wrote:
> > let add k1 k2 elem t =
> > let m2 =
> > try Fst.find k1 t
> > with Not_found -> Snd.empty
> > in
> > let m2 = Snd.add k2 elem m2 in
> > Fst.add k1 m2 t
> >
> > where Fst is the first map and Snd is the second map, k1 is the key of
> > the first, and k2 is the key of the second.
> >
> > Every time I do this, am I completely rewriting the int map, which is 1
> > million ints keys plus their elements? If not, how does the compiler
> get
> > around this, and are there still any significant performance issues?
>
> No, you're not rewriting either map. You probably want to have a look
> for some resources on 'persistent' data structures to understand
> what's "really" happening in memory:
>
> http://en.wikipedia.org/wiki/Purely_functional#Examples_of_purely_functional_data_structures
> <http://en.wikipedia.org/wiki/Purely_functional#Examples_of_purely_functional_data_structures>
>
> > Will using Hashtbls circumvent this problem?
>
> Hashtbls aren't persistent, and depending on your application that can
> be a good or bad thing. You'll probably want to benchmark the whole
> program to find out which it is. (In some circumstances you simply
> need to use a persistent structure to ease the programming).
>
> This book by Chris Okasaki is the canonical reference, albeit rather
> difficult to follow beyond the first few chaptes:
>
> http://www.amazon.com/Purely-Functional-Structures-Chris-Okasaki/dp/0521663504
> <http://www.amazon.com/Purely-Functional-Structures-Chris-Okasaki/dp/0521663504>
>
> BTW, have you thought about using a single map which is keyed on
> (string, int) key?
>
> Rich.
>
> --
> Richard Jones
> Red Hat
>
>

•  2
  New Members

> have you thought about using a single map which is keyed on (string, int)
key
I've been using a map of maps also because it allows more flexible
operations. I can perform operations on all the values, or all the values
for each string. Actually, I've been wondering if there are any
generalizations of this. What if we need three or four keys. I guess a
database is the ultimate answer but a lighter-weight solution would be
better.

On Sun, Nov 2, 2008 at 10:52 AM, Richard Jones <rich <at> annexia.org> wrote:

> On Fri, Oct 31, 2008 at 10:32:13AM -0400, David Koppstein wrote:
> > let add k1 k2 elem t =
> > let m2 =
> > try Fst.find k1 t
> > with Not_found -> Snd.empty
> > in
> > let m2 = Snd.add k2 elem m2 in
> > Fst.add k1 m2 t
> >
> > where Fst is the first map and Snd is the second map, k1 is the key of
> > the first, and k2 is the key of the second.
> >
> > Every time I do this, am I completely rewriting the int map, which is 1
> > million ints keys plus their elements? If not, how does the compiler get
> > around this, and are there still any significant performance issues?
>
> No, you're not rewriting either map. You probably want to have a look
> for some resources on 'persistent' data structures to understand
> what's "really" happening in memory:
>
>
> http://en.wikipedia.org/wiki/Purely_functional#Examples_of_purely_functional_data_structures
>
> > Will using Hashtbls circumvent this problem?
>
> Hashtbls aren't persistent, and depending on your application that can
> be a good or bad thing. You'll probably want to benchmark the whole
> program to find out which it is. (In some circumstances you simply
> need to use a persistent structure to ease the programming).
>
> This book by Chris Okasaki is the canonical reference, albeit rather
> difficult to follow beyond the first few chaptes:
>
>
> http://www.amazon.com/Purely-Functional-Structures-Chris-Okasaki/dp/0521663504
>
> BTW, have you thought about using a single map which is keyed on
> (string, int) key?
>
> Rich.
>
> --
> Richard Jones
> Red Hat
>
>
>

[Non-text portions of this message have been removed]

•  2
  New Members