检查字符串是否以一组字符串之一开头的有效方法

Question

我需要匹配一个字符串,以查看它是否以大约40个字符串中的一个开头,并且这个方法被称为很多.

目前确实如此

for pref, newval in list_of_prefixes:
    if oldval.startswith(pref):
         return newval
return oldval

然而,鉴于它被称为很多次,因此尽可能高效是有道理的.我可以确保list_of_prefixes被排序,然后在pref> oldval之后立即退出循环,但这似乎没有太大的收获.

目前,最大数量的输入值介于两个前缀之间,所以我可以明确地测试它,或者以相反的顺序搜索,但是虽然这对于现在的数据集是有效的,但是如果数据集改变则可能效率较低.

最初,只有一个可能的前缀,因此性能可能不是一个问题.

我看了一下string.startswith(tuple()),但这似乎只是为了让它更容易编写,并且它不会告诉我哪个元组匹配,所以在有匹配的地方我必须做两次检查.

Answer 1

使用已编译的正则表达式,我预计编译正则表达式的开销会在您拥有多个字符串时自行回报.基本上,编译的正则表达式是一个自动机,如果前缀不是自动机识别的前缀,它可以很快地用完可遍历的路径.特别是如果所有匹配都锚定到字符串的开头,那么当没有匹配时它会很快失败.

import re

prefixes = ['foo', 'bar', 'baz']
rx = re.compile(''.join(['^(?:', '|'.join(prefixes), ')']))
for line in input:
    match = rx.match(line)
    if match:
        matched = match.group(0)

如果您需要更复杂的正则表达式(例如,在右括号后具有尾随上下文的表达式),您将需要使用常规分组括号(而不是非分组(?:,而是使用fetch group(1).

以下是替换字典映射前缀:

prefixes = {'foo': 'nu', 'bar': 'beer', 'baz': 'base'}
rx = re.compile(''.join(['^(?:', '|'.join(prefixes.keys()), ')']))
for line in input:
    match = rx.match(line)
    if match:
        newval = prefixes[match.group(0)]

实际上,正如评论中指出的那样,^并非绝对必要re.match().