(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实现覆盖上面的定义”--这是解释差异的原因吗?如果是这样,我该如何创建这样一个预编译的模块呢?
任何建议都是非常感谢的。
发布于 2014-02-23 05:40:14
总结上面的话以便结束这个问题,内置模块更快的原因是因为模块是用c预编译的。基本上有两个选项可以尝试复制这样的性能,一个是使用PyPy这样的即时编译器,其中编译是在运行时完成的,另一个是使用C语言编译自己的模块,使用Cython或其他变体将C代码与python集成。从上面的sharth到二等分的c代码的链接特别有用,可以在here中找到。再次感谢你的帮助。
https://stackoverflow.com/questions/21948404
复制相似问题