为什么Numba无法改善此递归功能

Question

我有一个具有非常简单结构的true / false值数组：

# 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值的虚拟数组，以下是性能结果：

具有30万个元素的数组的性能结果

• 纯Python二进制搜索在11毫秒内运行
• 纯Python迭代搜索的运行时间为1.1秒（比二进制搜索慢100倍）>
• Numba二进制搜索在5毫秒内运行（（比纯Python快2倍）
• Numba迭代搜索的运行时间为900 µs （比纯Python快1200倍）]] >>

因此，使用Numba时，binary_search的速度比iterative_search慢5倍，而从理论上讲，它应该快100倍（如果得到适当的加速，则有望在9 µs内运行）。

如何使Numba加速二分搜索和加速迭代搜索？

这两种方法的代码（以及示例position数组）在此公共要点上均可用：https://gist.github.com/JivanRoquet/d58989aa0a4598e060ec2c705b9f3d8f

注：Numba不在对象模式下运行binary_search()，因为提及nopython=True时，它不会抱怨并很高兴地编译该函数。

我有一个具有非常简单结构的true / false值数组：＃实际数组具有成千上万个项目position = np.array（[True，False，False，False，True，True，True，True， False，...

要点是，只有使用Python机制的逻辑部分可以被加速-通过用等效的C逻辑替换它，可以消除Python运行时的大部分复杂性（和灵活性）（我想这就是Numba所做的）。

NumPy操作中所有繁重的工作已经在C语言中实现并且非常简单（因为NumPy数组是存储常规C类型的连续内存块，因此Numba只能剥离与Python机器接口的部分。

您的“二进制搜索”算法在完成此工作时会做更多的工作，并且会大量使用NumPy的矢量运算，因此可以通过这种方式来加速执行。

主要问题是您没有执行苹果对苹果的比较。您提供的不是同一算法的迭代版本和递归版本。您正在提出两种根本不同的算法，它们恰好是递归/迭代的。

特别是您在递归方法中使用了更多的NumPy内置函数，因此，难怪这两种方法之间存在如此惊人的差异。当您避免使用NumPy内置组件时，Numba JITting更有效也就不足为奇了。最终，递归算法似乎效率较低，因为np.all()和np.any()调用中有一些hidden

嵌套循环，因此避免了迭代方法，因此即使您要纯写所有代码，使用Numba可以更有效地加速Python，而递归方法会更慢。

通常，迭代方法比递归equivalent

更快，因为它们避免了函数调用开销（与纯Python相比，JIT加速函数的开销最小）。因此，我建议不要尝试以递归形式重写算法，以免发现它比较慢。

Answer 1

要点是，只有使用Python机制的逻辑部分可以被加速-通过用等效的C逻辑替换它，可以消除Python运行时的大部分复杂性（和灵活性）（我想这就是Numba所做的）。

Answer 2

主要问题是您没有执行苹果对苹果的比较。您提供的不是同一算法的迭代版本和递归版本。您正在提出两种根本不同的算法，它们恰好是递归/迭代的。

特别是您在递归方法中使用了更多的NumPy内置函数，因此，难怪这两种方法之间存在如此惊人的差异。当您避免使用NumPy内置组件时，Numba JITting更有效也就不足为奇了。最终，递归算法似乎效率较低，因为np.all()和np.any()调用中有一些hidden

嵌套循环，因此避免了迭代方法，因此即使您要纯写所有代码，使用Numba可以更有效地加速Python，而递归方法会更慢。