http://qs321.pair.com?node_id=692364

jryan has asked for the wisdom of the Perl Monks concerning the following question:

So, I've got this recursive subroutine, follow_paths, that walks a tree:
sub follow_paths { my ($x_s,$y_s,$s_s,$paths,$regs) = @_; my $branches = $paths->[$x_s][$y_s][$s_s]; unless (defined $branches) { # pad endpoint (base case)} return [[[$x_s,$y_s,$s_s,'pad']]]; } if (exists $regs->{$x_s}{$y_s}{$s_s}) { # register endpoint (base case) return [[[$x_s,$y_s,$s_s,'reg']]]; } my @current; foreach my $branch (@$branches) { my $branch_paths = follow_paths(@$branch,$paths,$regs); push @current, map { unshift @$_, [$x_s,$y_s,$s_s]; $_ } @$branch_paths; } return \@current; }
$paths is the tree structure we're walking; key in the coordinates for a node ($x,$y,$s) and you'll get a list of other nodes that the current node links to. $paths is pulled out of a file generated by another program. The whole point of follow_paths is to produced a list of linearized paths from the source (the initial $x,$y,$s) to the sinks (either a pad or a register). This linearized interface is needed by another part of this program that does a bunch of analysis on the paths. For instance, if a relevant subset of our paths and regs looked like this:
regs = 1,0,0 paths = 0,0,0 => 3,0,0 0,1,0 => 0,2,0 1,0,0 => 0,3,0 3,0,0 => 0,1,0 1,0,0
then the result of follow_paths(0,0,0,$paths,$regs) should produce:
[[3,0,0] [0,1,0] [0,2,0,'pad'] ], [[3,0,0] [1,0,0,'reg'] ]
And you know what? It does do that. It does it perfectly. Except when the paths are so deep that it hits deep recursion and then runs out of memory. :( My first thought to fix this was to apply MJD's general recursion-unrolling technique from his book Higher Order Perl. I came up with this:
sub follow_paths_unrolled { my ($x_s,$y_s,$s_s,$paths,$regs) = @_; my $cur_x = $x_s; my $cur_y = $y_s; my $cur_s = $s_s; my $index = 0; my $current = []; my @STACK; my $RETURN; my $BRANCH = 0; NEWCALL: while(1) { my $branches = $paths->[$cur_x][$cur_y][$cur_s]; if (not defined $branches) { # pad endpoint (base case)} $RETURN = [[[$x_s,$y_s,$s_s,'pad']]]; } elsif (exists $regs->{$x_s}{$y_s}{$s_s}) { # register endpoint (base case) $RETURN = [[[$x_s,$y_s,$s_s,'reg']]]; } else { for (my $i=$index; $i < @$branches; $i++) { if ($BRANCH == 0) { my $branch = $branches->[$i]; # push @STACK $BRANCH = 1; push @STACK, [$cur_x,$cur_y,$cur_s,$i,$current,$BR +ANCH]; # set new values ($cur_x,$cur_y,$cur_s) = @$branch; $index = 0; $current = []; $BRANCH = 0; next NEWCALL; } else { my $branch_paths = $RETURN; push @$current, map { unshift @$_, [$cur_x,$cur_y, +$cur_s]; $_ } @$branch_paths; $BRANCH = 0; } } $RETURN = $current; } return $RETURN unless @STACK; ($cur_x,$cur_y,$cur_s,$index,$current,$BRANCH) = @{pop @STACK} +; } }
That does indeed eliminate the warnings for deep recursion, but obviously (in hindsight) does nothing to fix the out-of-memory error. So, what I think I need now is some sort of way to apply another concept from his book, infinite streams, to my tree-walking problem. I suppose that it should have two parts: A stream that would return an iterator to each path. I have not, unfortunately, a fucking clue on how to go about doing this. Have any of y'all tried this sort of thing before? Edit: Added readmore code.