# 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