Seeking advice on memoizing

C

ctcgag

Michele Dondi said:
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
 
A

Anno Siegel

Michele Dondi said:
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
 
M

Michele Dondi

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
 
A

Anno Siegel

Michele Dondi said:
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
 
C

ctcgag

Michele Dondi said:
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
 
C

ctcgag

Michele Dondi said:
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
 
M

Michele Dondi

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
 
M

Michele Dondi

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
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,744
Messages
2,569,483
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top