An interesting problem

Paul Orrock paulo at
Thu Jan 4 10:25:45 GMT 2007

Thanks everyone for your input. I wrote a script to brute force it using 
Spreadsheet::Perl and summing every possible range. I've attached a 
sample sheet. As you can see there are large blocks of zero values so 
I've managed to cut it down quite a lot by working out where the first 
and last point of non zero data are and just iterating over the blocks 
between them. In the attached dataset this means it only works over the 
ranges between U11 to BC55.

It works but it is incredibly slow, like over a hour for 650,000 ranges 
on a P4. I'm sure the Spreadsheet::Perl range sum calculation is taking 
the time so I'll rip it out and write one myself. For the attached sheet 
my code makes AH34 to AP32 the most positive range at 97.57.

McGlinchy, Alistair wrote:
>> 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!

Wow, that's a big difference.

> Code available if anyone else was interested.

Yes please,



More information about the mailing list