1
\$\begingroup\$

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()
#"""
\$\endgroup\$
2
  • \$\begingroup\$ Why do you need to remove punctuation? And why only those listed and not others such as parentheses or semicolon? Counting exact occurrences you can do with the re module: docs.python.org/3/library/re.html \$\endgroup\$ Oct 30, 2023 at 18:11
  • \$\begingroup\$ The why or how is really not explained: it just has to pass the tests, and these characters are the one found in the tests. As for Regex, it is just too slow. \$\endgroup\$ Oct 30, 2023 at 18:34

1 Answer 1

4
\$\begingroup\$

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.

\$\endgroup\$
5
  • \$\begingroup\$ "comments promising to "remove space"" with the translation table ',_.!?:'. Given the code seems to be a copy of code further up in the function with the translation table ',_.!?\' '. Seems to me like a WET issue, and is a prime example of why explanation comments, which more beginner programmers tend to write, are a bad idea. \$\endgroup\$
    – Peilonrayz
    Oct 30, 2023 at 20:02
  • \$\begingroup\$ I tried using maketrans, and I have found it does not significantly improve efficiency. I am probably doing it wrong, though. As for using .index(), its results include occurrences of substrings of word, which I do not want. I'm sorry if the code doesn't seem serious, I try my best, but I am still learning. The comment promising to remove space comes from me, like mentioned above, but the test code has been provided by someone else. \$\endgroup\$ Oct 30, 2023 at 23:35
  • \$\begingroup\$ @JulesRaschilas, yeah, I took a stab at using pattern = re.compile(rf"\b{word}\b"), but the spec (or at least OP code) for various cases is complicated so it wasn't obvious how e.g. the O'Maley example should fit into a regex. I imagine your spec can be phrased in terms of a regex, and if so then I would expect .findall() to be fastest (working on un-split text, as find_each_occurrence does above). \$\endgroup\$
    – J_H
    Oct 31, 2023 at 19:41
  • \$\begingroup\$ I've been losing my mind over this, I think I'm just going to pass, as this is obviously above my current capabilities. If I may ask a last question, does this sound reasonable as a technical interview question for an internship? \$\endgroup\$ Nov 2, 2023 at 3:36
  • \$\begingroup\$ No, not especially. Ask interns questions about code you really care about. The difficult aspect of framing such a question is it must be short. Like, some people will be able to bang out the code in literally five minutes. And other candidates will take thirty minutes. You want to learn as much as possible during the interview, so you should have two or three short questions to ask the candidate. Be prepared to politely timeout / abandon a question and move on when you see things getting bogged down in the details. \$\endgroup\$
    – J_H
    Nov 2, 2023 at 3:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.