用于全文匹配的各种搜索算法和性能

2024-03-28 10:29:31 发布

您现在位置:Python中文网/ 问答频道 /正文

假设我有以下字符串:

/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])

其他可能的选择是:

各种算法的时间复杂度是多少?你知道吗


下面是我得到的关于计时regexstr() 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倍(至少在这个输入数据上)。你知道吗


Tags: inresetupallittfinaltermterms
1条回答
网友
1楼 · 发布于 2024-03-28 10:29:31

我认为您的基本版本是可用的最快的(a combination of Boyer-Moore and Horspoo)(良好情况下的次线性搜索行为(O(n/m)),我将对您的基本版本进行一些小的更改:

def test():
    lower_s = s .lower()
    return all([term in lower_s for term in terms])

相关问题 更多 >