<br><br><div class="gmail_quote">On Tue, Mar 5, 2013 at 9:15 AM, Phil Elson <span dir="ltr"><<a href="mailto:pelson.pub@gmail.com" target="_blank">pelson.pub@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div dir="ltr"><div>The ticket <a href="https://github.com/numpy/numpy/issues/2269" target="_blank">https://github.com/numpy/numpy/issues/2269</a> discusses the possibility of implementing a "find first" style function which can optimise the process of finding the first value(s) which match a predicate in a given 1D array. For example:<br>
<br><br>>>> a = np.sin(np.linspace(0, np.pi, 200))<br>>>> print find_first(a, lambda a: a > 0.9)<br></div>((71, ), 0.900479032457)<br><div><br><br></div><div>This has been discussed in several locations:<br>
<br><a href="https://github.com/numpy/numpy/issues/2269" target="_blank">https://github.com/numpy/numpy/issues/2269</a><br><a href="https://github.com/numpy/numpy/issues/2333" target="_blank">https://github.com/numpy/numpy/issues/2333</a><br>
<a href="http://stackoverflow.com/questions/7632963/numpy-array-how-to-find-index-of-first-occurrence-of-item" target="_blank">http://stackoverflow.com/questions/7632963/numpy-array-how-to-find-index-of-first-occurrence-of-item</a><br>
<br><br></div><div><u>Rationale</u><br></div><div><br></div><div>For small arrays there is no real reason to avoid doing:<br><br>>>> a = np.sin(np.linspace(0, np.pi, 200))<br>>>> ind = (a > 0.9).nonzero()[0][0]<br>
</div><div>>>> print (ind, ), a[ind]<br>(71,) 0.900479032457<br><br><br></div><div>But for larger arrays, this can lead to massive amounts of work even if the result is one of the first to be computed. Example:<br>
<br></div><div>>>> a = np.arange(1e8)<br></div><div>>>> print (a == 5).nonzero()[0][0]<br>5<br></div><div><br></div><div><br></div><div>So a function which terminates when the first matching value is found is desirable. <br>
<br>As mentioned in #2269, it is possible to define a consistent ordering which allows this functionality for >1D arrays, but IMHO it overcomplicates the problem and was not a case that I personally needed, so I've limited the scope to 1D arrays only.<br>
<br><br></div><div><u>Implementation</u><br><br></div><div>My initial assumption was that to get any kind of performance I would need to write the <b>find</b> function in C, however after prototyping with some array chunking it became apparent that a trivial python function would be quick enough for my needs.<br>
<br></div><div>The approach I've implemented in the code found in #2269 simply breaks the array into sub-arrays of maximum length <b>chunk_size</b> (2048 by default, though there is no real science to this number), applies the given predicating function, and yields the results from <b>nonzero()</b>. The given function should be a python function which operates on the whole of the sub-array element-wise (i.e. the function should be vectorized). Returning a generator also has the benefit of allowing users to get the first <b>n</b> matching values/indices.<br>
<br><br></div><div><u>Results</u><br><br><br></div><div>I timed the implementation of <b>find</b> found in my comment at <a href="https://github.com/numpy/numpy/issues/2269#issuecomment-14436725" target="_blank">https://github.com/numpy/numpy/issues/2269#issuecomment-14436725</a> with an obvious test:<br>
</div><div><br><br>In [1]: from np_utils import find<br><br>In [2]: import numpy as np<br><br>In [3]: import numpy.random <br><br>In [4]: np.random.seed(1)<br><br>In [5]: a = np.random.randn(1e8)<br><br>In [6]: a.min(), a.max()<br>
Out[6]: (-6.1194900990552776, 5.9632246301166321)<br><br>In [7]: next(find(a, lambda a: np.abs(a) > 6))<br>Out[7]: ((33105441,), -6.1194900990552776)<br><br>In [8]: (np.abs(a) > 6).nonzero()<br>Out[8]: (array([33105441]),)<br>
<br>In [9]: %timeit (np.abs(a) > 6).nonzero()<br>1 loops, best of 3: 1.51 s per loop<br><br>In [10]: %timeit next(find(a, lambda a: np.abs(a) > 6))<br>1 loops, best of 3: 912 ms per loop<br><br>In [11]: %timeit next(find(a, lambda a: np.abs(a) > 6, chunk_size=100000))<br>
1 loops, best of 3: 470 ms per loop<br><br>In [12]: %timeit next(find(a, lambda a: np.abs(a) > 6, chunk_size=1000000))<br>1 loops, best of 3: 483 ms per loop<br><br><br></div><div>This shows that picking a sensible <b>chunk_size</b> can yield massive speed-ups (nonzero is x3 slower in one case). A similar example with a much smaller 1D array shows similar promise:<br>
<br>In [41]: a = np.random.randn(1e4)<br><br>In [42]: %timeit next(find(a, lambda a: np.abs(a) > 3))<br>10000 loops, best of 3: 35.8 us per loop<br><br>In [43]: %timeit (np.abs(a) > 3).nonzero()<br>10000 loops, best of 3: 148 us per loop<br>
<br><br></div><div>As I commented on the issue tracker, if you think this function is worth taking forward, I'd be happy to open up a pull request.<br><br></div><div>Feedback greatfully received.<br><br></div><div>Cheers,<br>
<br>Phil<br></div><div><br><br></div></div></blockquote><div><br>In the interest of generalizing code and such, could such approaches be used for functions like np.any() and np.all() for short-circuiting if True or False (respectively) are found? I wonder what other sort of functions in NumPy might benefit from this?<br>
<br>Ben Root<br><br></div></div>