如何在Python中高效地对反向排序列表进行二分搜索

我想在Python语言中对反向排序的列表进行二进制搜索.列表是以相反的顺序追加的，它必须是这样的，否则我的代码就会崩溃.

我需要的代码是尽可能快，假设名单是巨大的.我知道Python代码很慢，所以代码必须编译.我知道标准库中的bisect模块导入了预编译的_bisect模块，如果找到的话，_bisect是用C实现的，这是非常快的.

然而，它在反向排序列表上不起作用，我try 了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

我从安装的文件中复制了代码并对其进行了修改:

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

将x < a[mid]更改为x > a[mid]将使其在反向排序列表上工作.

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

正如预期的那样，未编译的代码比预编译的代码慢得多.还要注意，我不能比较reverse_bisect和_bisect.bisect的性能，因为后者在这种情况下不能正常工作.

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)

所以我try 使用numba.jit来编译函数，我将@numba.jit(nopython=True, fastmath=True, cache=True, forceobj=False)添加到bisect_right之前的行，生成bisect_right_nb，但是bisect_right_nb给了我一个警告，结果是105:

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'.

For more information visit https://numba.readthedocs.io/en/stable/reference/deprecation.html#deprecation-of-reflection-for-list-and-set-types

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_right的性能呢？

不，我已经读了这个answer，我不是想把元素插入到列表中，我是想go 掉所有小于它的元素.

(而且我的网络连接不稳定，我的互联网服务Provider 中断了我的VPN连接，所以我的更新花了很长时间.)