in reply to Can I speed this up? (repetitively scanning ranges in a large array)

Here's a simple solution:

use strict; use warnings; sub assign_if_higher { $_[0] = $_[1] if $_[0] < $_[1]; } my $size = 10; my @ranges = ( [ 1, 3 ], # 1-based [ 2, 7 ], [ 10, 2 ], ); my @genome = (1) x $size; for (@ranges) { my $s = $_->[0] - 1; # 0-based my $e = $_->[1] - 1; my $m = ($e - $s) % $size / 2; my $x = 3; for (0..$m) { assign_if_higher($genome[($s + $_) % $size], $x); assign_if_higher($genome[($e - $_) % $size], $x); $x += 2; } } print(join(' ', @genome), "\n");

The time is still proportional to the sum of the number of elements covered by each range, but it's done very simply.

Any real optimisation to this approach will come from jumping over values that are already known.

Removing completely overlapping ranges first would take care of some cases, leaving the need to optimising ranges that only partially overlap. It's definitely possible, but I'm out of time.

  • Comment on Re: Can I speed this up? (repetitively scanning ranges in a large array)
  • Download Code

Replies are listed 'Best First'.
Re^2: Can I speed this up? (repetitively scanning ranges in a large array)
by daverave (Scribe) on Nov 03, 2010 at 13:10 UTC
    Thanks. That's actually very similar to the original solution, but with in-lining the object method calls. Adopting this approach actually decreases running time by half. I'm always amazed how large it the overhead for calling functions, and it saddens me since it makes the code less maintainable and understandable. I guess you can't have it all...

      I didn't "inline" for performance reason, I didn't create a sub because there was no reason to.

      my $dist = ($start - $end + 1) % $max_length;

      is perfectly fine without transforming it into

      my $dist = dist($start, $end); sub dist { my $start = shift // die; my $end = shift // die; if ( $end >= $start ) { # simple range return $end - $start + 1; } # warpped range return $max_length - $start + 1 + $end; }

      This is what I was explaining earlier.