473,320 Members | 2,083 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,320 software developers and data experts.

how to speedup this code?

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
Jul 18 '05 #1
5 1487
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
Jul 18 '05 #2
"Ognen Duzlevski" <ma****@gronland.freeshell.org> wrote in message
news:bt**********@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
Jul 18 '05 #3
On Fri, Jan 09, 2004 at 03:21:29PM +0000, Ognen Duzlevski wrote:
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)

You should definitely be using Numeric Python for this.

def Min(a,b):
if a< b:
return a
else:
return b

The builtin function "min" does exactly this, and probably does it quite a
bit faster.

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.


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

Jul 18 '05 #4
"Ognen Duzlevski" <ma****@gronland.freeshell.org> wrote in message
news:bt**********@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
Jul 18 '05 #5
Ognen Duzlevski <ma****@gronland.freeshell.org> writes:
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)


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.
Jul 18 '05 #6

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

8
by: andrewpalumbo | last post by:
I'm trying to write some code which will split up a vector into two halves and run a method on the objects in the vector using two seperate threads. I was hoping to see a near linear speedup on an...
12
by: Steve | last post by:
Hi, I'm getting some output by running a command using os.popen. I need to parse the output and transform it in some sense so that it's 'DB compatible', (i.e I need to store the output in a...
23
by: Mark Dickinson | last post by:
I have a simple 192-line Python script that begins with the line: dummy0 = 47 The script runs in less than 2.5 seconds. The variable dummy0 is never referenced again, directly or indirectly,...
0
by: internetmike | last post by:
I have a client database with a parent form and a tab control on the child form for all my child tables, such as Enquiry, Application, Journal, etc. I am trying to design a "dashboard" panel in...
8
by: TM | last post by:
I have a small application that displays records from an access mdb into two datagrids and am looking to see if it is possible to speedup the loadtime somehow. In my formload I am filling my...
4
by: Daniel | last post by:
Hi group. Any ideas how I could speed up/streamline the below code? Particuarly, is there a way to use a progress bar for when it calculates the MD5? Currently it just looks like it is hung for...
12
by: Lars Schouw | last post by:
All, Does anyone know how much performance speedup I can expect by using 64 bit C++ / Windows XP 64 bit over the 32 bit versions? Did anyone test this under Visual Studio 2005 or Intel C++...
4
by: Galen Somerville | last post by:
My VB2005 app gets real time Heart sounds and an ECG from a USB device. I'm looking for a way to speed up the drawing of the traces on the screen. In the following code the routine GetSounds...
5
by: Johnny Blonde | last post by:
Hello Group! I really tried hard for two hours to rewrite the following expression (python 2.4): -------------------------- teilnehmer = for r in Reisen.select(AND(Reisen.q.RESVON <= datum,...
0
by: DolphinDB | last post by:
The formulas of 101 quantitative trading alphas used by WorldQuant were presented in the paper 101 Formulaic Alphas. However, some formulas are complex, leading to challenges in calculation. Take...
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
0
by: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
0
by: Defcon1945 | last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
0
by: af34tf | last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you
0
by: Faith0G | last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.