Python的bisect函数比numpy中的searchsorted函数更快吗？

Question

Python的bisect函数比numpy中的searchsorted函数更快吗？

3

我惊讶地发现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。

- cglacet

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- user2357112 · Accepted Answer

这里的问题是您一次只查找一个标量。逐个标量查找不是使用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)