Beefy Boxes and Bandwidth Generously Provided by pair Networks
Problems? Is your data what you think it is?
 
PerlMonks  

Re^11: Finding All Paths From a Graph From a Given Source and End Node

by LanX (Cardinal)
on Nov 02, 2010 at 18:58 UTC ( #869069=note: print w/replies, xml ) Need Help??


in reply to Re^10: Finding All Paths From a Graph From a Given Source and End Node
in thread Finding All Paths From a Graph From a Given Source and End Node

And the culprit was ... usage of self-documenting variable names.

Simply avoiding the array-copy my @path=@_ makes a factor 4.5 performance boost...

Fascinating!!! What a pity Perl doesn't support aliasing out of the box!

{ my %seen; sub track { my $last=$_[-1]; $seen{$last}=1; for my $next (@{$graph{$last}}) { next if $seen{$next}; if ($next eq $stop) { #print join ("->",@_,$stop),"\n"; $anzahl++; print "$anzahl at ",time-$time0,"\n" if $anzahl%10000==0; } else { track(@_,$next); } } delete $seen{$last}; } }

Cheers Rolf

Replies are listed 'Best First'.
Re^12: Finding All Paths From a Graph From a Given Source and End Node
by BrowserUk (Pope) on Nov 02, 2010 at 19:43 UTC
    Simply avoiding the array-copy my @path=@_ makes a factor 4.5 performance boost...

    Wow. I'm amazed that avoiding the copying of such a small array had such a dramatic affect on the performance. I guess it must be being copied very many times.

    In mine, I tried building the hash from the array rather than carrying it around, and it produced an ~8% speed-up. Then I tried using $_[n] instead of named parameters and it leached less than 5% more. The first is worth having, the second not:

    sub _findPaths3 { return $_[0]->( @{ $_[4] }, $_[3] ) if $_[2] eq $_[3]; my %seen; $seen{ $_ } = 1 for @{ $_[4] }, $_[2]; for ( grep !$seen{ $_ }, @{ $_[1]->{ $_[2] } } ) { _findPaths3( $_[0], $_[1], $_, $_[3], [ @{ $_[4] }, $_[2] ] ), } } sub findPaths3(&@) { _findPaths3( @_, [] ); }

    Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
    "Science is about questioning the status quo. Questioning authority".
    In the absence of evidence, opinion is indistinguishable from prejudice.
      yep just try to imagine what linearizing and short circuiting could achieve.

      Cheers Rolf

        try to imagine what linearizing and short circuiting could achieve.

        Hm. Seeing's believing :) But I'm not really sure what you mean by "linearizing" in this context?

        If you mean brute-forcing the recursion to iteration using manual stack handling, that often works out more costly than the recusion it is trying to eliminate.

        If the recursion can be eliminated through tail-recursion, that's very effective in languages that support it. (Properly; goto \&recurse is usually slower).

        But I'm pretty sure this can't be written to be tail-recursive.

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others scrutinizing the Monastery: (6)
As of 2021-01-21 07:48 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    Notices?