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.
-
Are you posting in the right place? Check out Where do I post X? to know for sure.
-
Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
<code> <a> <b> <big>
<blockquote> <br /> <dd>
<dl> <dt> <em> <font>
<h1> <h2> <h3> <h4>
<h5> <h6> <hr /> <i>
<li> <nbsp> <ol> <p>
<small> <strike> <strong>
<sub> <sup> <table>
<td> <th> <tr> <tt>
<u> <ul>
-
Snippets of code should be wrapped in
<code> tags not
<pre> tags. In fact, <pre>
tags should generally be avoided. If they must
be used, extreme care should be
taken to ensure that their contents do not
have long lines (<70 chars), in order to prevent
horizontal scrolling (and possible janitor
intervention).
-
Want more info? How to link
or How to display code and escape characters
are good places to start.