为什么 Numba 不改进这个递归函数

我有一个结构非常简单的真/假值数组：

# the real array has hundreds of thousands of items
positions = np.array([True, False, False, False, True, True, True, True, False, False, False], dtype=np.bool)

我想遍历这个数组并输出发生变化的地方（true 变为 false 或相反）。为此，我总结了两种不同的方法：

• 递归二分搜索（查看所有值是否相同，如果不同，则分成两部分，然后递归）
• 纯粹的迭代搜索（循环遍历所有元素并与上一个/下一个元素进行比较）

两个版本都给出了我想要的结果，但是 Numba 对其中一个版本的影响比另一个版本更大。对于包含 300k 值的虚拟数组，以下是性能结果：

300k 元素数组的性能结果

• 纯 Python 二分搜索运行时间为 11 毫秒
• 纯 Python 迭代搜索在 1.1 秒内运行（比二分查找慢 100 倍）
• Numba 二分搜索在 5 毫秒内运行（比纯 Python 快 2 倍）
• Numba 迭代搜索在 900 µs 内运行（比纯 Python 快 1,200 倍）

因此，使用 Numba 时，binary_search 比 iterative_search 慢 5 倍，而理论上它应该快 100 倍（如果适当加速，预计运行时间为 9 µs）。

如何才能使 Numba 加速二分搜索的速度与加速迭代搜索的速度一样快？

两种方法的代码（以及示例positionarray) 可以在这个公共要点上找到：https://gist.github.com/JivanRoquet/d58989aa0a4598e060ec2c705b9f3d8f

注意：Numba 未运行binary_search()在对象模式下，因为当提到nopython=True，它不会抱怨并愉快地编译该函数。

您可以使用以下方法找到值变化的位置np.diff，不需要运行更复杂的算法，或者使用numba:

positions = np.array([True, False, False, False, True, True, True, True, False, False, False], dtype=np.bool)
dpos = np.diff(positions)
# array([ True, False, False,  True, False, False, False,  True, False, False])

这有效，因为False - True == -1 and np.bool(-1) == True.

它在我的电池供电（=由于节能模式而节流）和几年前的笔记本电脑上表现得很好：

In [52]: positions = np.random.randint(0, 2, size=300_000, dtype=bool)          

In [53]: %timeit np.diff(positions)                                             
633 µs ± 4.09 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

我想象写你自己的差异numba应该产生类似的性能。

编辑：最后一个语句是错误的，我使用实现了一个简单的 diff 函数numba，并且比速度快 10 倍以上numpy一个（但它的功能显然也少得多，但对于这项任务来说应该足够了）：

@numba.njit 
def ndiff(x): 
    s = x.size - 1 
    r = np.empty(s, dtype=x.dtype) 
    for i in range(s): 
        r[i] = x[i+1] - x[i] 
    return r

In [68]: np.all(ndiff(positions) == np.diff(positions))                            
Out[68]: True

In [69]: %timeit ndiff(positions)                                               
46 µs ± 138 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)