how to speedup this code?

[Sean Ross]

"Ognen Duzlevski" <maketo at gronland.freeshell.org> wrote in message
news:btmgtp$grr$1 at chessie.cirr.com...
> Hi all,
>
> I have rewritten a C program to solve a bioinformatics problem. Portion
where most of the time is spent is:
>
> def DynAlign(scoremat,insertmat,delmat,tseq,qseq,tlen,qlen):
>     global ONEINDELPENALTY,OPENGAPPENALTY
>
>     for ndx1 in range(1,tlen+1):
>         for ndx2 in range(1,qlen+1):
>             delmat[ndx1][ndx2] = Min(delmat[ndx1-1][ndx2]+ONEINDELPENALTY,
\
>
Min(scoremat[ndx1-1][ndx2]+OPENGAPPENALTY+ONEINDELPENALTY, \
>
insertmat[ndx1-1][ndx2]+OPENGAPPENALTY+ONEINDELPENALTY))
>             insertmat[ndx1][ndx2] =
Min(insertmat[ndx1][ndx2-1]+ONEINDELPENALTY, \
>
Min(scoremat[ndx1][ndx2-1]+OPENGAPPENALTY+ONEINDELPENALTY, \
>
delmat[ndx1][ndx2-1]+OPENGAPPENALTY+ONEINDELPENALTY))
>             scoremat[ndx1][ndx2] = Min(scoremat[ndx1-1][ndx2-1], \
>                             Min(delmat[ndx1-1][ndx2-1],
insertmat[ndx1-1][ndx2-1])) + \
>                             GetFitnessScore(tseq,ndx1-1,qseq,ndx2-1)
>
> def Min(a,b):
> if a< b:
> return a
> else:
> return b
>
> In C this is not a big deal, delmat, scoremat and insertmat are int
matrices dynamically allocated and the
> loop-inside-a-loop is pretty fast. However, on python (2.3) it is very
slow. So for comparison, my C version takes 8
> seconds to execute and the python version takes around 730 seconds. I have
narrowed down through visual observation
> (print before and print after entry into the above nested loop) that most
of the time is spent in there. I have also
> tried the Numeric package with their arrays. It speeded things up somewhat
but not considerably.
>
> Any suggestions?
>
> Thank you,
> Ognen

Hi.
There is a builtin min() function, so using that should speed things up a
little. Also, you calculate
"OPENGAPPENALTY+ONEINDELPENALTY" 4 times inside the loop. Outside the loop,
store
the value of this sum in a variable, say P(?). You also calculate ndx-1 and
ndx2-1
5 and 7 times, respectively, so you may want to store those values in temp.
variables -
say prerow, and precol.  range(1,qlen+1) is evaluated tlen times - if qlen
does not change, then
storing this result would be a good idea, using, say, 'columns'.

There are other things, though perhaps not speed related:

You have three near indentical operations that could be refactored into a
function:

def calculate_score(m, n, o, row, col, p0, p1, p2):
    # you can choose a more appropriate function name
    m_val = m[row][col]+p0
    n_val = n[row][col]+p1
    o_val = o[row][col]+p2
    return min(m_val, min(n_val, o_val))

This may actually slow things down, so you may not want to use this
function.
So, if you use these suggestions, you'll end up with something like this
[untested]:

def DynAlign(scoremat,insertmat,delmat,tseq,qseq,tlen,qlen):
     global ONEINDELPENALTY,OPENGAPPENALTY
     OIP = ONEINDELPENALTY
     P =  OPENGAPPENALTY+ONEINDELPENALTY
     s,i,d = scoremat,insertmat,delmat
     columns = range(1,qlen+1)
     for row in range(1,tlen+1):
         prerow = row - 1
         for col in columns:
             precol = col - 1
             FSP = GetFitnessScore(tseq,prerow,qseq,precol)
             delmat[row][col] = calculate_score(d,s,i,prerow,col,OIP,P,P)
             insertmat[row][col] = calculate_score(i,s,d,row,precol,OIP,P,P)
             scoremat[row][col] =
calculate_score(s,d,i,prerow,precol,0,0,FSP)


OK, so, HTH
Sean