soft-matter/trackpy — pull request #76 by nkeim (2014-02-08 22:04:42+00:00)
Title: PERF: Rewrite assign_candidates() for speed.

`scipy` >= 0.12 allows `cKDTree` to be queried for many points at once. This allows much of `assign_candidates` to be vectorized.

This can be seen in `prun` output, tracking ~16k particles for 5 frames. (Note that this is using my legacy feature-finding code)

Before:
```
ncalls tottime percall cumtime percall filename:lineno(function)
146506 3.272 0.000 7.375 0.000 {method 'query' of 'scipy.spatial.ckdtree.cKDTree' objects}
277617 2.793 0.000 2.793 0.000 {method 'reduce' of 'numpy.ufunc' objects}
10 2.296 0.230 2.296 0.230 {scipy.ndimage._nd_image.correlate}
4 1.187 0.297 4.513 1.128 linking.py:885(assign_candidates)
```

After:
```
ncalls tottime percall cumtime percall filename:lineno(function)
10 2.236 0.224 2.236 0.224 {scipy.ndimage._nd_image.correlate}
81487 1.908 0.000 4.119 0.000 {method 'query' of 'scipy.spatial.ckdtree.cKDTree' objects}
212603 1.898 0.000 1.898 0.000 {method 'reduce' of 'numpy.ufunc' objects}
6 0.894 0.149 20.353 3.392 linking.py:623(link_iter)
65022 0.729 0.000 4.623 0.000 predict.py:155(predict)
65022 0.694 0.000 1.620 0.000 interpolate.py:454(_check_bounds)
20 0.647 0.032 0.647 0.032 {scipy.ndimage._nd_image.correlate1d}
376924 0.641 0.000 0.820 0.000 {numpy.core.multiarray.array}
20 0.570 0.029 0.570 0.029 {scipy.ndimage._nd_image.uniform_filter1d}
65022 0.450 0.000 1.002 0.000 interpolate.py:423(_call_nearest)
65022 0.432 0.000 3.153 0.000 interpolate.py:443(_evaluate)
35353/20113 0.408 0.000 7.303 0.000 {map}
5 0.384 0.077 0.836 0.167 identification.py:27(find_local_max)
5 0.384 0.077 4.385 0.877 track.py:177(merge_groups)
4 0.337 0.084 0.565 0.141 linking.py:885(assign_candidates)
```