An interesting problem
Andy Armstrong
andy at hexten.net
Wed Jan 3 21:08:23 GMT 2007
On 3 Jan 2007, at 20:44, McGlinchy, Alistair wrote:
> my $best;
> my @result;
> for (my $x1 = 0 ; $x1< $max_x ; $x1++) {
> for (my $y1 = 0 ; $y1< $max_y ; $y1++) {
> print "New $x1,$y1 for top left considerd\n";
> for (my $x2 = $x1 ; $x2< $max_x ; $x2++) {
> for (my $y2 = $y1 ; $y2< $max_y ; $y2++) {
> my $val = sum_range($x1, $y1, $x2, $y2);
> # print "Range ($x1,$y1) , ($x2,$y2) has val $val\n";
> if (!defined($best) or $val > $best) {
> print "Range ($x1,$y1) , ($x2,$y2) is better with $val\n";
> $best = $val;
> @result = ($x1,$y1,$x2,$y2);
>
> }
> }}}}
You don't actually need to compute the sum from scratch every time -
you can instead adjust the sum every time one of the indexes changes
to include / exclude the part of the row / column that corresponds
with the change of index. For any non-trivial array though the
performance problem's going to come from having four nested loops.
How much data will you be working with in practice?
--
Andy Armstrong, hexten.net
More information about the london.pm
mailing list