An interesting problem
paulo at digitalcraftsmen.net
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.
More information about the london.pm