[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