为什么python内置的二进制搜索函数运行得更快?

内容来源于 Stack Overflow,并遵循CC BY-SA 3.0许可协议进行翻译与使用

  • 回答 (1)
  • 关注 (0)
  • 查看 (39)

我已经在python中编写了一个二进制搜索算法,或多或少遵循与在bisect模块中找到的bisect_left函数相同的结构。事实上,它有少两个条件,因为我知道高点是列表的长度,低点是0.然而,由于某种原因,内置函数的运行速度是我的速度的5倍。

我的代码如下:

def bisection_search(word, t):

    high = len(t)
    low = 0

    while low < high:
        half = (high+low)/2
        if t[half] < word:
            low = half + 1
        else:
            high = half
    return low

内置函数的源代码是:

def bisect_left(a, x, lo=0, hi=None):
    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        if a[mid] < x: lo = mid+1
        else: hi = mid
    return lo

正如你所看到的,几乎完全相同。然而,对于我的功能(搜索最后一个词的有序列表中的100,000个单词)超时为-3.60012054443e-05,其中内置达到-6.91413879395e-06。什么解释了这种差异?

提问于
用户回答回答于

内置模块更快的原因是因为模块在c中被预编译。基本上有两种选择来尝试复制这样的性能,一种是使用JIT编译器,如PyPy,其中编译是在运行时完成的,另一种是使用Cython或其他某些变体来编译自己的模块以集成C代码与Python。

扫码关注云+社区

领取腾讯云代金券