Is python bisect faster than numpy.searchsorted?

user_1720199 0
Viewed 744

I was surprised to see that python's bisect.bisect_left was faster than the numpy equivalent numpy.searchsorted. Is that related to the distribution of values I used or will this remain true for any input?

>>> input_size = 10**3
>>> input_list = sorted([random.uniform(0, 300) for _ in range(input_size)])
>>> numpy_input = np.array(input_list)

>>> %timeit index = bisect.bisect_left(input_list, 100)
434 ns ± 6.17 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

>>> %timeit index = np.searchsorted(numpy_input, 100)
1.8 µs ± 21.8 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

Python is on version 3.8.0 and numpy on version 1.18.4.

python-3.x numpy python
1 Answers

The problem here is that you're doing one lookup at a time. One scalar at a time is not an efficient way to use NumPy.

Calling searchsorted with an entire array of elements to find is faster than calling bisect_left with one element at a time in a loop:

In [1]: import numpy

In [2]: import bisect

In [3]: numpy_haystack = numpy.arange(300)

In [4]: list_haystack = numpy_haystack.tolist()

In [5]: numpy_needles = numpy.arange(5, 150, 3)

In [6]: list_needles = numpy_needles.tolist()

In [7]: %timeit numpy.searchsorted(numpy_haystack, numpy_needles)
2.39 µs ± 71.2 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

In [8]: %%timeit
   ...: for needle in list_needles:
   ...:     bisect.bisect_left(list_haystack, needle)
   ...:
18.4 µs ± 1.48 µs per loop (mean ± std. dev. of 7 runs, 100000 loops each)
user_23571120
Related