in reply to Optimizing a double loop

The best way to speed up this loop is not to execute it.

Yes, I'm serious. Depending on your actual problem, there might be a way around it.

If you read abut inversion lists, you find that this idea can be generalized to overlapping lists.

Assume you have the ranges 10-50 and 20-100; You mark each start of a range with a positive number, and each end of range by a negative number. So 1-50 and 20-100 would translate to 

[1, 20, -50, -100]

[download]

That way you only store two integers for a large range.

If you want to know how many ranges overlap at a given point, say at 30, you just traverse the array from left to right up to abs($_) <= 30, and count how many positive and how many negative numbers you have encountered; the difference is the number of overlapping ranges.

You can also cache such numbers as long as the array doesn't change, to avoid having it to iterate it from the beginning every time.

Replies are listed 'Best First'.
Re^2: Optimizing a double loop
by roibrodo (Sexton) on Jun 03, 2010 at 12:40 UTC
    Interesting idea. The thing is once I finished processing all the ranges, I must output the full array of counts (this is passed to another program which I don't have control on). This means I will have to translate this representation to an explicit full array with count in each cell.
[reply]
      You can still generate the full array of counts afterwards and have a speed benefit, because you only have to iterate once over the big array (as opposed to once per overlap in your current implementation).

      Update:

      Example code for obtaining the full array: 

      use strict;
use warnings;

my @a = (10, 15, -20, -30);
my $highest = abs($a[-1]);
my @full = (0) x ($highest + 1);

# decrement all negative values by 1, otherwise
# we would exclude the end points:
for (@a) {
    $_-- if $_ < 0;
}


my $count = 0;
for (0..$highest) {
    if (abs $a[0] == $_) {
        my $c = shift @a;
        if ($c > 0) {
            $count++;
        } else {
            $count--;
        }
    }
    $full[$_] += $count;
}

print join('', @full), "\n";

      [download]

      This assumes that there are never two values of same magnitude in the array, ie never exactly matching start- and endpoints. You can generalize it on your own :-)

      Second update: I've just realized that the extension is very simple:

      Instead of if (abs $a[0] == $_) write while (abs $a[0] == $_), and you're done.

[reply]
[d/l]
[select]

        I'll give it a try. BTW, I will also need to sort the array (by abs values) now.

        UPDATE: There's no real to use $full[$_] += $count; instead of $full[$_] = $count;, is there? we can therefore also drop the initialization of @full, can't we?

[reply]
[d/l]
[select]
      That does revise the spec, doesn't it?
[reply]

In Section Seekers of Perl Wisdom