1

所以，我有一个正则表达式模式列表和一个字符串列表，我想做的是在这个字符串列表中说，是否有任何字符串不匹配任何正则表达式。

目前，我正在从两个字典中提取正则表达式以及正则表达式要匹配的值：

我从两个字典中制作了两个列表，一个模式，一个键：

patterns = []
keys = []
for pattern, schema in patternproperties.items():
    patterns.append(pattern)
for key, value in value_obj.items():
    keys.append(key)

# Now work out if there are any non-matching keys

for key in keys:
    matches = 0
    for pattern in patterns:
        if re.match(pattern, key):
            matches += 1
    if matches == 0:
        print 'Key %s matches no patterns' %(key)

但这似乎非常低效。任何人都可以找到更好的解决方案吗？

4

3 回答 3

3

正则表达式针对搜索大块文本而不是小块序列进行了优化。因此，您可能需要考虑搜索'\n'.join(keys)而不是单独搜索每一个。

或者，或者，不是将循环从 Python 移动到正则表达式，而是将隐式的“或”/“任何”位从 Python 移动到正则表达式：

pattern = re.compile('|'.join('({})'.format(p) for p in patterns))    
for key in keys:
    if not pattern.match(key):
        print 'Key %s matches no patterns' %(key)

另外，请注意我使用了re.compile. 由于自动正则表达式缓存，这可能无济于事……但它永远不会受到伤害，而且它通常也使代码更易于阅读。

通过快速timeit测试，键列表和简单模式的数量不同：

patterns   original   alternation
2          76.1 us    42.4 us
3          109 us     42.5 us
4          143 us     43.3 us

因此，我们已经从模式数量的线性变为几乎恒定。

当然，这不会支持更复杂的模式，或者太多的模式。

于 2013-07-12T18:41:01.377 回答
2 
[key for key in keys if not any(re.match(pattern, key) for pattern in patterns)]
于 2013-07-12T18:32:33.800 回答
0

您可以通过多种方式对此进行优化。基本算法是合理的，所以你有一些选择：

  • 如果有匹配项，请尽早跳出循环（而不是计算匹配的数量，您不关心）。
  • 缓存正则表达式的编译（如果你有很多模式）。
  • 对正则表达式进行排序，以便将倾向于快速匹配的表达式排在第一位。这种方式将使您的提前终止获得最大的收益。
  • 使用列表推导，它可能比手动迭代更快（并且可能有一天允许 Python 解释器并行化，尽管今天可​​能不会）。虽然它不一定更容易阅读。（请参阅使用列表推导更好还是使用每个循环来获得一些意见。）

一种不同的算法可能是首先对模式进行迭代，并在一个模式匹配后立即从潜在键集中删除一些东西。就像是：

remainder = set(keys)
for pattern in patterns:
    toremove = set()
    for key in remainder:
        if re.match(pattern, key):
            toremove.add(key)
    remainder -= toremove

如果您有一个匹配很多键的模式，这可能会有所帮助。

您当然应该根据您的情况和输入进行衡量，以确定哪些优化是最合适的。

于 2013-07-12T18:56:25.213 回答