python - 如何进一步优化此文本匹配功能？

Question

我需要让这个函数运行得更快（约快 20 倍）以满足所需的基准。我从最初的实现中做了很多改进，但我碰壁了。

word基本问题是：计算in不区分大小写的出现次数text。

复杂的标准包括：

1. 必须是一个完整的单词（ “Georges”word中没有text“George”）
2. 单引号将被视为单词的一部分，除非一行中有多个
3. word实际上可能是一个短语（意味着它可能有空格、标点符号等）
4. 不能使用正则表达式

我的基本实现是遍历 in 中的每个字符text，保持我在 in 中的位置word，如果该字符与 的对应字符匹配word，我将其添加到本地字符串中，推进我在wordand中的位置text，然后再去。一旦我有一个匹配候选（即我的本地字符串等于word），我检查周围的字符以确保匹配候选是一个完整的单词，根据上面的规则 1 和 2。请注意，此检查发生的频率不足以严重影响算法所花费的总时间。

迄今为止我所做的最成功的优化：

• 在循环外进行字符串小写和长度测量
• 检查word是否至少是一个子字符串，text否则立即返回 0
• 在我们完全匹配之前不要费心检查完整的单词潜力
• 预先计算出现的次数（没有规则），如果我们遇到这个数字，立即跳出循环

我已经使用pprofile 逐行分析了代码，并且我的代码的大部分运行时都是简单的行，例如递增计数器 var、将match_candidate字符串重置为“”、索引到字符串和 if 语句。我没有包含代码，validate_full_match因为它不是一个重要的时间用户。

有没有我忽略的低垂果实？我应该考虑完全不同的方法？

感谢您的任何建议！

def count_occurences_in_text(word, text):
    """Number of occurences of word (case insensitive) in text

    Note that word can actually be any length of text, from a single
    character to a complete phrase; however, partial words do not
    count. For example:
    count_occurences_in_text("george", "I am Georges") returns 0
    while
    count_occurences_in_text("i am", "I am Georges") returns 1
    """
    # We perform some measurements and manipulation at the start to
    # avoid performing them repeatedly in the loop below
    text = text.lower()
    word = word.lower()
    max_matches = text.count(word)
    if max_matches == 0:
        return 0
    word_len = len(word)
    # Counter vars
    match_count = 0
    text_cursor = 0
    word_cursor = 0
    # We will build up match_candidate and check it against word
    match_candidate = ""
    for text_char in text:
        if text_char == word[word_cursor]:
            match_candidate += text_char
            if word == match_candidate:
                if validate_full_match(text, text_cursor, word_len):
                    match_count += 1
                    if match_count == max_matches:
                        break
                    word_cursor = 0
                    match_candidate = ""
            else:
                word_cursor += 1
        else:
            match_candidate = ""
            word_cursor = 0
        text_cursor += 1
    return match_count

标签： python

Answer 1

1. Python 字符串是不可变的，每次执行 a 时，match_candidate += text_char您实际上是在创建一个新字符串并将以前版本的 match_candidate 的所有内容复制到它。假设你的话是'helloworld'。当'helloworl'文本中有匹配的机会时，您在(len(word)^2)此处执行操作。您当然可以通过维护索引来避免这种情况。这样可以节省很多操作。
2. max_matches = text.count(word)，您可以通过检查是否已到达文本末尾来避免这种情况。此功能最初会花费您O(len(text))可以避免的费用。
3. validate_full_match在这个函数中检查了什么。如果在比较单个字符时采取适当的步骤，您可以避免这种情况。

Python 易于编码，并且具有惊人的内置函数和构造。但要进行优化，您需要确保跟踪每一行的复杂性。