[NumPy-Tickets] [NumPy] #2064: numpy.digitize uses a linear search when it should be using binary search
NumPy Trac
numpy-tickets@scipy....
Sat Feb 25 09:47:41 CST 2012
#2064: numpy.digitize uses a linear search when it should be using binary search
--------------------+-------------------------------------------------------
Reporter: jpeel | Owner: somebody
Type: defect | Status: new
Priority: normal | Milestone: Unscheduled
Component: Other | Version: 1.6.1
Keywords: |
--------------------+-------------------------------------------------------
In numpy/lib/src/_compiled_base.c, numpy.digitize's code uses linear
searches rather than binary searches as it should. The difference in speed
is quite enormous when using very many bins. Quite frankly, it should
probably use searchsorted after checking that the bins are monotonic.
This was opened as a result of a question on stackoverflow
[http://stackoverflow.com/questions/9444409/why-is-numpy-much-slower-than-
matlab-on-a-digitize-example/9445500#9445500]
You can see an example of the speed issue there.
--
Ticket URL: <http://projects.scipy.org/numpy/ticket/2064>
NumPy <http://projects.scipy.org/numpy>
My example project
More information about the NumPy-Tickets
mailing list