Beefy Boxes and Bandwidth Generously Provided by pair Networks
We don't bite newbies here... much
 
PerlMonks  

Re: Re: Better algorithm than brute-force stack for combinatorial problems? (Take 3 and homage to A::L)

by BrowserUk (Patriarch)
on May 22, 2004 at 10:50 UTC ( [id://355571]=note: print w/replies, xml ) Need Help??


in reply to Re: Better algorithm than brute-force stack for combinatorial problems? (A::L)
in thread Better algorithm than brute-force stack for combinatorial problems?

My hat's of to you Sir! That is very, very cool code.

At take 3, I managed to get your benchmark (30/1..20) down to under 1 second (675 ms) and with less than 10 MB with a new version and Memoize, but... for 40/1..20 I was up to 11s/98MB whereas your's did it in under half a second and 3 MB, even with the addition of accumulating the results in an AoA rather than printing them direct.

My (pretty worthless) take 3 code

#! perl -slw use strict; use Memoize; use Benchmark::Timer; use List::Util qw[ sum ]; $|=1; BEGIN{ @ARGV = map{ eval } @ARGV } sub sums{ INIT{ memoize( 'sums' ); } my $total = shift; return unless @_ or $total > 1; return $_[ 0 ] == $total ? $_[ 0 ]: () if @_ == 1; my @list; for my $i ( 0 .. $#_ ) { my $next = $_[ $i ]; my $newTotal = $total - $next; for my $partial ( sums( $newTotal, grep $_ <= $newTotal, @_[ grep $_ != $i, 0 .. $# +_ ] ) ) { next unless $partial and sum( split ' ', $partial ) == $newTotal; push @list, "$next $partial"; } } return @list; } my( $total, @list ) = ( shift @ARGV, @ARGV ); my $T = new Benchmark::Timer; $T->start( 'memoized' ); my @sums3 = sums( $total, sort{ $b <=> $a } @ARGV ); $T->stop( 'memoized' ); $T->report; <STDIN>; __END__ P:\test>355455-3 30 1..20 1 trial of memoized (675.107ms total) P:\test>355455-3 40 1..20 1 trial of memoized (11.674s total)

The only problem I have (with the emphasis on I), is that even with the benefit of your commented code, I'm still not entirely sure that I understand how it works. I am certainly sure that I would not have been able to come up with the code (for this problem using Algorithm::Loops) myself.

(FWIW) I've long been impressed by (your examples of using) A::L, I just can't wrap my brain around how to use it for non-trivial tasks like this.

Off to re-read the documentation for the umpteenth time in the hope that something will click.


Examine what is said, not who speaks.
"Efficiency is intelligent laziness." -David Dunham
"Think for yourself!" - Abigail
  • Comment on Re: Re: Better algorithm than brute-force stack for combinatorial problems? (Take 3 and homage to A::L)
  • Download Code

Replies are listed 'Best First'.
Re^3: Better algorithm than brute-force stack for combinatorial problems? (explain)
by tye (Sage) on May 22, 2004 at 19:52 UTC

    The first argument to NestedLoops is the list of loops so

    [ # First loop: all item indices [ 0..$#items ], # @items-1 subsequent loops: ( sub { # If we need more items: $sum[@_] < $target # then get more (unique) item indices ? [ ($_+1)..$#items ] # else don't get more items : [] } ) x $#items, ],

    becomes the equivalent of

    for $_ ( 0..$#items ) { # ... for $_ ( @{ $sum[@_] < $target ? [ ($_+1)..$#items ] : [] } ) { # ... for $_ ( @{ $sum[@_] < $target ? [ ($_+1)..$#items ] : [] } ) { # ... } } }

    The sub { ... } in the original code is required to delay the running of the loop computation code instead of running it before NestedLoops is called (at which point $_ and other variables wouldn't contain the rigth values).

    The list of items computed by the nested loops is passed to the subs as @_ and the currently innermost loop's variable is also put into $_ so you can use that as short-hand for $_[-1].

    And this bit

    OnlyWhen => sub { # Compute sum of selected items as # sum of @_-1 items plus last item: $sum[@_]= $sum[$#_] + $items[$_[-1]]; # Return subsets that match desired sum: return $sum[@_] == $target; },

    just declares a sub that gets called to determine which lists to return. We'll pretend it is named when() below. And we'll replace the @_ in each $sum[@_] with a hard-coded value to simplify our 'translation' which becomes something close to:

    @_= (); for $_ ( 0..$#items ) { push @_, $_; push @return, [ @_ ] if when( @_ ); for $_ ( @{ $sum[1] < $target ? [ ($_+1)..$#items ] : [] } ) { push @_, $_; push @return, [ @_ ] if when( @_ ); for $_ ( @{ $sum[2] < $target ? [ ($_+1)..$#items ] : [] } ) { push @_, $_; push @return, [ @_ ] if when( @_ ); # ... pop @_; } pop @_; } pop @_; }

    But instead of pushing each selected list into @return, each call to $iter->() returns the next list that would be pushed.

    Note that we loop over indices so we can use ($_+1)..$#items to only loop over indices that we haven't already looped over.

    Let's simplify the inner loops. The point of

    $sum[@_] < $target ? [ ($_+1)..$#items ] : []

    is to avoid looping any deeper if we don't need more items to add up (because we've already reached our desired total). Which can be more clearly written in our translation as

    next if $target <= $sum[@_];

    (if we do our pops in continue blocks) so we can clarify our example to

    @_= (); for $_ ( 0..$#items ) { push @_, $_; push @return, [ @_ ] if when( @_ ); next if $target <= $sum[1]; for $_ ( ($_+1)..$#items ) { push @_, $_; push @return, [ @_ ] if when( @_ ); next if $target <= $sum[2]; for $_ ( ($_+1)..$#items ) { push @_, $_; push @return, [ @_ ] if when( @_ ); # ... } continue { pop @_; } } continue { pop @_; } } continue { pop @_; }

    Of course, we can't finish this translation because you can't write loops that nest to some arbitrary depth.

    Fiinally, we use the iterator to get each desired set of indices. We use an array slice to convert the list of indices into a list of iitems:

    while( my @list= @items[ $iter->() ] ) { warn "$target = sum( @list )\n"; }

    I hope that helps explain how this works.

    - tye        

      Thanks. It'll probably take a few more readings to take that all in, but on the surface it makes (more) sense to me now. I think I was part way there with understanding the calling syntax and general methodology of the algorithm, but this clarifies it.

      The main problem I was commenting upon though is subtly different from understanding how to use NestedLoops. It's more a case of wrapping my brain around how to apply it to any given problem. I guess it is really no more complicated that coding a recursive routine and remembering that each piece of code will be run at all levels, but I've been doing recursion long enough that it has become second nature to think that way. This is like recursion, but different; and without the overhead.

      The subtly seems to be to the $sum[ @_ ] = ... bit. It took this post for me to realise that @sum isn't really an array in terms of the algorithm (the absence of the postfix 's' would be a clue if you normally hold to that convention). It's really a stack of autovivified, level-specific, persistant 'local' storage. (I think!).

      I stuck a print "@sum\n"; before the return in the OnlyWhen routine and it's interesting to watch the values iterate.

      This definitely requires a good "cookbook" article (or book?) to stimulate exploration of it's uses and algorithms. If you have the time TPJ were asking for authors:)


      Examine what is said, not who speaks.
      "Efficiency is intelligent laziness." -David Dunham
      "Think for yourself!" - Abigail
        The main problem I was commenting upon though is subtly different from understanding how to use NestedLoops.

        Yes. I'd hoped my explanation might still help with the other problem (and help others understand the code)...

        It's more a case of wrapping my brain around how to apply it to any given problem. I guess it is really no more complicated that coding a recursive routine and remembering [...]

        Yeah, that certainly sounds like a difficult way to go about it. Instead, think of writing foreach loops. Does that help much? I could elaborate but I'd rather do that based on your response. I could go into how to write foreach loops but maybe that isn't something you need elaboration on. (:

        - tye        

A::L::NestedLoops walkthrough (was Re^3: Better algorithm than brute-force stack for combinatorial problems?)
by Solo (Deacon) on May 22, 2004 at 15:33 UTC
    I agree BrowserUK. ++tye for an incredible module! I missed the original discussions of A::L last year, but went back and read most of them last night after completely failing to understand the source for NestedLoops()! The prior posts were no help, so this is how I grok'd his code eventually.

    I knew tye's approach was based on a closure as an iterator. Allright, I understand that, so I'll take what I understand and try to build it up to what NestedLoops() does...

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://355571]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others taking refuge in the Monastery: (4)
As of 2024-05-18 15:48 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found