Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Perl > Perl Misc > Seeking advice on memoizing

Reply
Thread Tools

Seeking advice on memoizing

 
 
ctcgag@hotmail.com
Guest
Posts: n/a
 
      01-26-2004
Michele Dondi <(E-Mail Removed)> wrote:
> I'm writing a script to do a few arithmetic computations. The code is
> highly factorized in small subs and I'd like to do some "manual"
> memoizing, i.e. not using the Memoize module of which I'm aware.
>
> FWIW *one* of the reasons why I do not want to use Memoize is that
> values to be cached (1) are not the return values of the subs, (2)
> they can be "produced" by different subs.


So then couldn't they be pulled into a sub sub which is used by the all
the subs?


> The data to be saved correspond to couples of integers $a, $b with
> $a<$b and the question is: should I store them in a hash indexed, say,
> by keys like $a.','.$b or in an AoA? Is there any advantage of one
> method over the other?


What are the legal bounds on $a and $b, and how dense do you expect the
memoized data to get? If the number that will actually be stored is sparce
WRT the number of legal pairs, that would favor hashes. If the number
stored is dense WRT all legal pairs, that would favor arrays.

(If you use AoA, it should be $mem[$b][$a], not $mem[$a][$b])

Xho

--
-------------------- http://NewsReader.Com/ --------------------
Usenet Newsgroup Service New Rate! $9.95/Month 50GB
 
Reply With Quote
 
 
 
 
Anno Siegel
Guest
Posts: n/a
 
      01-26-2004
<(E-Mail Removed)> wrote in comp.lang.perl.misc:
> Michele Dondi <(E-Mail Removed)> wrote:
> > I'm writing a script to do a few arithmetic computations. The code is
> > highly factorized in small subs and I'd like to do some "manual"
> > memoizing, i.e. not using the Memoize module of which I'm aware.
> >
> > FWIW *one* of the reasons why I do not want to use Memoize is that
> > values to be cached (1) are not the return values of the subs, (2)
> > they can be "produced" by different subs.

>
> So then couldn't they be pulled into a sub sub which is used by the all
> the subs?
>
>
> > The data to be saved correspond to couples of integers $a, $b with
> > $a<$b and the question is: should I store them in a hash indexed, say,
> > by keys like $a.','.$b or in an AoA? Is there any advantage of one
> > method over the other?

>
> What are the legal bounds on $a and $b, and how dense do you expect the
> memoized data to get? If the number that will actually be stored is sparce
> WRT the number of legal pairs, that would favor hashes. If the number
> stored is dense WRT all legal pairs, that would favor arrays.
>
> (If you use AoA, it should be $mem[$b][$a], not $mem[$a][$b])


A naive approach would simply use a HoH. That takes (some) advantage of
sparse data and gives you convenient access (well, as convenient as it
gets). Think of something else when that approach turns out to be too
simplistic.

A variant of the original hash method might use Perl's simulated multi-
dimensional arrays of yore. $hash{ $a, $b, ...} is interpreted as
$hash{ join $", $a, $b, ...}. That puts the necessary join() and split()
of this approach out of the way.

Anno
 
Reply With Quote
 
 
 
 
Michele Dondi
Guest
Posts: n/a
 
      01-27-2004
I'm writing a script to do a few arithmetic computations. The code is
highly factorized in small subs and I'd like to do some "manual"
memoizing, i.e. not using the Memoize module of which I'm aware.

FWIW *one* of the reasons why I do not want to use Memoize is that
values to be cached (1) are not the return values of the subs, (2)
they can be "produced" by different subs.

The data to be saved correspond to couples of integers $a, $b with
$a<$b and the question is: should I store them in a hash indexed, say,
by keys like $a.','.$b or in an AoA? Is there any advantage of one
method over the other?


TIA,
Michele
 
Reply With Quote
 
Anno Siegel
Guest
Posts: n/a
 
      01-27-2004
Michele Dondi <(E-Mail Removed)> wrote in comp.lang.perl.misc:
> On 26 Jan 2004 19:25:52 GMT, http://www.velocityreviews.com/forums/(E-Mail Removed)-berlin.de (Anno
> Siegel) wrote:
>
> >A variant of the original hash method might use Perl's simulated multi-
> >dimensional arrays of yore. $hash{ $a, $b, ...} is interpreted as
> >$hash{ join $", $a, $b, ...}. That puts the necessary join() and split()
> >of this approach out of the way.

>
> I knew this feature. Always resisted the temptation to use it because
> I've always been told that the Good Thing(TM) is to use "real"
> multidimensional hashes, which sounds reasonable, of course.


Apart from the restriction in key space that comes with key concatenation,
it's a space/time tradeoff. The time spent in joining and splitting keys
may be immeasurable with the built_in method (I don't know), but it won't be
if you do it explicitly. On the other hand, the multiple anonymous hashes
in a HoH consume quite a bit of memory.

> I think it is a typo you wrote $", though. It is $; in fact!


Indeed. Before I posted I was smugly self-satisfied I had remembered it
right this time, down to the bizarre mnemonic "A comma is a semi-semicolon",
instead of having to look it up to be sure. How I got it wrong again is
beyond me, but so much for smug self-satisfaction...

Anno
 
Reply With Quote
 
ctcgag@hotmail.com
Guest
Posts: n/a
 
      01-27-2004
Michele Dondi <(E-Mail Removed)> wrote:
> >
> >What are the legal bounds on $a and $b, and how dense do you expect the
> >memoized data to get? If the number that will actually be stored is
> >sparce WRT the number of legal pairs, that would favor hashes. If the
> >number stored is dense WRT all legal pairs, that would favor arrays.
> >
> >(If you use AoA, it should be $mem[$b][$a], not $mem[$a][$b])

>
> I'd say "dense", so I'm favoring the AoA approach. I'll do some tests,
> anyway.
>
> BTW: Would I gain something by preassigning to $#{$mem[$b]}?


I've tried that type of pre-allocation before, and have never seen a
meaningful improvement (in speed).

Cheers,

Xho

--
-------------------- http://NewsReader.Com/ --------------------
Usenet Newsgroup Service New Rate! $9.95/Month 50GB
 
Reply With Quote
 
ctcgag@hotmail.com
Guest
Posts: n/a
 
      01-27-2004
(E-Mail Removed)-berlin.de (Anno Siegel) wrote:
> <(E-Mail Removed)> wrote in comp.lang.perl.misc:
> > Michele Dondi <(E-Mail Removed)> wrote:
> > > I'm writing a script to do a few arithmetic computations. The code is
> > > highly factorized in small subs and I'd like to do some "manual"
> > > memoizing, i.e. not using the Memoize module of which I'm aware.
> > >
> > > FWIW *one* of the reasons why I do not want to use Memoize is that
> > > values to be cached (1) are not the return values of the subs, (2)
> > > they can be "produced" by different subs.

> >
> > So then couldn't they be pulled into a sub sub which is used by the all
> > the subs?
> >
> >
> > > The data to be saved correspond to couples of integers $a, $b with
> > > $a<$b and the question is: should I store them in a hash indexed,
> > > say, by keys like $a.','.$b or in an AoA? Is there any advantage of
> > > one method over the other?

> >
> > What are the legal bounds on $a and $b, and how dense do you expect the
> > memoized data to get? If the number that will actually be stored is
> > sparce WRT the number of legal pairs, that would favor hashes. If the
> > number stored is dense WRT all legal pairs, that would favor arrays.
> >
> > (If you use AoA, it should be $mem[$b][$a], not $mem[$a][$b])

>
> A naive approach would simply use a HoH. That takes (some) advantage of
> sparse data and gives you convenient access (well, as convenient as it
> gets). Think of something else when that approach turns out to be too
> simplistic.


I agree that that is the most natural way to do it, and would
be my first choice for an ordinary script. I'd only go with the others
if I were pushing the limits of space and/or time, which I assumed (perhaps
without warrant) that the OP was.

Xho

--
-------------------- http://NewsReader.Com/ --------------------
Usenet Newsgroup Service New Rate! $9.95/Month 50GB
 
Reply With Quote
 
Michele Dondi
Guest
Posts: n/a
 
      01-28-2004
On 26 Jan 2004 19:01:45 GMT, http://www.velocityreviews.com/forums/(E-Mail Removed) wrote:

>> FWIW *one* of the reasons why I do not want to use Memoize is that
>> values to be cached (1) are not the return values of the subs, (2)
>> they can be "produced" by different subs.

>
>So then couldn't they be pulled into a sub sub which is used by the all
>the subs?


Oh yes, I'm actually using an accessory sub, but data are produced by
(slightly) different means, even though in a consistent way, in
different subs.

>> The data to be saved correspond to couples of integers $a, $b with
>> $a<$b and the question is: should I store them in a hash indexed, say,
>> by keys like $a.','.$b or in an AoA? Is there any advantage of one
>> method over the other?

>
>What are the legal bounds on $a and $b, and how dense do you expect the
>memoized data to get? If the number that will actually be stored is sparce
>WRT the number of legal pairs, that would favor hashes. If the number
>stored is dense WRT all legal pairs, that would favor arrays.
>
>(If you use AoA, it should be $mem[$b][$a], not $mem[$a][$b])


I'd say "dense", so I'm favoring the AoA approach. I'll do some tests,
anyway.

BTW: Would I gain something by preassigning to $#{$mem[$b]}?


Thanks
--
you'll see that it shouldn't be so. AND, the writting as usuall is
fantastic incompetent. To illustrate, i quote:
- Xah Lee trolling on clpmisc,
"perl bug File::Basename and Perl's nature"
 
Reply With Quote
 
Michele Dondi
Guest
Posts: n/a
 
      01-28-2004
On 26 Jan 2004 19:25:52 GMT, (E-Mail Removed)-berlin.de (Anno
Siegel) wrote:

>A variant of the original hash method might use Perl's simulated multi-
>dimensional arrays of yore. $hash{ $a, $b, ...} is interpreted as
>$hash{ join $", $a, $b, ...}. That puts the necessary join() and split()
>of this approach out of the way.


I knew this feature. Always resisted the temptation to use it because
I've always been told that the Good Thing(TM) is to use "real"
multidimensional hashes, which sounds reasonable, of course.

I think it is a typo you wrote $", though. It is $; in fact!


Thanks,
Michele
--
you'll see that it shouldn't be so. AND, the writting as usuall is
fantastic incompetent. To illustrate, i quote:
- Xah Lee trolling on clpmisc,
"perl bug File::Basename and Perl's nature"
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
why memoizing is faster Andrea Crotti Python 0 03-24-2011 01:48 PM
Memoizing and WeakValueDictionary Paul McGuire Python 1 01-04-2009 11:59 AM
weakref and memoizing bearophileHUGS@lycos.com Python 0 01-20-2006 12:01 AM
Memoizing decorator Daishi Harada Python 6 12-08-2005 01:37 AM
Memoizing Generators Mark Python 2 07-09-2003 02:19 PM



Advertisments