Re^3: Searching parallel arrays.

BrowserUk,
I haven't had a chance to optimize this or even to test it thoroughly but I wanted to share. It is commented but if you need further explanation, please don't hesitate.

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

my @aoa = ([100, 204, 312], [102, 313, 409], [205, 206, 315], [207, 21
+0, 314]);
my $next = gen_find_contiguous(4, \@aoa);
while (my @seq = $next->()) {
    print "Val: $_->[0]\tArr: $_->[1]\tPos: $_->[2]\n" for @seq;
    print "\n";
}
sub gen_find_contiguous {
    my ($min, $list) = @_;
    my @pos = (0) x @$list;
    return sub {
        my $found;
        my @cont;
        while (! $found) {
            # Find smallest value keeping track of array and index in 
+that array
            my ($arr, $val, $idx);
            for (grep defined($pos[$_]), 0 .. $#pos) {
                if (! defined $arr || $list->[$_][$pos[$_]] < $val) {
                    ($arr, $val, $idx) = ($_, $list->[$_][$pos[$_]], $
+pos[$_]);
                }
            }
            # Check to see if we are at the end of all arrays
            if (! defined $arr) {
                return @cont >= $min ? @cont : ();
            }
            # Add value to cont if empty
            if (! @cont) {
                push @cont, [$val, $arr, $idx];
            }
            else {
                # Add value to cont if it 1 away from prev value
                if ($val - $cont[-1][0] == 1) {
                    push @cont, [$val, $arr, $idx];
                }
                else {
                    # If @cont >= $min, set found flag
                    if (@cont >= $min) {
                        $found = 1;
                    }
                    # Else start over
                    else {
                        @cont = [$val, $arr, $idx];
                    }
                }
            }
            # Increment index of array we fetched value from if ! $fou
+nd
            if (! $found) {
                $pos[$arr] = $idx == $#{$list->[$arr]}
                    ? undef
                    : $idx + 1;
            }
        }
        return @cont;
    };
}
[download]

I didn't use List::Util's reduce() because apparently it can handle multiple return values. The docs (Returns the result of the last call to BLOCK.) should probably be clarified on this point

Cheers - L~R

Comment on Re^3: Searching parallel arrays. Download Code

Replies are listed 'Best First'.
Re^4: Searching parallel arrays. by BrowserUk (Patriarch) on Dec 09, 2006 at 02:12 UTC
Nice++ I like that you've made it an iterator. I'll do some comparisons with mine and one of the sort them together solutions and see what's what as far as efficiency is concerned. I didn't use List::Util's reduce() because apparently it can['t] handle multiple return values. I guess it's pretty much the nature of the beast that `reduce` can only handle one return value as it becomes `$a` for the next iteration. However, I have worked around this in the past by using an anonmous array. `@data = map int( rand 100 ), 1.. 100; $max = ( reduce{ $a->[0] > $b ? $a : ( $a->[0] = $b, $a ) } [0], @data )->[0]; print $max;; 96` [download] Of course that's a useless use of the technique, but it demonstrates it and you can put anything else inside the anon array that you need to carry around. `reduce` is biggest discovery from playing with functional languages. I find it, and it's named variants just so useful. I really think that it deserves inclusion directly into the langauge--which would be possible for 5.10 now they've added support for adding new stuff into core. I'm also hoping for great things as far as the efficiency of function calls goes in 5.10, which I read somewhere was going to be improved--but I cannot now find where. It might make functional composition ala tmortel's meditations, and HOP efficient enough to be usable for something other than interestign demonstrations. Did you here anything about this? I'll probably communicate the finding of whatever benchmarking I do offline if your interested, unless someone else reading this speaks up and asks me to post it. Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error. Lingua non convalesco, consenesco et abolesco. -- Rule 1 has a caveat! -- Who broke the cabal? "Science is about questioning the status quo. Questioning authority". In the absence of evidence, opinion is indistinguishable from prejudice.	[reply] [d/l] [select]
Re^5: Searching parallel arrays. by Limbic~Region (Chancellor) on Dec 09, 2006 at 02:42 UTC
BrowserUk, I had originally always intended it to be an iterator but it would have made describing the algorithm more difficult. I made no effort at optimization so it can probably be improved greatly. I have submitted a bug report on List::Util indicating that the documentation should be explicit about the single return value or the implementation should be changed. I suspect you are right and the fix is a doc update. I have read through the perldeltas for 5.9.0 - 5.9.4 and did not see anything regarding sub call speedups. I am interested in Benchmark results using real data. One optimization could be made by only handling 4 arrays and using a hardcode @cont of 4 instead of both being user defined. You mentioned earlier not understanding tye's Algorithm::Loops. I won't pretend to understand his code either but I do understand the methodology. If you haven't seen Arbitrarily Nested Loops and NestedLoops and the Odometer Model, they may help explain it. Cheers - L~R	[reply]