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

[BrowserUk]

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( @_, [] ); }

[LanX]

yep just try to imagine what linearizing and short circuiting could achieve.

[BrowserUk]

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.

[LanX]

just intelligent looping, no need for tail-recursion.

Any recursion can be linearized.

Pushing and popping the @path array and/or %seen is all you need as a stack.

But I'm too lazy to do neversaints homework! :)