An interesting problem

[McGlinchy, Alistair]

> >> I think that the previous mention of a 2D autocorrelation will be
> >> good to explore, but you can use the "moving average" trick 
> >to avoid
> >> lots of extra cycles while summing neighborhoods.  I've implemented
> >> this in C before and gotten speedups of 1x to 50x, 
> depending on the  
> >> neighborhood size.
> >
> >Aye, That's the trick. Run time from 10 mins to 16secs for 
> the 30x100 
> >case. Great fun!
> >
> >Code available if anyone else was interested.
> 
> I certainly am, and I'd imagine most others who read the thread.
> 

OK some warts'n'all code here. Something is munging my posts to either
word-wrap or delete attachments. I'll attach the code as a .txt file as
well and see if that helps.

#!/usr/bin/perl 
use strict;
use warnings;
my %store;

# Data stores using in process. Global out of laziness. 
my @sum_row;
my @sum_range;
my @table; 

# Read in the numbers
while (<DATA>) {
    chomp;
    s/^\s+//;# Remove initial  whitespace.
    s/\s+$//;# Remove trailing whitespace.
    next if /^\s*$/; #Ignore blank lines
    my @row = split /\s+/;
    push @table, \@row;
}
my $max_x = $#table;
my $max_y = $#{$table[0]};

warn "Preparing row cache\n";
prepare_sum_row();
warn "Row Cache Constructed\n";
my ($max, @result ) = max_sum_range();
print "Best range ($result[0],$result[1]) , ($result[2],$result[3]) has
maximum val $max\n";
exit 0;

sub prepare_sum_row { 
    # Prepare a cache of AoAoA of sum of intervales within each row 
    # $sum_row[$x][$y_start][$y_end] is the sum of the cells in row 
    # x from column y_start to y_end
    for my $x        (0 .. $max_x) {
    for my $y_start  (0 .. $max_y) {
        $sum_row[$x][$y_start][$y_start] = $table[$x][$y_start]; # First
cell in the row
        for my $y_end ($y_start +1 .. $max_y) {
            $sum_row[$x][$y_start][$y_end] =    
                $sum_row[$x][$y_start][$y_end-1] + # All previous cells
                $table[$x][$y_end];                # plust this one
        }
    }}
}

sub max_sum_range { 
    # Note for ref lookup efficiency the matrix is in a funny order 
    # $sum_range[$x_start][$y_start][$y_end][$x_end  ]
    # is the sum of the range from (x_start,y_start) to (x_end,_y_end)
    my $max;
    for my $x_start (0..$max_x)  {
        for my $y_start (0..$max_y)  {
            my $row_ender =   $sum_row[$x_start][$y_start];     #keep
this ref hand
            my $range_cnr = $sum_range[$x_start][$y_start]=[];  #keep
this ref handy too
            for my $y_end ($y_start .. $max_y ) {
                my $range_2cnrs= $range_cnr->[$y_end];
                my $val = $range_2cnrs->[$x_start] =
$row_ender->[$y_end]; 
                if (!defined($max) or $max < $val ) {
                    $max = $val;
                    print "Range ($x_start,$y_start) , ($x_start,$y_end)
is better with $val\n";
                    @result = ($x_start,$y_start,$x_start,$y_end);
                }
                for my $x_end ($x_start+1 .. $max_x) {
                    $val = $range_2cnrs->[$x_end] = 
                           $range_2cnrs->[$x_end-1] + 
                           $sum_row[$x_end][$y_start][$y_end];


                    if ($max < $val) {
                        $max = $val;
                        print "Range ($x_start,$y_start) ,
($x_end,$y_end) is better with $val\n";
                        @result = ($x_start,$y_start,$x_end,$y_end);
                    }
                }
            }               
        }
    }
    return ($max, @result);
}
            
__DATA__
-22 -42 -37 -48 29  48  -31 7   -19 -47 -50 -25 -27 -23 38  -24 20  -45
38  -31 -27 14  25  18  -5  13  33  25  19  41  23  26  -43 -21 45  9
-42 18  15  4   49  -45 46  13  -31 -17 -34 27  3   -41
-12 16  38  -18 -18 -43 -39 -44 47  -45 40  -46 -27 5   -23 -26 18  48
15  -11 -41 45  -5  4   -5  -40 18  -34 1   -48 40  39  -33 -24 25  -32
-9  -12 -5  16  10  48  4   14  -20 -20 -39 1   -36 29
-14 37  -34 -21 43  13  4   46  -43 38  -33 -21 -44 24  36  37  46  1
-31 42  -23 -37 -12 -11 -36 29  -46 10  -22 2   -41 -29 41  0   40  22
20  -1  24  -49 -29 1   21  -14 43  -47 13  26  -4  -5

**********************************************************************
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


-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: max_range5.txt
Url: http://london.pm.org/pipermail/london.pm/attachments/20070104/db76688b/max_range5-0001.txt