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

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

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

我已经在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。

热门问答

在serverless中,我能否自己host 一个express(nodejs)的服务?

Tina

腾讯云 · 产品经理 (已认证)

Go Serverless!
推荐
您好,可以这样的。您可以参考如下文档,申请下http function 您可以使用常见的 WEB 框架(如 Nodejs Web 框架:Express、Koa)编写 HTTP 函数。而 WEB 框架内置的一些中间件(如cors)也会极大的方便您的业务编写 文档链接 https:...... 展开详请

使用有过期时间的签名往Cos存储桶中上传文件,若上传还在进行中签名过期,上传是否会终止?

galenye

腾讯 · 工程师 (已认证)

对象存储专业搬砖工
推荐已采纳

如果你是使用的简单上传,它能接收5g以内的文件,那签名过期的文件还在上传的话,是没影响的,因为签名判断是在cos接受到请求时。

如果你是使用的sdk等封装的分片上传,那其实是多个请求去上传文件,如果签名过期了,那上传到某一刻,后面的请求都会返回403

为何我使用.Net API 生成的临时密钥无法进行文件操作?

推荐
cos有自己的密钥系统,应该是在控制台上,访问管理,API密钥,项目密钥那里,或者去看看cos的文档是如何说明的吧。 你通过ms接口创建cos临时密钥,也许的确会被限制一些,这个需要ms这个产品的人回答下比较好。 生成临时密钥和哪个SDK无关,可以直接在线调用也可以生成,通过AP...... 展开详请

存储桶的默认加速域名 cdn 如何更改业务类型, 即把静态加速改成下载加速?

Jinqn

腾讯 · 高级工程师 (已认证)

腾讯云COS前端开发
推荐

我理解你意思是,浏览器打开的时候要下载,不要直接显示。

通过存储桶的文件 Content-Type 来控制

新版乐加固 不支持 64位应用?

Richel码农
推荐
1.麻烦确认应用自身apk中是否存在64位支持库【应用自身不存在64位支持库的话,加固后是肯定不存在的 2.乐固最新版本已适配arm64位,请更新版本或直接在官网进行加固; 3.乐固目前暂时未支持x86-64位,如需上架GooglePlay,需先删除x86支持 ... 展开详请

树莓派4能够连上腾讯云物联网平台吗?

DylanRichard

腾讯 · 产品经理 (已认证)

万物互联的时代,欢迎来到IoT的世界
推荐

所属标签

扫码关注云+社区

领取腾讯云代金券