Function that finds the exact number of times a string appears in a text

Question

So I was tasked with providing a function that returns how many exact occurrences of attribute word appear in attribute text. The goal is for the function to be as fast as possible, and I managed to get down to 0.21 seconds. When using python -m pytest file.py. Here is what I got:

def count_occurrences_in_text(word, text):
    """
    Return the number of occurrences of word (case insensitive) in text
    Trims text of the following characters : ,_.!?:'
    'word' can be either a single word or a series of word separated by empty spaces
    """
    #Lowercases both string so that comparisons are case insensitive
    word, text = word.lower(), text.lower()

    #Case where pattern is a sentence
    if ' ' in word:
        #Remove space and punctuation from word 
        for char in ',_.!?\' ':
            word, text = word.replace(char, ''), text.replace(char, '')
      
        return word in text 
    

    #Case where pattern is a simple word
    else:
        #Remove space and punctuation from text 
        for char in ',_.!?:':
            text = text.replace(char, ' ')
        if("''" in text):
            text = text.replace("'", '')

        #Split the text into list of words using empty space as separator
        text = text.split()

        #Go through the words in the text
        return sum(1 for elem in text if word == elem)

My problem is that I need the function to be able to do the same significantly faster, and I am completely out of ideas. Here are the tests:

def test_count_occurrences_in_text():
    text = """Georges is my name and I like python. Oh ! your name is georges? And you like Python!
Yes is is true, I like PYTHON
and my name is GEORGES"""
    # test with a little text.
    assert 3 == count_occurrences_in_text("Georges", text)
    assert 3 == count_occurrences_in_text("GEORGES", text)
    assert 3 == count_occurrences_in_text("georges", text)
    assert 0 == count_occurrences_in_text("george", text)
    assert 3 == count_occurrences_in_text("python", text)
    assert 3 == count_occurrences_in_text("PYTHON", text)
    assert 2 == count_occurrences_in_text("I", text)
    assert 0 == count_occurrences_in_text("n", text)
    assert 1 == count_occurrences_in_text("true", text)
    # regard ' as text:
    assert 0 == count_occurrences_in_text("maley", "John O'maley is my friend")

    # Test it but with a BIG length file.
    text = """The quick brown fox jump over the lazy dog.The quick brown fox jump over the lazy dog.""" * 500
    text += """The quick brown fox jump over the lazy dog.The quick brown Georges jump over the lazy dog."""
    text += """esrf sqfdg sfdglkj sdflgh sdflgjdsqrgl """ * 4000
    text += """The quick brown fox jump over the lazy dog.The quick brown fox jump over the lazy python."""
    text += """The quick brown fox jump over the lazy dog.The quick brown fox jump over the lazy dog.""" * 500
    text += """The quick brown fox jump over the lazy dog.The quick brown Georges jump over the lazy dog."""
    text += """esrf sqfdg sfdglkj sdflgh sdflgjdsqrgl """ * 4000
    text += """The quick brown fox jump over the lazy dog.The quick brown fox jump over the lazy python."""
    text += """The quick brown fox jump over the lazy dog.The quick brown fox jump over the lazy dog.""" * 500
    text += """The quick brown fox jump over the lazy dog.The quick brown Georges jump over the lazy dog."""
    text += """esrf sqfdg sfdglkj sdflgh sdflgjdsqrgl """ * 4000
    text += """The quick brown fox jump over the lazy dog.The quick brown fox jump over the lazy python."""
    text += """The quick brown fox jump over the true lazy dog.The quick brown fox jump over the lazy dog."""
    text += """The quick brown fox jump over the lazy dog.The quick brown fox jump over the lazy dog.""" * 500
    text += """ I vsfgsdfg sfdg sdfg sdgh sgh I sfdgsdf"""
    text += """The quick brown fox jump over the lazy dog.The quick brown fox jump over the lazy dog.""" * 500

    assert 3 == count_occurrences_in_text("Georges", text)
    assert 3 == count_occurrences_in_text("GEORGES", text)
    assert 3 == count_occurrences_in_text("georges", text)
    assert 0 == count_occurrences_in_text("george", text)
    assert 3 == count_occurrences_in_text("python", text)
    assert 3 == count_occurrences_in_text("PYTHON", text)
    assert 2 == count_occurrences_in_text("I", text)
    assert 0 == count_occurrences_in_text("n", text)
    assert 1 == count_occurrences_in_text("true", text)
    assert 1 == count_occurrences_in_text(
        "'reflexion mirror'", "I am a senior citizen and I live in the Fun-Plex 'Reflexion Mirror' in Sopchoppy, Florida"
    )
    assert 1 == count_occurrences_in_text(
        "reflexion mirror", "I am a senior citizen and I live in the Fun-Plex (Reflexion Mirror) in Sopchoppy, Florida"
    )
    assert 1 == count_occurrences_in_text("reflexion mirror", "Reflexion Mirror\" in Sopchoppy, Florida")
    assert 1 == count_occurrences_in_text(
        "reflexion mirror", "I am a senior citizen and I live in the Fun-Plex «Reflexion Mirror» in Sopchoppy, Florida"
    )
    assert 1 == count_occurrences_in_text(
        "reflexion mirror",
        "I am a senior citizen and I live in the Fun-Plex \u201cReflexion Mirror\u201d in Sopchoppy, Florida"
    )
    assert 1 == count_occurrences_in_text(
        "legitimate", "who is approved by OILS is completely legitimate: their employees are of legal working age"
    )
    assert 0 == count_occurrences_in_text(
        "legitimate their", "who is approved by OILS is completely legitimate: their employees are of legal working age"
    )
    assert 1 == count_occurrences_in_text(
        "get back to me", "I hope you will consider this proposal, and get back to me as soon as possible"
    )
    assert 1 == count_occurrences_in_text(
        "skin-care", "enable Delavigne and its subsidiaries to create a skin-care monopoly"
    )
    assert 1 == count_occurrences_in_text(
        "skin-care monopoly", "enable Delavigne and its subsidiaries to create a skin-care monopoly"
    )
    assert 0 == count_occurrences_in_text(
        "skin-care monopoly in the US", "enable Delavigne and its subsidiaries to create a skin-care monopoly"
    )
    assert 1 == count_occurrences_in_text("get back to me", "When you know:get back to me")
    assert 1 == count_occurrences_in_text(
        "don't be left", """emergency alarm warning.
Don't be left unprotected. Order your SSSS3000 today!"""
    )
    assert 1 == count_occurrences_in_text(
        "don", """emergency alarm warning.
Don't be left unprotected. Order your don SSSS3000 today!"""
    )
    assert 1 == count_occurrences_in_text("take that as a 'yes'", "Do I have to take that as a 'yes'?")
    assert 1 == count_occurrences_in_text("don't take that as a 'yes'", "I don't take that as a 'yes'?")
    assert 1 == count_occurrences_in_text("take that as a 'yes'", "I don't take that as a 'yes'?")
    assert 1 == count_occurrences_in_text("don't", "I don't take that as a 'yes'?")
    assert 1 == count_occurrences_in_text("attaching my c.v. to this e-mail", "I am attaching my c.v. to this e-mail.")
    assert 1 == count_occurrences_in_text("Linguist", "'''Linguist Specialist Found Dead on Laboratory Floor'''")
    assert 1 == count_occurrences_in_text(
        "Linguist Specialist", "'''Linguist Specialist Found Dead on Laboratory Floor'''"
    )
    assert 1 == count_occurrences_in_text(
        "Laboratory Floor", "'''Linguist Specialist Found Dead on Laboratory Floor'''"
    )
    assert 1 == count_occurrences_in_text("Floor", "'''Linguist Specialist Found Dead on Laboratory Floor'''")
    assert 1 == count_occurrences_in_text("Floor", "''Linguist Specialist Found Dead on Laboratory Floor''")
    assert 1 == count_occurrences_in_text("Floor", "__Linguist Specialist Found Dead on Laboratory Floor__")
    assert 1 == count_occurrences_in_text("Floor", "'''''Linguist Specialist Found Dead on Laboratory Floor'''''")
    assert 1 == count_occurrences_in_text("Linguist", "'''Linguist Specialist Found Dead on Laboratory Floor'''")
    assert 1 == count_occurrences_in_text("Linguist", "''Linguist Specialist Found Dead on Laboratory Floor''")
    assert 1 == count_occurrences_in_text("Linguist", "__Linguist Specialist Found Dead on Laboratory Floor__")
    assert 1 == count_occurrences_in_text("Linguist", "'''''Linguist Specialist Found Dead on Laboratory Floor'''''")


SAMPLE_TEXT_FOR_BENCH = """
A Suggestion Box Entry from Bob Carter

Dear Anonymous,

I'm not quite sure I understand the concept of this 'Anonymous' Suggestion Box. If no one reads what we write, then how will anything ever
change?

But in the spirit of good will, I've decided to offer my two cents, and hopefully Kevin won't steal it! (ha, ha). I would really like to
see more varieties of coffee in the coffee machine in the break room. 'Milk and sugar', 'black with sugar', 'extra sugar' and 'cream and su
gar' don't offer much diversity. Also, the selection of drinks seems heavily weighted in favor of 'sugar'. What if we don't want any suga
r?

But all this is beside the point because I quite like sugar, to be honest. In fact, that's my second suggestion: more sugar in the office.
Cakes, candy, insulin, aspartame... I'm not picky. I'll take it by mouth or inject it intravenously, if I have to.

Also, if someone could please fix the lock on the men's room stall, that would be helpful. Yesterday I was doing my business when Icarus ne
arly climbed into my lap.

So, have a great day!

Anonymously,
Bob Carter
"""


def doit():
    """
    Run count_occurrences_in_text on a few examples
    """
    i = 0
    for x in range(400):
        i += count_occurrences_in_text("word", SAMPLE_TEXT_FOR_BENCH)
        i += count_occurrences_in_text("sugar", SAMPLE_TEXT_FOR_BENCH)
        i += count_occurrences_in_text("help", SAMPLE_TEXT_FOR_BENCH)
        i += count_occurrences_in_text("heavily", SAMPLE_TEXT_FOR_BENCH)
        i += count_occurrences_in_text("witfull", SAMPLE_TEXT_FOR_BENCH)
        i += count_occurrences_in_text("dog", SAMPLE_TEXT_FOR_BENCH)
        i += count_occurrences_in_text("almost", SAMPLE_TEXT_FOR_BENCH)
        i += count_occurrences_in_text("insulin", SAMPLE_TEXT_FOR_BENCH)
        i += count_occurrences_in_text("attaching", SAMPLE_TEXT_FOR_BENCH)
        i += count_occurrences_in_text("asma", SAMPLE_TEXT_FOR_BENCH)
        i += count_occurrences_in_text("neither", SAMPLE_TEXT_FOR_BENCH)
        i += count_occurrences_in_text("won't", SAMPLE_TEXT_FOR_BENCH)
        i += count_occurrences_in_text("green", SAMPLE_TEXT_FOR_BENCH)
        i += count_occurrences_in_text("parabole", SAMPLE_TEXT_FOR_BENCH)
    return i


#"""
def test_profile():
    with cProfile.Profile() as pr:
        assert doit() == 2000
        pr.print_stats()
#"""

Answer 1

Your question doesn't seem like a serious request for a software engineering "code review". Given the meaningless identifiers such as doit, comments promising to "remove space" for code which does not remove space, and so on.

Repeated .index() calls could skip over "lorem ipsum" dross without producing each word, nearly as fast as .findall().

I will focus on just one bit of code.

        for char in ',_.!?\' ':
            ..., text = ..., text.replace(char, '')

It would have been more natural to express the constant as ",_.!?' ", whatever. Or use a MANIFEST_CONSTANT that its multiple uses can refer to.

What's the time complexity?
We have K = 7 characters to trim from text of length N. That gives O(K × N) time to repeatedly read and write most of that text. There's a builtin C function to accomplish this common task in a single pass, in O(N) time.

At module scope (outside the function) initialize

punct_xlate = str.maketrans("", "", ",_.!?' ")

Now within the function we can assign

        text = text.translate(punct_xlate)

EDIT

How do we know one approach is faster than the other? Let's benchmark it and see.

punct_xlate = str.maketrans("", "", ",_.!?' ")


def prepare_text_rapidly(text: str) -> str:
    return text.translate(punct_xlate)


def prepare_text_slowly(text: str) -> str:
    for char in ",_.!?' ":
        text = text.replace(char, "")
    return text


def test_profile(text=SAMPLE_TEXT_FOR_BENCH):
    assert 1094 == len(text)
    assert 855 == len(prepare_text_rapidly(text))
    assert 855 == len(prepare_text_slowly(text))

    with cProfile.Profile() as pr:
        for _ in range(1_000_000):
            prepare_text_rapidly(text)

    pr.print_stats(sort="cumulative")

Output:

         2000002 function calls in 5.534 seconds

   Ordered by: cumulative time

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
  1000000    0.368    0.000    5.534    0.000 word_finder.py:256(prepare_text_rapidly)
  1000000    5.165    0.000    5.165    0.000 {method 'translate' of 'str' objects}

Output with a one-line change that invokes prepare_text_slowly():

         8000002 function calls in 12.677 seconds

   Ordered by: cumulative time

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
  1000000    2.347    0.000   12.677    0.000 word_finder.py:260(prepare_text_slowly)
  7000000   10.329    0.000   10.329    0.000 {method 'replace' of 'str' objects}

For this workload that's significantly more than a 2x speedup.

Let's bench the .index() alternative:

        ...
        # Go through the words in the text
        return sum(find_each_occurrence(word, text))


def find_each_occurrence(word, text):
    """Generates as many 1's as there are word matches."""
    i = 0
    try:
        while i < len(text):
            i = text.index(word, i) + 1
            yield 1
    except ValueError:
        pass

Executing assert 2_000 == doit() a hundred times gives this:

         8440102 function calls in 12.186 seconds

   Ordered by: cumulative time

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
      100    1.224    0.012   12.186    0.122 word_finder.py:243(do_counts)
   560000    2.731    0.000   10.963    0.000 word_finder.py:4(count_occurrences_in_text)
   560000    3.743    0.000    3.743    0.000 {method 'split' of 'str' objects}
   560000    0.274    0.000    2.810    0.000 {built-in method builtins.sum}
   760000    0.706    0.000    2.535    0.000 word_finder.py:38(find_each_occurrence)
   760000    1.725    0.000    1.725    0.000 {method 'index' of 'list' objects}
  3360000    1.130    0.000    1.130    0.000 {method 'replace' of 'str' objects}
  1120000    0.549    0.000    0.549    0.000 {method 'lower' of 'str' objects}
   760000    0.104    0.000    0.104    0.000 {built-in method builtins.len}

Corresponding measurement of OP code (sum(1 ...)) gives this:

         6920102 function calls in 18.452 seconds

   Ordered by: cumulative time

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
      100    1.424    0.014   18.452    0.185 word_finder.py:243(do_counts)
   560000    3.072    0.000   17.028    0.000 word_finder.py:4(count_occurrences_in_text)
   560000    0.357    0.000    7.987    0.000 {built-in method builtins.sum}
   760000    7.630    0.000    7.630    0.000 word_finder.py:34(<genexpr>)
   560000    4.154    0.000    4.154    0.000 {method 'split' of 'str' objects}
  3360000    1.210    0.000    1.210    0.000 {method 'replace' of 'str' objects}
  1120000    0.604    0.000    0.604    0.000 {method 'lower' of 'str' objects}

Looks like we shaved more than one-third off the running time.