15

我有一个函数，如果字符串与列表中的至少一个正则表达式匹配，则返回 True，否则返回 False。该函数经常被调用，以至于性能是一个问题。

当通过 cProfile 运行它时，该函数大约 65% 的时间用于匹配，35% 的时间用于遍历列表。

我认为会有一种使用 map() 或其他东西的方法，但我想不出一种方法让它在找到匹配项后停止迭代。

有没有办法让函数更快，同时在找到第一个匹配项时仍然返回？

def matches_pattern(str, patterns):
    for pattern in patterns:
        if pattern.match(str):
            return True
    return False
4

4 回答 4

24

首先想到的是使用生成器表达式将循环推到 C 端：

def matches_pattern(s, patterns):
    return any(p.match(s) for p in patterns)

可能您甚至不需要单独的功能。

您应该尝试的另一件事是使用交替运算符构建单个复合正则表达式|，以便引擎有机会为您优化它。如果有必要，您还可以从字符串模式列表动态创建正则表达式：

def matches_pattern(s, patterns):
    return re.match('|'.join('(?:%s)' % p for p in patterns), s)

当然，您需要以字符串形式使用正则表达式才能使其正常工作。只需分析这两个并检查哪个更快:)

您可能还想查看在 Python 中调试正则表达式的一般技巧。这也有助于找到优化的机会。

更新：我很好奇并写了一个小基准：

import timeit

setup = """
import re
patterns = [".*abc", "123.*", "ab.*", "foo.*bar", "11010.*", "1[^o]*"]*10
strings = ["asdabc", "123awd2", "abasdae23", "fooasdabar", "111", "11010100101", "xxxx", "eeeeee", "dddddddddddddd", "ffffff"]*10
compiled_patterns = list(map(re.compile, patterns))

def matches_pattern(str, patterns):
    for pattern in patterns:
        if pattern.match(str):
            return True
    return False

def test0():
    for s in strings:
        matches_pattern(s, compiled_patterns)

def test1():
    for s in strings:
        any(p.match(s) for p in compiled_patterns)

def test2():
    for s in strings:
        re.match('|'.join('(?:%s)' % p for p in patterns), s)

def test3():
    r = re.compile('|'.join('(?:%s)' % p for p in patterns))
    for s in strings:
        r.match(s)
"""

import sys
print(timeit.timeit("test0()", setup=setup, number=1000))
print(timeit.timeit("test1()", setup=setup, number=1000))
print(timeit.timeit("test2()", setup=setup, number=1000))
print(timeit.timeit("test3()", setup=setup, number=1000))

我机器上的输出：

1.4120500087738037
1.662621021270752
4.729579925537109
0.1489570140838623

所以any似乎并不比你原来的方法快。动态构建正则表达式也不是很快。但是，如果您可以设法预先构建一个正则表达式并多次使用它，这可能会带来更好的性能。您还可以调整此基准来测试其他一些选项:)

于 2012-05-14T21:09:17.187 回答
8

最快的方法是将所有正则表达式组合成一个"|"，然后在它们之间进行一次正则表达式匹配调用。此外，您需要编译一次以确保避免重复的正则表达式编译。

例如：

def matches_pattern(s, pats):
    pat = "|".join("(%s)" % p for p in pats)
    return bool(re.match(pat, s))

这是pats作为字符串，而不是编译模式。如果你真的只编译过正则表达式，那么：

def matches_pattern(s, pats):
    pat = "|".join("(%s)" % p.pattern for p in pats)
    return bool(re.match(pat, s))
于 2012-05-14T21:08:38.277 回答
2

除了上面的优秀答案之外，请确保将 re.match 的输出与 None 进行比较：

>>> timeit('None is None')
0.03676295280456543
>>> timeit('bool(None)')
0.1125330924987793
>>> timeit('re.match("a","abc") is None', 'import re')
1.0200879573822021
>>> timeit('bool(re.match("a","abc"))', 'import re')
1.134294033050537
于 2013-04-17T15:59:30.590 回答
0

这不完全是 OP 所要求的，但这对我来说作为长迭代匹配的替代方案很有效。

以下是一些示例数据和代码：

import random
import time
mylonglist = [ ''.join([ random.choice("ABCDE") for i in range(50)]) for j in range(3000) ]

# check uniqueness
print "uniqueness:"
print len(mylonglist) == len(set(mylonglist))

# subsample 1000
subsamp = [ mylonglist[x] for x in random.sample(xrange(3000),1000) ]
# join long string for matching
string = " ".join(subsamp)

# test function 1
def by_string_match(string, mylonglist):
    counter = 0
    t1 = time.time()
    for i in mylonglist:
        if i in string:
            counter += 1
    t2 = time.time()
    print "It took {} seconds to find {} items".format(t2-t1,counter)

# test function 2
def by_iterative_match(subsamp, mylonglist):
    counter = 0
    t1 = time.time()
    for i in mylonglist:
        if any([ i in s for s in subsamp ]):
            counter += 1
    t2 = time.time()
    print "It took {} seconds to find {} items".format(t2-t1,counter)

# test 1:
print "string match:"
by_string_match(string, mylonglist)
# test 2:
print "iterative match:"
by_iterative_match(subsamp, mylonglist)
于 2018-08-14T20:54:19.620 回答