449,264 Members | 1,761 Online
Need help? Post your question and get tips & solutions from a community of 449,264 IT Pros & Developers. It's quick & easy.

# how to speedup this code?

 P: n/a 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 Replies

 P: n/a 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

 P: n/a "Ognen Duzlevski" 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

 P: n/a 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

 P: n/a "Ognen Duzlevski" 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

 P: n/a Ognen Duzlevski 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 discussion thread is closed

Replies have been disabled for this discussion.