in reply to Re: Scoping problems in nested loops
in thread Scoping problems in nested loops

Thanks. That looks really great.

I've been playing with it, and I did hit one snag so far. The arrays sotred in @{$matches{$element}{$sitekey}} contain possibly millions of elements, all stored in numerical order. If we assume that the ones being pushed into @arrayA are going to number a dozen or less, it seems really wasteful to me to sift through the entire array, for instance, once you've already reached values >= $upperlimit.

This is why I had included some of the early loop exits and so on. It will (presumaby) greatly increase the speed of the program, which is highly desirable. What are your thoughts on modifying your code here:

for my $hElem (@{$matches{$element}{$sitekey}}) {
    print "...in \$hElem\n";
    if ($hElem >= $lowerlimit && $hElem <= $upperlimit) {
        push (@arrayA, $hElem);
        }
    }

[download]
To something along these lines instead? :

for my $hElem (@{$matches{$element}{$sitekey}}) {
    next unless ($hElem >= $lowerlimit);
    break unless ($hElem <= $upperlimit);
    print "...in \$hElem\n"   
    push (@arrayA, $hElem);
    }

[download]
Thanks,
Matt

Replies are listed 'Best First'.
Re^3: Scoping problems in nested loops
by GrandFather (Saint) on Nov 15, 2006 at 18:48 UTC

    The loop with early exit looks fine. However if there are large numbers of elements and the range represents a small fraction of the total number of elements, then I'd be inclined to do a binary search for the two end elements in the range and use an array slice to copy the elements in the range out. You may find Binary search helps as a starting point for the search code.

    Given two end element indexes the following does the slice and copy:

    @arrayA = @{$matches{$element}{$sitekey}}[$first .. $last];

    [download]
    DWIM is Perl's answer to Gödel
[reply]
[d/l]
      OK, I think I see where you're going with that but....

      I don't have the indices of the array elements, I would just have the values. And I am under the impression that slicing only works when you have the indices, not the values. Besides, if I am looking for any $x where
      $x <= $upperlimit && $x >= $lowerlimit
      I don't actually know that $upperlimit corresponds to a value in the array.

      So, I'm not sure that that accomplishes what you think it does.

      Also, as for my early exits, I realized break was the wrong command, and last seems to be doing the trick I wanted..

      Thanks,
      Matt

[reply]
[d/l]

        Consider this example code:

        use strict;
use warnings;

my @bigarray = ( # Think @{$matches{$element}{$sitekey}}
    1 .. 15, 21 .. 100, 200 .. 2000, 2010 .. 2015
    );

test (1, 12);
test (10, 20);
test (18, 25);
test (2000, 3000);


sub test {
    my $lowIndex = BinSearch ($_[0], \&cmpFunc, \@bigarray) + 0.5;
    my $highIndex = BinSearch ($_[1], \&cmpFunc, \@bigarray);
    my @arrayA = @bigarray[$lowIndex..$highIndex];
    
    print "$_[0] - $_[1]: [$lowIndex .. $highIndex]: @arrayA\n";
}


sub cmpFunc {
    $_[0] <=> $_[1];
}


sub BinSearch {
    my ($target, $cmp, $array) = @_;
    my $posmin = 0;
    my $posmax = $#$array;
    
    return -0.5 if $cmp->($array->[0], $target) > 0;
    return $#$array + 0.5 if &$cmp ($array->[-1], $target) < 0;
    
    while (1) {
        my $mid = int (($posmin + $posmax) / 2);
        my $result = $cmp->($array->[$mid], $target);
        
        if ($result < 0) {
            $posmin = $posmax, next if $mid == $posmin && $posmax != $
+posmin;
            return $mid + 0.5 if $mid == $posmin;
            $posmin = $mid;
        } elsif ($result > 0) {
            $posmax = $posmin, next if $mid == $posmax && $posmax != $
+posmin;
            return $mid - 0.5 if $mid == $posmax;
            $posmax = $mid;
        } else {
            return $mid;
        }
    }
}

        [download]

        Prints:

        1 - 12: [0 .. 11]: 1 2 3 4 5 6 7 8 9 10 11 12
10 - 20: [9 .. 14.5]: 10 11 12 13 14 15
18 - 25: [15 .. 19]: 21 22 23 24 25
2000 - 3000: [1895 .. 1901.5]: 2000 2010 2011 2012 2013 2014 2015

        [download]

        In your context you would do something like:

        my $lowIndex = BinSearch ($lowerlimit, sub {$_[0] <=> $_[1]}, $matches
+{$element}{$sitekey}) + 0.5;
my $highIndex = BinSearch ($upperlimit, sub {$_[0] <=> $_[1]}, $matche
+s{$element}{$sitekey});
my @arrayA = @{$matches{$element}{$sitekey}}[$lowIndex..$highIndex];

        [download]
        DWIM is Perl's answer to Gödel
[reply]
[d/l]
[select]

In Section Seekers of Perl Wisdom