numpy/numpy — pull request #4184 by jaimefrio (2014-01-10 18:20:11+00:00)
Title: ENH: change `np.digitize` to use binary search

Currently `np.digitize` uses a linear search to bin the input values, this
PR provides two different implementations of the same functionality using
binary search:

`np.new_digitize` is a pure Python function that replicates the functionality
of `np.digitize`, but calls `np.searchsorted` to perform the binning. While
it outperforms the current `np.digitize` for inputs with many bins, it can be
(much) slower for inputs with less than ~200 bins.

`np.bindigitize` is a modification of the C code, which replaces the current
binning functions with binary search equivalents, which are heavily leveraged
from the corresponding C functions of `np.searchsorted`. It appears to always
outperform `np.digitize`.

If this PR is accepted, only one of the two new functions would remain (I
think `np.bindigitize` should be it) and be renamed to the current
`np.digitize`.