Beefy Boxes and Bandwidth Generously Provided by pair Networks
good chemistry is complicated,
and a little bit messy -LW
 
PerlMonks  

comment on

( [id://3333]=superdoc: print w/replies, xml ) Need Help??
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.

In reply to Eliminating Recursive Tree Walking by using MJD-style Infinite Streams? by jryan

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":



  • 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.
Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others admiring the Monastery: (5)
As of 2024-03-28 17:09 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found