Seeking advice on memoizing

Discussion in 'Perl Misc' started by ctcgag@hotmail.com, Jan 26, 2004.

  1. Guest

    Michele Dondi <> 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
    , Jan 26, 2004
    #1
    1. Advertising

  2. Anno Siegel Guest

    <> wrote in comp.lang.perl.misc:
    > Michele Dondi <> 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
    Anno Siegel, Jan 26, 2004
    #2
    1. Advertising

  3. 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
    Michele Dondi, Jan 27, 2004
    #3
  4. Anno Siegel Guest

    Michele Dondi <> wrote in comp.lang.perl.misc:
    > On 26 Jan 2004 19:25:52 GMT, -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
    Anno Siegel, Jan 27, 2004
    #4
  5. Guest

    Michele Dondi <> 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
    , Jan 27, 2004
    #5
  6. Guest

    -berlin.de (Anno Siegel) wrote:
    > <> wrote in comp.lang.perl.misc:
    > > Michele Dondi <> 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
    , Jan 27, 2004
    #6
  7. On 26 Jan 2004 19:01:45 GMT, 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"
    Michele Dondi, Jan 28, 2004
    #7
  8. On 26 Jan 2004 19:25:52 GMT, -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"
    Michele Dondi, Jan 28, 2004
    #8
    1. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Mark

    Memoizing Generators

    Mark, Jul 8, 2003, in forum: Python
    Replies:
    2
    Views:
    325
  2. Daishi  Harada

    Memoizing decorator

    Daishi Harada, Dec 6, 2005, in forum: Python
    Replies:
    6
    Views:
    403
    Daishi Harada
    Dec 8, 2005
  3. weakref and memoizing

    , Jan 20, 2006, in forum: Python
    Replies:
    0
    Views:
    362
  4. Paul McGuire

    Memoizing and WeakValueDictionary

    Paul McGuire, Jan 4, 2009, in forum: Python
    Replies:
    1
    Views:
    310
  5. Andrea Crotti

    why memoizing is faster

    Andrea Crotti, Mar 24, 2011, in forum: Python
    Replies:
    0
    Views:
    172
    Andrea Crotti
    Mar 24, 2011
Loading...

Share This Page