专栏首页邵靖的专栏Python 字符串子串定位性能比较
原创

Python 字符串子串定位性能比较

项目最近遇到一个需求:

  1. 给定一组文本文件,每个文本包含若干行,每一行是一条数据记录;
  2. 每一行各字段按照如下方式排布,首先是n个metafield字段,紧接着是最多4个keyfield字段,然后是m个valuefield字段,每个字段用"|"分隔,key从哪个字段开始以及key有几个字段已知metafield_1|metafield_2|...|metafield_n|keyfield_1|...|keyfield_4|valuefield_1|valuefield_2|....|valuefield_m
  3. 任务是对这组文件按keyfields_string除重

除开业务细节,这个任务本质是:

  1. 遍历每个文件的每一行;
  2. 然后截取出keyfield字段集合;
  3. 然后对其进行重复判断;
  4. 最后按照判断结果决定本行是否插入新文件中。

Python很适合完成这种文本处理任务,字符串重复判断这种任务可以使用dict来完成,本文中不做深入探讨。本文想探讨的是在给定了key字段在字段列表中开始下标和key字段个数后,如何在整行字符串中定位到key字符串的起始位置。简而言之,就是确定keyfield_1前一个和keyfield_p后一个“|”字符的位置。

解决这个问题,我想到了三种思路:

  1. 将整个字符串用"|"分割(split),并根据key字段的下标计算首尾两个"|"的位置;
  2. 使用(index/find)函数,通过设置搜索起始位置,按顺序逐个查找"|"字符的位置,直到找到目标“|”位置
  3. 先通过正则表达式或字符串遍历的方式查找出所有"|"的位置生成list,然后根据key字段下标找到目标“|”位置

有同学会说方法1既然每个字段都已经分割开了,将其按照顺序组合就能得到keyfields_string,为何还要查找“|”字符的位置,我想说在这里只是比较在字符串中查找子串的各种方法。

针对以上三个思路,我一共有七种实现,后面会对比其效率:

字符串分割思路

Split

def get_pos_split(line, key_start):
    pos = 0
    tmp_line_list = line.split('|')
    for i in xrange(key_start):
        if i >= len(tmp_line_list):
            return len(line)
        pos += len(tmp_line_list[i]) + 1
    return pos

逐个查找子串位置思路

这个思路我写了三种方法,分别用 index/find来实现,需要注意的是,index函数在未找到子串的情况下会抛出ValueError错误,需要用try except处理,而find在找不到子串的情况下返回-1,两者效率基本一致。并且在查找下一个子串的方式上有少许不同,一种是当找到当前子串位置后,记录下该位置,然后下一次从本次找到的位置+1开始查找,另一种是每找到一个子串,就去掉前缀部分,然后下一次在剩下的字符串中查找。

Find

#使用find查找,记录查找位置,下一次从本次找到的位置+1开始查找
def get_pos_find(line, key_start):
    if key_start == 0: 
        return 0
    pos = line.find('|')
    while pos >= 0 and key_start > 1:
        pos = line.find('|', pos+1)
        key_start -= 1
    return len(line) if pos == -1 else pos+1

Index

#使用index查找,记录查找位置,下一次从本次找到的位置+1开始查找
def get_pos_index(line, key_start):
    pos = 0
    for i in xrange(key_start):
        try:  
            pos = line.index('|', pos+1)
        except ValueError,e:
            return len(line)
    return 0 if pos == 0 else pos+1

Index Cut

#使用index查找,每次找到第一个子串后,就去掉前缀部分,拷贝后缀部分,后续不断在后缀部分查找
def get_pos_index_2(line, key_start):
    tmp_line = line
    pos = 0
    for i in xrange(key_start):
        try:
            pos += tmp_line.index('|')+1
            tmp_line = tmp_line[tmp_line.index('|')+1:]
        except ValueError, e:
            return len(line)
    return pos

定位所有子串思路

针对这个思路,分别使用正则表达式模块,列表推导式以及lambda、map、filter组合方式实现。

  • 正则表达式 re.finditer 方法会返回字符串中所有子串位置的迭代器
  • 列表推倒式将遍历整个字符串并输出子串位置的列表
  • 组合复杂函数的方法,首先用map扫描字符串中所有匹配子串的位置,不匹配的输出-1,再通过filter与lambda函数结合的方式在刚才的结果中过滤掉-1元素

Regex

#通过正则表达式re模块查找匹配所有子串位置
def get_pos_re(line, key_start):
    pos_idx = [p.start() for p in re.finditer('\|', line)]
    return 0 if key_start == 0 else (pos_idx[key_start-1]+1 if key_start <= len(pos_idx) else len(line))

LC

#通过列表推导式(list comprehensions)实现
def get_pos_lc(line, key_start):
    pos_idx = [i for i, x in enumerate(line) if x == '|']
    return 0 if key_start == 0 else (pos_idx[key_start-1]+1 if key_start <= len(pos_idx) else len(line))

Filter

#通过 lambda、map、filter 组合实现
def get_pos_filter(line, key_start):
    def func_in(t):
        return t[0] if t[1] == '|' else -1
    pos_idx = filter(lambda x: x!=-1, map(func_in, enumerate(line)))
    return 0 if key_start == 0 else (pos_idx[key_start-1]+1 if key_start <= len(pos_idx) else len(line))

测试对比

首先,测试在相同单条记录,不同的记录条数条件下,各种方法的耗时,结果如上图所示。

然后,测试在记录条数一定,不同记录长度条件下,各种方法耗时,结果如上图所示。

第三,测试在相同单条记录,相同记录条数情况下取不同位置的字段各种方法耗时,结果如上图所示。

结论

通过测试对比可以看到,字符串分割逐个查找子串位置的思路在总体上都比定位所有子串位置的思路效率更高。

逐个查找子串位置思路中通过find和index定位子串位置的效率最高,拆分子串的方式次之。影响性能的因素是单条记录长度以及所需要查找的字段位置。

字符串分割,影响性能的因素是单条记录长度以及所需要查找的字段位置。

定位所有子串因为要定位到每个字段的位置,相当于扫描全数据,所以效率最低。在这个思路的三种方法中,正则表达式的实现效率最高,其他两种效率都很差。

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 一个基于 Docker 的负载均衡实例

    本文目地主要是给大家简单安利一下目前最火的容器产品 Docker 及其所涉及的相关技术,并通过一个实际例子演示一下容器技术的典型应用场景。

    邵靖
  • GlusterFS的数据分布(DHT)和文件副本(AFR)机制

    GlusterFS是一种分布式文件系统,项目中使用它作为数据文件冷备存储后台。GlusterFS的技术特点是采用无元数据中心的架构,采用Xlator以调用栈的形...

    邵靖
  • 使用 plotly 绘制数据图表

    不少小伙伴在开发过程中都有对模块进行压测的经历,压测结束后大家往往喜欢使用Excel处理压测数据并绘制数据可视化视图,但这样不能很方便的使用web页面进行数据展...

    邵靖
  • DDD的终极大招——By Experience | 洞见

    以DDD思想和微服务架构为代表的新的架构时代正在逐步形成,不同方法和工具的涌现让人激动不已,同时这个过程也让人感觉到些许的不安,因为没有一套方法和一套架构能够打...

    ThoughtWorks
  • 调用快递鸟电子面单API实现打印电子面单接口 C#

    老杨占线
  • Pown-CDB:用于自动化执行Chrome调试协议任务的工具

    Pown CDB是一个Chrome调试协议实用程序。该工具的主要目标是将一些常见任务自动化的执行,以帮助从命令行调试Web应用,并主动监视和拦截HTTP请求和响...

    FB客服
  • 为什么我强烈推荐你使用 IDEA,放弃 Eclipse?

    来源:https://www.cnblogs.com/ouyida3/p/9901312.html

    开发者技术前线
  • 财报断崖式下跌 鼎捷未来何处寻路?

    ERP风光不再,业绩下滑加速转型成为ERP厂商当前的头等大事儿,虽然前些年都有试水尝试,但始终没有摘掉传统软件的帽子,近两年各家财报成为跳水大赛,国内知名的管理...

    人称T客
  • 鼎捷软件中期财报解读:制造业冬眠无期 鼎捷急需另择新路

    这两天网友不断发来各家中期财报让我解读,我仅以我个人视角不代表其它人的观点,同时也避免口水战。今天我们来解读一下专注制造业ERP解决方案厂商鼎捷软件。 鼎捷软...

    人称T客
  • 基于OpenCV的条形码区域分割

    本期,我们将一起学习如何从图像中提取出含有条形码的区域。下面的代码,我们将在Anaconda中采用Python 2.7 完成,当然OpenCV中的图像处理库也是...

    AI算法与图像处理

扫码关注云+社区

领取腾讯云代金券