Optimising Python

[PhrackSipsin]

Hello All,

I'm pretty new to python but have been programming, for a few years hobby wise and decided to try python after I found how concise the syntax was and with a computer science bent. So I'm writing a little code for a work related thing, simulating some basic message passing model we're working with. I finally got something to work and it's pretty shocking how long it takes. To fill a 10x20 array it must take 30-40 minutes. I can do it by hand faster and was hoping to fill arrays of thousands.

Anyway any help appreciated, I realise that most of it's loops and comparisons which a brief look over the python optimisation guide tells me is really inefficient but I can't see anyway of using different methods to accomplish this.

#! /usr/bin/env python #Define size of matrix xSize, ySize = 10, 20

#Define sources s1x, s1y = 0, 0 s2x, s2y = 1, 1

# create a 10 x 10 matrix of zeroes medium = [['e' for y in range(ySize)] for x in range(xSize)]

#Return the tuple of points that is the moore neighbourhood def moorePoints(tup): coords = () for x1 in range(-1,2): for y1 in range(-1,2): coords += (tup[0]+x1,tup[1]+y1), return coords #Print the array def displayMed(): for row in reversed(medium): print row #return coords not already in the array def newCoords(tup): newtup = () for k in tup: if k[0] >= xSize or k[1] >= ySize or k[0] < 0 or k[1] < 0: pass elif medium[k[0]][k[1]] == 'e': newtup += k, return newtup

#Add the coordinates to the array def addCoords(tup, time): for k in tup: medium[k[0]][k[1]] = time

#Calculate maximum number of iterations required loop = max(abs(((xSize/2)-s2x))+(xSize/2),abs(((ySize/2)-s2y))+(ySize/2)) setOfPoints = (s2x,s2y), medium[s2x][s2y] = 0 print 'loops', loop

#MainLoop

for j in range(loop): print 'loop:', j newPoints = () for k in setOfPoints: newPoints += moorePoints(k) addCoords(newCoords(newPoints),(j+1)) setOfPoints = newPoints #print setOfPoints, '::::', newPoints displayMed() print '' displayMed()

[\code][code=python]

#! /usr/bin/env python
#Define size of matrix
xSize, ySize = 10, 20

#Define sources
s1x, s1y = 0, 0
s2x, s2y = 1, 1

# create a 10 x 10 matrix of zeroes
medium = [ for x in range(xSize)]

#Return the tuple of points that is the moore neighbourhood
def moorePoints(tup):
coords = ()
for x1 in range(-1,2):
for y1 in range(-1,2):
coords += (tup[0]+x1,tup[1]+y1),
return coords

#Print the array
def displayMed():
for row in reversed(medium):
print row

#return coords not already in the array
def newCoords(tup):
newtup = ()

for k in tup:

if k[0] >= xSize or k[1] >= ySize or k[0] < 0 or k[1] < 0:
pass
elif medium[k[0]][k[1]] == 'e':
newtup += k,

return newtup

#Add the coordinates to the array
def addCoords(tup, time):
for k in tup:
medium[k[0]][k[1]] = time

#Calculate maximum number of iterations required
loop = max(abs(((xSize/2)-s2x))+(xSize/2),abs(((ySize/2)-s2y))+(ySize/2))
setOfPoints = (s2x,s2y),
medium[s2x][s2y] = 0
print 'loops', loop

#MainLoop

for j in range(loop):
print 'loop:', j
newPoints = ()

for k in setOfPoints:
newPoints += moorePoints(k)

addCoords(newCoords(newPoints),(j+1))
setOfPoints = newPoints

#print setOfPoints, '::::', newPoints
displayMed()
print ''
displayMed()

[\code]

[woooee]

There is something terribly wrong if a 200 element list (10x20) takes that long to run. To answer your question, you can use a dictionary of tuples to get better performance. For example:
medium[k[0]][k[1]] = time
becomes
medium_dict[ (k[0], k[1]) ] = time

The simpliest way to time something is to use datetime. You would probably start by timing a suspect function. There is also the timeit module but that slows things down by a factor of 10 or more.

def newCoords(tup):
    now = datetime.datetime.now()     ## start time
    newtup = ()

    for k in tup:
       
        ##  the following if statement does nothing, unless you want to exclude these records.
        ##  if you do want to exclude them,  place this if() under the next "if medium [k[0]][k[1]] == 'e':"
        ##  there is no point testing every record
        if k[0] >= xSize or k[1] >= ySize or k[0] < 0 or k[1] < 0:
            pass
        elif medium[k[0]][k[1]] == 'e':
            newtup += k,

    print datetime.datetime.now() - now   ##  print elapsed time
    return newtup

And this is the code that I ran.

import datetime

now = datetime.datetime.now()
#Define size of matrix
xSize, ySize = 10, 20

#Define sources
s1x, s1y = 0, 0
s2x, s2y = 1, 1

# create a 10 x 10 matrix of zeroes
medium = [['e' for y in range(ySize)] for x in range(xSize)]



#Return the tuple of points that is the moore neighbourhood
def moorePoints(tup):
    coords = ()
    for x1 in range(-1,2):
        for y1 in range(-1,2):
            coords += (tup[0]+x1,tup[1]+y1),
    return coords

#Print the array
def displayMed():
    for row in reversed(medium):
        print row

#return coords not already in the array
def newCoords(tup):
    newtup = ()

    for k in tup:

        if k[0] >= xSize or k[1] >= ySize or k[0] < 0 or k[1] < 0:
            pass
        elif medium[k[0]][k[1]] == 'e':
            newtup += k,

    return newtup

#Add the coordinates to the array
def addCoords(tup, time):
    for k in tup:
        medium[k[0]][k[1]] = time

#Calculate maximum number of iterations required
loop = max(abs(((xSize/2)-s2x))+(xSize/2),abs(((ySize/2)-s2y))+(ySize/2))
setOfPoints = (s2x,s2y),
medium[s2x][s2y] = 0
print 'loops', loop


#MainLoop

for j in range(loop):
    print 'loop:', j
    newPoints = ()

    for k in setOfPoints:
        newPoints += moorePoints(k)

        addCoords(newCoords(newPoints),(j+1))
        setOfPoints = newPoints

        #print setOfPoints, '::::', newPoints
        displayMed()
print 
displayMed()
print datetime.datetime.now() - now