[Tutor] Code optmisation

Kent Johnson kent37 at tds.net
Mon Apr 7 15:40:39 CEST 2008


yogi wrote:
Some small optimizations inline, more important comments after the code.

>  #/bin/python
> import sys, os, csv, re
> x =  0                                  #Define Zero for now
> var = 1000000                           #Taking the variation 
> # This programme finds the SNPs from the range passed 
> # csv splits columns and this file is tab spaced
> fis = csv.reader(open("divs.map", "rb"), delimiter='\t', quoting=csv.QUOTE_NONE)
> for row in fis:
> # csv splits columns and this file is ","  spaced
>         gvalues = csv.reader(open("genvalues", "rb"), delimiter=',', quoting=csv.QUOTE_NONE)

If gvalues contains all integers you could say
   gvalues = map(int, gvalues)
to convert the whole list to ints at once, then you could remove the 
individual int(gvalue[x]) calls below.

>         for gvalue in gvalues:
> # To see  Columns (chr) Match 
>                 if row[0] == gvalue[0]:
> # If  Column 3  (range) is Zero  print row
>                         if int(gvalue[3]) ==  x:
>                                 a = int(gvalue[1]) - var
>                                 b = int(gvalue[2]) + var + 1
>                                 if int(a <= int(row[3]) <= b):

No need for int() here and below, the result of the comparison is a 
boolean which is what the if statement wants.

>                                         print   row
> # If  Column 3  (range) is not zero find matches and print row
>                         else:
>                                 a = int(gvalue[1]) - var
>                                 b = int(gvalue[2]) + var + 1
>                                 if int(a <= int(row[3]) <= b):
>                                         print row
>                                         c = int(gvalue[3]) - var
>                                         d = int(gvalue[4]) + var + 1
>                                         if int(c <= int(row[3]) <= d):
>                                                 print   row
> 

There will probably be other micro-optimizations you can do but first 
you need to fix your algorithm.
> -----------------------------------------------------
> 
> Question1 : Is there a better way ?

Yes. You don't say how long the above takes to run but if by 12M you 
mean 12,000,000 then I think the running time will be measured in months.

The biggest problem (other than reading genvalues from disk 12M times, 
as Alan pointed out) is that the body of the inner loop will be executed 
12M*1M times. You have to look for ways to get away from that product term.

Two possibilities:
- If the two files are sorted, you could walk through them in parallel 
finding and printing matches as you go. If the files are not sorted, you 
could sort them yourself, either reading the entire file into memory and 
sorting with Python, or using an external disk sort such as Linux 
sort(1). With this approach you would make a single pass through each file.

- Build a dict mapping gvalue[0] to a list of ranges for the gvalue. 
Precompute the ranges (int conversion and var offsets) so when you 
access the values you only have to compare, no arithmetic. Then for each 
row in fis, look up row[0] in the dict, iterate through the ranges 
associated with that value and print the matches.

How well the second approach works will depend on the number of 
different gvalue[0] values. If there are none, it won't cut down on the 
size of the inner loop at all. If there are many, it will help considerably.

> Question 2: If I have convert this code into a function.
> Should I ?

Yes. Access to local variables in a function is faster than access to 
global variables.

Kent


More information about the Tutor mailing list