Python 字符串子串定位性能比较
原创
项目最近遇到一个需求：
- 给定一组文本文件，每个文本包含若干行，每一行是一条数据记录；
- 每一行各字段按照如下方式排布，首先是n个metafield字段，紧接着是最多4个keyfield字段，然后是m个valuefield字段，每个字段用"|"分隔，key从哪个字段开始以及key有几个字段已知
metafield_1|metafield_2|...|metafield_n|keyfield_1|...|keyfield_4|valuefield_1|valuefield_2|....|valuefield_m - 任务是对这组文件按keyfields_string除重
除开业务细节，这个任务本质是：
- 遍历每个文件的每一行；
- 然后截取出keyfield字段集合；
- 然后对其进行重复判断；
- 最后按照判断结果决定本行是否插入新文件中。
Python很适合完成这种文本处理任务，字符串重复判断这种任务可以使用dict来完成，本文中不做深入探讨。本文想探讨的是在给定了key字段在字段列表中开始下标和key字段个数后，如何在整行字符串中定位到key字符串的起始位置。简而言之，就是确定keyfield_1前一个和keyfield_p后一个“|”字符的位置。
解决这个问题，我想到了三种思路：
- 将整个字符串用"|"分割（split），并根据key字段的下标计算首尾两个"|"的位置；
- 使用（index/find）函数，通过设置搜索起始位置，按顺序逐个查找"|"字符的位置，直到找到目标“|”位置
- 先通过正则表达式或字符串遍历的方式查找出所有"|"的位置生成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定位子串位置的效率最高，拆分子串的方式次之。影响性能的因素是单条记录长度以及所需要查找的字段位置。
字符串分割，影响性能的因素是单条记录长度以及所需要查找的字段位置。
定位所有子串因为要定位到每个字段的位置，相当于扫描全数据，所以效率最低。在这个思路的三种方法中，正则表达式的实现效率最高，其他两种效率都很差。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。