如何在Python中高效对倒序排序列表进行二分查找？

我需要在Python中对倒序排序的列表执行二分查找，且列表必须保持倒序结构（否则现有代码会出错）。由于列表规模极大，要求代码尽可能高效，希望使用编译后的代码。

已知标准库bisect模块依赖预编译的C实现_bisect，性能极佳，但它无法处理倒序排序的列表，尝试用key=lambda x: -x也失败了：

In [51]: l = range(50, 0, -5)

In [52]: from bisect import bisect

In [53]: bisect(l, 18, key=lambda x: -x)
Out[53]: 10

我复制了bisect模块的源码并修改，将判断条件x < a[mid]改为x > a[mid]，得到了能处理倒序列表的reverse_bisect函数：

# 原bisect_right实现
def bisect_right(a, x):
    lo, hi = 0, len(a)
    while lo < hi:
        mid = (lo + hi) // 2
        if x < a[mid]:
            hi = mid
        else:
            lo = mid + 1
    return lo

# 修改后的倒序二分查找
def reverse_bisect(a, x):
    lo, hi = 0, len(a)
    while lo < hi:
        mid = (lo + hi) // 2
        if x > a[mid]:
            hi = mid
        else:
            lo = mid + 1
    return lo

但纯Python实现的性能远不如预编译代码：

In [55]: %timeit bisect(range(0, 10**7, 10), 4096)
2.91 µs ± 97.3 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)

In [56]: %timeit bisect_right(range(0, 10**7, 10), 4096)
5.22 µs ± 87.9 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)

我尝试用numba.jit编译函数，但不仅出现警告，性能反而暴跌六个数量级：

In [59]: @numba.jit(nopython=True, fastmath=True, cache=True, forceobj=False)
    ...: def bisect_right_nb(a: list, x: int):
    ...:     lo, hi = 0, len(a)
    ...:     while lo < hi:
    ...:         mid = (lo + hi) // 2
    ...:         if x < a[mid]:
    ...:             hi = mid
    ...:         else:
    ...:             lo = mid + 1
    ...:     return lo

In [60]: l = list(range(0, 10**7, 10))

In [61]: %timeit bisect_right_nb(l, 4096)
C:\Python310\lib\site-packages\numba\core\ir_utils.py:2149: NumbaPendingDeprecationWarning:
Encountered the use of a type that is scheduled for deprecation: type 'reflected list' found for argument 'a' of function 'bisect_right_nb'.

File "<ipython-input-59-23a3cb61146c>", line 2:
@numba.jit(nopython=True, fastmath=True, cache=True, forceobj=False)
def bisect_right_nb(a: list, x: int):
^

  warnings.warn(NumbaPendingDeprecationWarning(msg, loc=loc))
1.66 s ± 11.2 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

In [62]: 1.66*10**6/5.22
Out[62]: 318007.66283524904

请问如何提升reverse_bisect函数的性能？另外，我并非要向列表中插入元素，而是要移除所有比目标值小的元素。

1. 修复Numba编译问题 #

Numba性能暴跌是因为传入了Pythonlist类型，触发了已弃用的反射机制。改用Numba原生支持的numpy数组作为输入，能直接编译为高效机器码：

import numba
import numpy as np

@numba.jit(nopython=True, fastmath=True, cache=True)
def reverse_bisect_numba(a: np.ndarray, x: int):
    lo, hi = 0, len(a)
    while lo < hi:
        mid = (lo + hi) // 2
        if x > a[mid]:
            hi = mid
        else:
            lo = mid + 1
    return lo

# 使用示例
arr = np.arange(0, 10**7, 10)[::-1]  # 生成倒序numpy数组
reverse_bisect_numba(arr, 4096)

这种实现的性能接近bisect模块的C级水平，numpy数组的连续内存布局也更适合快速随机访问。

2. 复用bisect模块的优化逻辑 #

不用手动修改源码，通过键转换间接利用bisect的预编译实现：

from bisect import bisect_right

def reverse_bisect_indirect(a, x):
    # 倒序列表等价于正序列表元素取反，对x取反后复用bisect_right的逻辑
    return bisect_right(a, x, key=lambda val: -val)

注意：Python 3.10及以上版本的bisect才支持key参数。如果使用更低版本，可手动实现键转换逻辑，避免生成额外键列表浪费内存：

from bisect import bisect_right

def reverse_bisect_indirect_pre310(a, x):
    lo, hi = 0, len(a)
    while lo < hi:
        mid = (lo + hi) // 2
        # 等价于比较 -x 和 -a[mid]，对齐正序bisect的逻辑
        if -x < -a[mid]:
            hi = mid
        else:
            lo = mid + 1
    return lo

这种方法的纯Python实现性能也会优于手动编写的reverse_bisect。

3. Cython编译实现极致性能 #

如果Numba方案仍无法满足需求，可使用Cython编写原生C级别的二分查找：

# reverse_bisect.pyx
def reverse_bisect_cython(list a, int x):
    cdef int lo = 0
    cdef int hi = len(a)
    cdef int mid
    while lo < hi:
        mid = (lo + hi) // 2
        if x > a[mid]:
            hi = mid
        else:
            lo = mid + 1
    return lo

编译后的函数性能与_bisect模块的原生C实现基本一致。

针对业务场景的优化（移除小于目标值的元素） #

由于列表是倒序的，所有小于x的元素都在reverse_bisect返回索引的右侧，直接切片即可完成操作：

# 列表场景
cut_idx = reverse_bisect(a, x)
result = a[:cut_idx]

# numpy数组场景（更高效）
cut_idx = reverse_bisect_numba(arr, x)
result = arr[:cut_idx]

内容的提问来源于stack exchange，提问作者Ξένη Γήινος