[SciPy-User] Speeding up a search algorithm

R. Padraic Springuel R.Springuel@umit.maine....
Fri Jun 4 16:19:55 CDT 2010


After playing around with some of the various suggestions, as well as a 
few of my own ideas, I've modified my algorithm to the following:

c = []
d = []
for i in range(len(current)):
     c += [current[i]]*i
     d += current[:i]
search = distancematrix[c,d]
m = numpy.nanmin(search)
mask = search == m
n1 = c[mask.argmax()]
n2 = d[mask.argmax()]
if aggr != None:
     if aggr:
         p1 = 0
     else:
         p1 = N
     for i in range(len(search)):
         if mask[i]:
             if c[i] < 0:
                 p2 = tree.pop[c[i]]
             else:
                 p2 = 1
             if d[i] < 0:
                 p2 += tree.pop[d[i]]
             else:
                 p2 += 1
             if p2 < p1 and not aggr:
                 n1 = c[i]
                 n2 = d[i]
                 p1 = p2
             elif p2 > p1 and aggr:
                 n1 = c[i]
                 n2 = d[i]
                 p1 = p2

In testing on a 3000x3000 array, I'm seeing approximately a 7- to 8-fold 
increase in speed.  While I believe that will serve my purposes for now, 
if anyone has any other ideas on how to increase the speed further, I'm 
all ears.  According to my testing "search = distancematrix[c,d]" is 
consistently the slowest step but the "for i in range(len(search)):" 
loop takes about the same amount of time when it's run.
-- 

R. Padraic Springuel
Research Assistant
Department of Physics and Astronomy
University of Maine
Bennett 309
Office Hours: By Appointment Only


More information about the SciPy-User mailing list