为什么Python内置的二分查找函数运行速度更快？

Question

（已由sharth的评论回答。）

我在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实现覆盖上述定义” - 这是什么解释了这种差异吗？如果是这样，我该如何创建这样的预编译模块呢？

非常感谢您的任何建议。

- advert2013

---

http://docs.python.org/2/extending/index.html - Ignacio Vazquez-Abrams

“这是否解释了差异？” “是的。” - roippi

你可以尝试使用像PyPy这样的JIT编译器 - 我相信你的代码将在此上运行得更快，但会牺牲一些模块的可用性。 - Benjamin Gruenbaum

以下是 _bisect 的 C 代码：http://hg.python.org/cpython/file/0199bff14c5c/Modules/_bisectmodule.c - Bill Lynch

“我该如何创建这样一个预编译模块？”-- 你可以尝试使用Cython（一个类似于Python的语言，用于为CPython创建C扩展）。pyximport 可以实时编译扩展（用于开发）。 - jfs

Answer 1

为了总结上面的评论以便关闭问题，内置模块更快的原因是因为这些模块在C中预编译。基本上有两种尝试复制这种性能的选项，一种是使用像PyPy这样的JIT编译器，在运行时进行编译，另一种是使用Cython或其他变体将自己的模块编译成C代码，以将C代码与Python集成。sharth提供的链接到bisect的C代码特别有帮助，可以在此处找到这里。再次感谢所有的帮助。

- advert2013

---

请为了未来读者的需求，包含一个实际答案的概括在此处。因为你现在的评论并不是一个答案。 - FThompson

完成。是的，我不确定当问题在评论中得到答案时应该做什么，希望这个总结可以吧。明天让我关闭这个问题时我会这样做。 - advert2013