Given some text and a word list, print the 7 most common correctly spelled words

Question

I've got a basic python function that I've been tasked with finishing in a class.

It's already fulfilling all the requirements for an A as it's an introductory course to Python, but I'd like to get some advice on it still as it's taking quite some time to execute.

I've got a few years of experience with general programming, but I'm still quite new to Python. As such any sort of advice on what might be taking up time would be appreciated.

As it stands at the moment, it takes about .5 seconds to run through the code and print all the data.

A bit of detail to the program:

• It reads three files:

  1. A part of Alice in the Wonderland's first chapter (alice-ch1.txt)
  2. A list of common words (common-words.txt)
  3. And a list of correctly spelt words.
• Finally it prints the top 7 words that have passed through the filters.

def analyse():
    #import listdir
    from os import listdir
    #import counter
    from collections import Counter
    files = "*************************************\n"
    for file in listdir():
        if file.endswith('.txt'):
            files = files + file + "\n"
    choice = input("These are the files: \n" + files + "*************************************\nWhat file would you like to analyse?\n")

    if choice.strip() == "":
        choice = "alice-ch1.txt"
    elif choice.endswith(".txt"):
        print(choice)
    else:
        choice = choice + ".txt"
    print(choice)

    with open(choice) as readFile, open('common-words.txt') as common, open('words.txt') as correct:
        correct_words = correct.readlines()
        common_words = common.readlines()
        common_words = list(map(lambda s: s.strip(), common_words))
        correct_words = list(map(lambda s: s.strip(), correct_words))

        words = [word for line in readFile for word in line.split()]
        for word in list(words):
            if word in common_words or not word in correct_words:
                words.remove(word)
        print("There are " + str(len(words)))
        c = Counter(words)
        #for word, count in c.most_common():
        #    print (word, count)
        nNumbers = list(c.most_common(7))
        out = ""
        print("*************************************\nThese are the 7 most common:")
        for word, count in nNumbers:
                out = out + word + "," + str(count) + "\n"
        print(out + "\n*************************************")

    input("\nPress enter to continue...")

Answer 1

List Comprehension

I'm not at all sure it'll run much faster (though it might--it's a little faster under Python 2.7, anyway), but I think a more Pythonesque approach would be to replace your loop:

    for word in list(words):
        if word in common_words or not word in correct_words:
            words.remove(word)

... with a list comprehension, something like:

words = [word for word in words if not word in common_words and word in correct_words]

Algorithm

To gain substantial speed, you probably want to rearrange your operations. Right now you're looking at each word in the input separately (and looking at all of them). Then, after you've found all the words that aren't common and are spelled correctly, you choose the 7 most common.

I'd reverse that: start by creating a Counter of all the input words. Then print those filtering words that are common or aren't spelled correctly. When you've printed seven of them, stop:

    words = [ word for line in readFile for word in line.split() ]

    c = Counter(words)

    counter = 0

    for word, count in c.most_common():
        if not word in common_words and word in correct_words:
           print word + ", "  + str(count)
           counter = counter + 1
           if counter == 7:
               break;

You could simplify that inner loop a little by by doing a little preprocessing. Instead of testing against both the common and correctly spelled lists, you could start by removing all the common words from the correctly spelled list, to get a single list of the words that are acceptable. Then when you're printing out your results, you'd check only against that one list. Given the sizes of the lists, this would be a win primarily if you did it once and saved the result so you can re-use it. If you re-did the preprocessing every time you ran the program, you'd probably use more time on the preprocessing than you'd save on the output loop.

There's probably more than can be done to make this neater as well, but nothing occurs to me immediately. At least for me in a quick test, this seems to run around ten to fifteen (or so) times as fast as the code in the question. The exact difference in speed will probably depend (heavily) on the size of input file though. In particular, I believe this is changing from \$O(N^2)\$ complexity to an expected complexity around \$O(N)\$¹.

As an aside, I did consider (and test with) using a set instead of a list for common_words and correct_words, but at least in my testing, with the updated algorithm this didn't seem to make a difference that I could replicate dependably. With the original algorithm, however, changing these from list to set can improve performance considerably.

Logic

As it stands right now, your if/then chain:

if choice.strip() == "":
    choice = "alice-ch1.txt"
elif choice.endswith(".txt"):
    print(choice)
else:
    choice = choice + ".txt"
print(choice)

... prints out choice twice if it starts out ending with .txt. I suspect you really want something closer to:

if choice.strip() == "":
    choice = "alice-ch1.txt"
elif not choice.endswith(".txt")
    choice = choice + ".txt"
print(choice)

Magic number

It would probably be better to use something on the order of:

mostCommonLimit = 7

# ...

if counter == mostCommonLimit
    break;

---

1. If you want to get technical, it probably is still \$O(N^2)\$. The Counter presumably uses a hash table, which is \$O(1)\$ expected complexity, but can be \$O(N)\$ in the worst case (where all keys produce equivalent hashes). This is, however, so rare that in practice it's often ignored.