Attached is a quick implementation of the grid idea. This was 13 times as fast as the original script on my system (6sec vs. 1:18min).

Little disclaimer: I've only tested this on P8 so far, so it is possible that I'm using some Python syntax that doesn't work with earlier versions. If that's the case, and it isn't obvious how to back-port a particular line, let me know.

-- I'm not mad at you, just Westphalian.