Re^2: Challenge: Perl 5: lazy sameFinge()?

Nice ... but I'm not really sure if this qualifies as lazy !?!

You are using many copies to flatten the stack.

with some dumps of intermediate @stack-states:

#!/usr/bin/perl
use strict;
no warnings ;

my $tree1 = [ [ [ 'a', 'b', ], 'c'],'d' ];
my $tree2 = [ ['a','b'],[ 'c','d' ] ];

my $ti1 = get_tree_iterator($tree1);
my $ti2 = get_tree_iterator($tree2);

my $cnt_mismatches=0;
while (1) {
    my ($L, $R) = ($ti1->(), $ti2->());
    print "L=$L, R=$R\n";
    die "--- not equal!" unless  ($R eq $L) or (!$L and !$R);
    last if !defined $L;
}
print $cnt_mismatches ? "$cnt_mismatches mismatches" : "TREES MATCH!",
+ "\n";

use Data::Dump 'dd';

sub get_tree_iterator {
    my @stack = (shift);
    return sub {
      print "---\n";
      dd \@stack;
      while (@stack and ref $stack[0] eq 'ARRAY') { 
    unshift @stack, @{shift @stack};
    dd \@stack
      }
      return shift @stack;
    }
}
[download]

out

---
[[[["a", "b"], "c"], "d"]]
[[["a", "b"], "c"], "d"]
[["a", "b"], "c", "d"]
["a", "b", "c", "d"]
---
[[["a", "b"], ["c", "d"]]]
[["a", "b"], ["c", "d"]]
["a", "b", ["c", "d"]]
L=a, R=a
---
["b", "c", "d"]
---
["b", ["c", "d"]]
L=b, R=b
---
["c", "d"]
---
[["c", "d"]]
["c", "d"]
L=c, R=c
---
["d"]
---
["d"]
L=d, R=d
---
[]
---
[]
L=, R=
[download]

Cheers Rolf

( addicted to the Perl Programming Language)

Comment on Re^2: Challenge: Perl 5: lazy sameFinge()? Select or Download Code

Replies are listed 'Best First'.
Re^3: Challenge: Perl 5: lazy sameFinge()? by roboticus (Chancellor) on Jun 29, 2013 at 20:59 UTC
LanX: They didn't specify where the laziness should be, so I let the programmer be lazy at the expense of the computer working hard! ...roboticus When your only tool is a hammer, all problems look like your thumb.	[reply]
Re^3: Challenge: Perl 5: lazy sameFinge()? by roboticus (Chancellor) on Jul 02, 2013 at 15:03 UTC
LanX: On rereading this thread, I think you may misunderstand what my code is doing. When you said that my code wasn't "lazy", I thought you meant that it was working too hard, but in retrospect I think you're meaning that I'm flattening the entire tree at once before returning anything. But I'm not doing that--Instead, I'm properly visiting the tree, traversing the left subtree(s) until I find the first (leftmost) leaf. The unused right subtrees are left on the stack for processing later. Since my test data was small and the tree left-heavy, though, it's hard to see that. Below (in readmore tags for those uninterested) is a run of the original iterator that you instrumented with a more "interesting" tree. I also have the output of my better version (also instrumented): Read more... (6 kB) ...roboticus When your only tool is a hammer, all problems look like your thumb.	[reply] [d/l] [select]
Re^4: Challenge: Perl 5: lazy sameFinge()? by LanX (Saint) on Jul 02, 2013 at 17:15 UTC
No no! I'm well aware that you are flattening the actual array only on demand. And as I said thats not expensive for binary trees. I'll qualify it as "half-lazy" if you want, b/c of the on-demand. IMHO, real lazy means no big-copies at all... (see requirements) Just imagine a non-binary tree like `[[1..1e8]]` then your algorithm would double the memory needed. Cheers Rolf ( addicted to the Perl Programming Language) PS: I wouldn't be surprized if your algorithm was faster than hdb's but with the advantage to be able to handle non-binary trees.	[reply] [d/l]