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.
|
|---|
| 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 | |
by ikegami (Patriarch) on Nov 03, 2010 at 17:16 UTC |