python bisect 比 numpy.searchsorted 快吗？

Question

我很惊讶地发现 python 的bisect.bisect_left比 numpy 等效的numpy.searchsorted更快。这与我使用的值的分布有关还是对于任何输入都如此？

\n

>>> input_size = 10**3\n>>> input_list = sorted([random.uniform(0, 300) for _ in range(input_size)])\n>>> numpy_input = np.array(input_list)\n\n>>> %timeit index = bisect.bisect_left(input_list, 100)\n434 ns \xc2\xb1 6.17 ns per loop (mean \xc2\xb1 std. dev. of 7 runs, 1000000 loops each)\n\n>>> %timeit index = np.searchsorted(numpy_input, 100)\n1.8 \xc2\xb5s \xc2\xb1 21.8 ns per loop (mean \xc2\xb1 std. dev. of 7 runs, 1000000 loops each)\n

\n

Python 的版本为 3.8.0，numpy 的版本为 1.18.4。

\n

Answer 1

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

\n

调用searchsorted整个元素数组来查找比bisect_left在循环中一次调用一个元素要快：

\n

In [1]: import numpy\n\nIn [2]: import bisect\n\nIn [3]: numpy_haystack = numpy.arange(300)\n\nIn [4]: list_haystack = numpy_haystack.tolist()\n\nIn [5]: numpy_needles = numpy.arange(5, 150, 3)\n\nIn [6]: list_needles = numpy_needles.tolist()\n\nIn [7]: %timeit numpy.searchsorted(numpy_haystack, numpy_needles)\n2.39 \xc2\xb5s \xc2\xb1 71.2 ns per loop (mean \xc2\xb1 std. dev. of 7 runs, 100000 loops each)\n\nIn [8]: %%timeit\n   ...: for needle in list_needles:\n   ...:     bisect.bisect_left(list_haystack, needle)\n   ...:\n18.4 \xc2\xb5s \xc2\xb1 1.48 \xc2\xb5s per loop (mean \xc2\xb1 std. dev. of 7 runs, 100000 loops each)\n

\n