An interesting problem
McGlinchy, Alistair
Alistair.McGlinchy at marks-and-spencer.com
Thu Jan 4 17:39:41 GMT 2007
Simon Matthews wrote:
> One thing that might speed it up even further would be to
> pre-cache the
> total of (0..x, 0..y) for each x and y.
>
> Then for a particular tile (l..r, t..b):
>
> 0 l r
> +---|---|----+
> |...|///| |
> ----+---+----- t
> |\\\|XXX| |
> |\\\|XXX| |
> ----+---+----- b
> | | | |
> +---|---|----+
>
> Total of ... will be T(l,t)
> Total of /// will be T(r,t) - T(l,r)
> Total of \\\ will be T(l,b) - T(l,r)
>
> So the total of XXX will be:
> T(r,b) - ( total of /// + total of \\\ + total of ... )
> = T(r,b) - ( T(r,t) - T(l,r) + T(l,b) - T(l,r) + T(l,r) )
> = T(r,b) - T(r,t) + T(l,t) - T(l,b)
>
> Simon
I've had a go at this method. Its slower than my previous post (up to
40secs from about 16secs). There's some hash ref caching that may help
speed it up a bit. What I cannot work out is how you think this method
can be intergrare within the previous method. Please advise.
By the way does anyone have a better method doing the max calculation. I
loathe "if (!defined($max) or $max < $val)" line.
Cheers
Alistair
__CODE__
# Same top bit as before.
sub prepare_origin_range {
# Prepare a cache of range sums from he origin to $x,$y
# Initialise the top left row
$sum_from_origin[0][0] = $table[0][0];
# Complete the calulations for the rest of $y where $x==0.
for my $y (1 .. $max_y) {
$sum_from_origin[0][$y] =
$sum_from_origin[0][$y-1] +
$table[0][$y];
}
# Populate the whole table of the $x >0
for my $x (1 .. $max_x) {
#@row_sum is the sume of the slice (0..$y) of the $x'th row
my @row_sum = ($table[$x][0]);
$sum_from_origin[$x][0] = $row_sum[0];
for my $y (1 .. $max_y) {
$row_sum[$y]= $row_sum[$y-1] + $table[$x][$y];
$sum_from_origin[$x][$y] = $sum_from_origin[$x-1][$y] +
$row_sum[$y];
}
}
}
sub max_sum_range {
my $max;
for my $x1(0 .. $max_x) {
for my $y1(0 .. $max_y) {
for my $x2($x1 .. $max_x) {
for my $y2($y1 .. $max_y) {
#+---|---|
#| A | B |
#----+---+
#| C | D |
#----+---+
my $A = $sum_from_origin[$x1][$y1];
my $AB = $sum_from_origin[$x1][$y2];
my $AC = $sum_from_origin[$x2][$y1];
my $ABCD = $sum_from_origin[$x2][$y2];
my $val = $ABCD - $AB - $AC + $A;
if (!defined($max) or $max < $val) {
$max = $val;
print "Range ($x1,$y1) , ($x2,$y2) is better with $val\n";
@result = ($x1,$y1,$x2,$y2);
}
}}}}
return ($max, @result);
}
**********************************************************************
Registered Office:
Marks and Spencer plc
Waterside House
35 North Wharf Road
London
W2 1NW
Registered No. 214436 in England and Wales.
Telephone (020) 7935 4422
Facsimile (020) 7487 2670
<<www.marksandspencer.com>>
Please note that electronic mail may be monitored.
This e-mail is confidential. If you received it by mistake, please let us know and then delete it from your system; you should not copy, disclose, or distribute its contents to anyone nor act in reliance on this e-mail, as this is prohibited and may be unlawful.
2005
More information about the london.pm
mailing list