how to speedup this code?

[Paul McGuire]

"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

I'm a big fan of "knowing one's blind spots."  It looks to me like you are
using Python, but still thinking in C.  Here are some things Python will be
able to do that C wont.
1. No need to define your own Min() routine - Python has a built-in min()
function that works fine.
2. And even better, the Python min() will accept an arbitrary number of
arguments, not just two.  So instead of calling Min(a,Min(b,c)) you can just
call min(a,b,c).  (This should help quite a bit, as function call overhead
in Python is relatively high.)
3. Access to locals is faster than globals (I'm told).  Try copying
ONEINDELPENALTY and OPENGAPPENALTY to local vars.  Also, since you are not
updating them, the global declaration of ONEINDEL... and OPENGAP... is not
strictly necessary - but I like to include these declarations anyway, as a
reminder that these are globals being accessed.
4. Look at repeated operations, especially in your inner loop.  You
recalculate ndx1-1 many times - how about doing it once in the outer loop
before the second for statement, something like ndx1_1 = ndx1-1, and then
reference ndx1_1 instead (and similar for ndx2-1 and
OPENGAPPENALTY+ONEINDELPENALTY).
5. Look into using the psyco package.  It is very low overhead,
non-intrusive, and can give remarkable results.
6. More performance tips at
http://manatee.mojam.com/~skip/python/fastpython.html, or by Googling for
"python performance".

-- Paul