An interesting problem

[McGlinchy, Alistair]

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