python - python bisect 比 numpy.searchsorted 快吗？

Question

我很惊讶地看到 python 的 bisect.bisect_left比 numpy 等价物快 numpy.searchsorted .这是否与我使用的值的分布有关，或者这对任何输入都适用吗？

>>> 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 的版本是 3.8.0，numpy 的版本是 1.18.4。

Answer 1

这里的问题是您一次进行一次查找。一次一个标量并不是使用 NumPy 的有效方式。

用一整组元素调用searchsorted比在循环中一次用一个元素调用bisect_left更快:

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)