Interesting timing issue I noticed

[Gabriel Genellina]

En Tue, 15 Apr 2008 23:24:01 -0300, Jonathan Shao <jzshao1 at gmail.com>  
escribió:

> I've written up a stripped down version of the code. I apologize for the  
> bad
> coding; I am in a bit of a hurry.

First things first: I think you will gain inmensely using NumPy:  
http://numpy.scipy.org/

My timings were 62 and 47ms with your code; after I modified it slightly,  
39 and 48ms (for the "on3" and "two" functions).
The changes:
- instead of a list of lists, I used a defaultdict with (x,y) as the keys.  
That is, instead of matrix[x][y], I use matrix[x,y]
- I converted all range -> xrange

Some lines showing the changes:

# generates a zero matrix
def generate_zero():
     import collections
     matrix = collections.defaultdict(int)
     return matrix

def back_diff_one(back_array, fore_array, box):
     diff_array = generate_zero()
     start = time.time()
     for x in xrange(sizeX):
         for y in xrange(borderY):
             idx = x,y
             diff_array[idx] = back_array[idx] - fore_array[idx]
         for y in xrange((sizeY - borderY), sizeY):
             idx = x,y
             diff_array[idx] = back_array[idx] - fore_array[idx]
     for y in xrange(borderY, (sizeY - borderY)):
         for x in xrange(borderX):
             idx = x,y
             diff_array[idx] = back_array[idx] - fore_array[idx]
         for x in xrange((sizeX - borderX), sizeX):
             idx = x,y
             diff_array[idx] = back_array[idx] - fore_array[idx]

Probably most of the time was spent on creating that many range objects in  
the inner loops. xrange objects are rather cheap, but you may try  
pre-creating them in advance before entering the loops.
Another thing would be to rearrange the loops so the outer one executes  
less times; if you know that borderX<<sizeX and borderY<<sizeY it may be  
better to swap the inner and outer loops above.

(I assume the above code is just a simplified example, because all the  
loops do the same thing and cover the whole picture...)

-- 
Gabriel Genellina