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

Question

我需要让这个函数运行得更快(大约快 20 倍)以满足所需的基准。与最初的实现相比，我已经做了很多改进，但遇到了困难。

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

复杂的标准包括:

1. 必须是一个完整的单词(在文本“Georges”中找不到单词“George”)
2. 单引号被视为单词的一部分，除非连续有多个单引号
3. word 实际上可能是一个短语(意味着它可以包含空格、标点符号等)
4. 无法使用正则表达式

我的基本实现是循环遍历 text 中的每个字符，维护我在 word 中的位置，以及该字符是否与 word 的相应字符匹配code>，我将其添加到本地字符串中，在 word 和 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

Answer 1

1. Python 字符串是不可变的，每次执行 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 易于编码，并且具有令人惊叹的内置函数和结构。但为了优化，您需要确保跟踪每一行的复杂性。