假设我有以下字符串:
/Volumes/01/LG_SICARIO_ES419SUB_16X9_240_2398_DIGITAL_FINAL.itt
在给定的输入条件下,如何确定搜索此字符串的最快方法['sicario', '419']
例如,最基本的版本是:
1)字符串包含:
s = '/Volumes/01/LG_SICARIO_ES419SUB_16X9_240_2398_DIGITAL_FINAL.itt'
terms = ['sicario', '419']
has_match = all([term.lower() in s.lower() for term in terms])
2)正则表达式
has_match = all([re.compile(term, re.I).search(s) for term in terms])
其他可能的选择是:
各种算法的时间复杂度是多少?你知道吗
下面是我得到的关于计时regex
和str() in
的结果:
import timeit
# Case insensitive
setup = 's="/Volumes/01/LG_SICARIO_ES419SUB_16X9_240_2398_DIGITAL_FINAL.itt"; terms = ["sicario", "419"]'
print min(timeit.Timer('all([term in s.lower() for term in terms])', setup=setup).repeat(7, 1000))
0.00134181976318
# Case sensitive
setup = 's="/Volumes/01/LG_SICARIO_ES419SUB_16X9_240_2398_DIGITAL_FINAL.itt"; terms = ["sicario", "419"]'
print min(timeit.Timer('all([term in s for term in terms])', setup=setup).repeat(7, 1000))
0.000231027603149
# Regex case insensitive
setup = 'import re; s="/Volumes/01/LG_SICARIO_ES419SUB_16X9_240_2398_DIGITAL_FINAL.itt"; compiled_terms = [re.compile("sicario", re.I), re.compile("419", re.I)]'
print min(timeit.Timer('all([compiled_term.search(s) for compiled_term in compiled_terms])', setup=setup).repeat(7, 1000))
0.00111889839172
# Regex case sensitive
setup = 'import re; s="/Volumes/01/LG_SICARIO_ES419SUB_16X9_240_2398_DIGITAL_FINAL.itt"; compiled_terms = [re.compile("sicario"), re.compile("419")]'
print min(timeit.Timer('all([compiled_term.search(s) for compiled_term in compiled_terms])', setup=setup).repeat(7, 1000))
0.000588893890381
虽然区分大小写的字符串搜索的性能比regex好2倍(至少在这个输入数据上)。你知道吗
我认为您的基本版本是可用的最快的(a combination of Boyer-Moore and Horspoo)(良好情况下的次线性搜索行为(O(n/m)),我将对您的基本版本进行一些小的更改:
相关问题 更多 >
编程相关推荐