为什么python内置的二进制搜索函数运行得这么快？
为什么python内置的二进制搜索函数运行得这么快？
提问于 2014-02-22 09:27:07
(sharth的评论已经对此做出了回应。)
我用Python语言编写了一个二进制搜索算法，它的结构与在二等分模块中找到的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如你所见，它们几乎是一样的。但是，my函数(在100,000个单词的有序列表中搜索最后一个词)的超时put是-3.60012054443e-05，其中内置的是-6.91413879395e-06。如何解释这种差异？
在source code的末尾有一条注释，说“用快速的C实现覆盖上面的定义”--这是解释差异的原因吗？如果是这样，我该如何创建这样一个预编译的模块呢？
任何建议都是非常感谢的。
回答 1
Stack Overflow用户
回答已采纳
发布于 2014-02-23 05:40:14
总结上面的话以便结束这个问题，内置模块更快的原因是因为模块是用c预编译的。基本上有两个选项可以尝试复制这样的性能，一个是使用PyPy这样的即时编译器，其中编译是在运行时完成的，另一个是使用C语言编译自己的模块，使用Cython或其他变体将C代码与python集成。从上面的sharth到二等分的c代码的链接特别有用，可以在here中找到。再次感谢你的帮助。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/21948404
复制相关文章
相似问题