[SciPy-User] Speeding up a search algorithm
R. Padraic Springuel
R.Springuel at umit.maine.edu
Fri Jun 4 17:19:55 EDT 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