how to speedup this code?

[Ognen Duzlevski]

Hi all,

I have rewritten a C program to solve a bioinformatics problem. Portion where most of the time is spent is:

def DynAlign(scorem at,insertmat,de lmat,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]+ONEINDELPENALT Y, \
Min(scoremat[ndx1-1][ndx2]+OPENGAPPENALTY +ONEINDELPENALT Y, \
insertmat[ndx1-1][ndx2]+OPENGAPPENALTY +ONEINDELPENALT Y))
insertmat[ndx1][ndx2] = Min(insertmat[ndx1][ndx2-1]+ONEINDELPENALT Y, \
Min(scoremat[ndx1][ndx2-1]+OPENGAPPENALTY +ONEINDELPENALT Y, \
delmat[ndx1][ndx2-1]+OPENGAPPENALTY +ONEINDELPENALT Y))
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

[Ognen Duzlevski]

Re: how to speedup this code?

I forgot to say that I have declared the above matrices as lists of lists or by using the Numeric package as their
arrays.

Ognen

[Paul McGuire]

Re: how to speedup this code?

"Ognen Duzlevski" <maketo@gronlan d.freeshell.org > wrote in message
news:btmgtp$grr $1@chessie.cirr .com...[color=blue]
> Hi all,
>
> I have rewritten a C program to solve a bioinformatics problem. Portion[/color]
where most of the time is spent is:[color=blue]
>
> def DynAlign(scorem at,insertmat,de lmat,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]+ONEINDELPENALT Y,[/color]
\[color=blue]
>[/color]
Min(scoremat[ndx1-1][ndx2]+OPENGAPPENALTY +ONEINDELPENALT Y, \[color=blue]
>[/color]
insertmat[ndx1-1][ndx2]+OPENGAPPENALTY +ONEINDELPENALT Y))[color=blue]
> insertmat[ndx1][ndx2] =[/color]
Min(insertmat[ndx1][ndx2-1]+ONEINDELPENALT Y, \[color=blue]
>[/color]
Min(scoremat[ndx1][ndx2-1]+OPENGAPPENALTY +ONEINDELPENALT Y, \[color=blue]
>[/color]
delmat[ndx1][ndx2-1]+OPENGAPPENALTY +ONEINDELPENALT Y))[color=blue]
> scoremat[ndx1][ndx2] = Min(scoremat[ndx1-1][ndx2-1], \
> Min(delmat[ndx1-1][ndx2-1],[/color]
insertmat[ndx1-1][ndx2-1])) + \[color=blue]
> 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[/color]
matrices dynamically allocated and the[color=blue]
> loop-inside-a-loop is pretty fast. However, on python (2.3) it is very[/color]
slow. So for comparison, my C version takes 8[color=blue]
> seconds to execute and the python version takes around 730 seconds. I have[/color]
narrowed down through visual observation[color=blue]
> (print before and print after entry into the above nested loop) that most[/color]
of the time is spent in there. I have also[color=blue]
> tried the Numeric package with their arrays. It speeded things up somewhat[/color]
but not considerably.[color=blue]
>
> Any suggestions?
>
> Thank you,
> Ognen[/color]

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

[Jp Calderone]

Re: how to speedup this code?

On Fri, Jan 09, 2004 at 03:21:29PM +0000, Ognen Duzlevski wrote:[color=blue]
> Hi all,
>
> I have rewritten a C program to solve a bioinformatics problem. Portion
> where most of the time is spent is:
>
> def DynAlign(scorem at,insertmat,de lmat,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]+ONEINDELPENALT Y, \
> Min(scoremat[ndx1-1][ndx2]+OPENGAPPENALTY +ONEINDELPENALT Y, \
> insertmat[ndx1-1][ndx2]+OPENGAPPENALTY +ONEINDELPENALT Y))
> insertmat[ndx1][ndx2] = Min(insertmat[ndx1][ndx2-1]+ONEINDELPENALT Y, \
> Min(scoremat[ndx1][ndx2-1]+OPENGAPPENALTY +ONEINDELPENALT Y, \
> delmat[ndx1][ndx2-1]+OPENGAPPENALTY +ONEINDELPENALT Y))
> 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)[/color]


You should definitely be using Numeric Python for this.
[color=blue]
>
> def Min(a,b):
> if a< b:
> return a
> else:
> return b[/color]


The builtin function "min" does exactly this, and probably does it quite a
bit faster.
[color=blue]
>
> 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.[/color]

Did you loop over the arrays and perform the same operations as DynAlign
above does? If so, that's not the best way to do it. Use the matrix
operations it provides. You'll know when you have written a good Numeric
solution when your code no longer has any `for' loops.

Jp

[Sean Ross]

Re: how to speedup this code?

"Ognen Duzlevski" <maketo@gronlan d.freeshell.org > wrote in message
news:btmgtp$grr $1@chessie.cirr .com...[color=blue]
> Hi all,
>
> I have rewritten a C program to solve a bioinformatics problem. Portion[/color]
where most of the time is spent is:[color=blue]
>
> def DynAlign(scorem at,insertmat,de lmat,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]+ONEINDELPENALT Y,[/color]
\[color=blue]
>[/color]
Min(scoremat[ndx1-1][ndx2]+OPENGAPPENALTY +ONEINDELPENALT Y, \[color=blue]
>[/color]
insertmat[ndx1-1][ndx2]+OPENGAPPENALTY +ONEINDELPENALT Y))[color=blue]
> insertmat[ndx1][ndx2] =[/color]
Min(insertmat[ndx1][ndx2-1]+ONEINDELPENALT Y, \[color=blue]
>[/color]
Min(scoremat[ndx1][ndx2-1]+OPENGAPPENALTY +ONEINDELPENALT Y, \[color=blue]
>[/color]
delmat[ndx1][ndx2-1]+OPENGAPPENALTY +ONEINDELPENALT Y))[color=blue]
> scoremat[ndx1][ndx2] = Min(scoremat[ndx1-1][ndx2-1], \
> Min(delmat[ndx1-1][ndx2-1],[/color]
insertmat[ndx1-1][ndx2-1])) + \[color=blue]
> 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[/color]
matrices dynamically allocated and the[color=blue]
> loop-inside-a-loop is pretty fast. However, on python (2.3) it is very[/color]
slow. So for comparison, my C version takes 8[color=blue]
> seconds to execute and the python version takes around 730 seconds. I have[/color]
narrowed down through visual observation[color=blue]
> (print before and print after entry into the above nested loop) that most[/color]
of the time is spent in there. I have also[color=blue]
> tried the Numeric package with their arrays. It speeded things up somewhat[/color]
but not considerably.[color=blue]
>
> Any suggestions?
>
> Thank you,
> Ognen[/color]

Hi.
There is a builtin min() function, so using that should speed things up a
little. Also, you calculate
"OPENGAPPENALTY +ONEINDELPENALT Y" 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(scorem at,insertmat,de lmat,tseq,qseq, tlen,qlen):
global ONEINDELPENALTY ,OPENGAPPENALTY
OIP = ONEINDELPENALTY
P = OPENGAPPENALTY+ ONEINDELPENALTY
s,i,d = scoremat,insert mat,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,qs eq,precol)
delmat[row][col] = calculate_score (d,s,i,prerow,c ol,OIP,P,P)
insertmat[row][col] = calculate_score (i,s,d,row,prec ol,OIP,P,P)
scoremat[row][col] =
calculate_score (s,d,i,prerow,p recol,0,0,FSP)


OK, so, HTH
Sean

[Alexander Schmolck]

Re: how to speedup this code?

Ognen Duzlevski <maketo@gronlan d.freeshell.org > writes:
[color=blue]
> Hi all,
>
> I have rewritten a C program to solve a bioinformatics problem. Portion where most of the time is spent is:
>
> def DynAlign(scorem at,insertmat,de lmat,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]+ONEINDELPENALT Y, \
> Min(scoremat[ndx1-1][ndx2]+OPENGAPPENALTY +ONEINDELPENALT Y, \
> insertmat[ndx1-1][ndx2]+OPENGAPPENALTY +ONEINDELPENALT Y))
> insertmat[ndx1][ndx2] = Min(insertmat[ndx1][ndx2-1]+ONEINDELPENALT Y, \
> Min(scoremat[ndx1][ndx2-1]+OPENGAPPENALTY +ONEINDELPENALT Y, \
> delmat[ndx1][ndx2-1]+OPENGAPPENALTY +ONEINDELPENALT Y))
> 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)[/color]

You're obviously quite new to python and Numeric (also have a look at
numarray, BTW, which is meant to replace Numeric in the not so far future), so
you're still thinking in terms of C.

In python+Numeric you can often replace C-style for loops with a much more
concise and elegant array manipulation (which will be very efficient, unlike
for loops in python -- unless you are using psyco, that is).

I think you're particular example will fit into this pattern (warning: the
code below is just toget you started -- it might be quite wrong, I haven't
looked too carefullly at your code and just jotted this down quickly):

from Numeric import minimum, array, ...
delmat = array(
[...]
def ...

# formatted a bit funny for better visual clarity
delmat[1:tlen+1,1:qlen +1] = \
minimum( delmat[1:tlen,1:qlen+1]+ ONEINDELPENALTY ,
minimum( scoremat[1:tlen,1:qlen+1]+ OPENGAPPENALTY,
insertmat[1:tlen,1:qlen+1]+ OPENGAPPENALTY + ONEINDELPENALTY ))
[etc.]

Be sure you understand the indexing (NB. array[a][b] vs. array[a,b]), the
Numeric manual is quite good, so have a look at it (reading some code in scipy
or some other project that uses Numeric might also be a good way to speed up
the learning process).


HTH

'as

p.s. Let me also recommend that you don't emulate the C style
compile-run-debug-edit approach in python -- I think you'll find that a
test-driven development + an interactive shell to try things out (have a look
at ipython, BTW) make for much more pleasant scientific computing.