11
\$\begingroup\$

I'm learning programming with Python.

I’ve written the code below for finding the most common words in a text file that has about 1.1 million words. It is working fine, but I believe there is always room for improvement.

When run, the function in the script gets a text file from the command-line argument sys.argv[1], opens the file in read mode, converts the text to lowercase, makes a list of words from the text after removing any whitespaces or empty strings, and stores the list elements as dictionary keys and values in a collections.Counter object. Finally, it returns a dictionary of the most common words and their counts. The words.most_common() method gets its argument from the optional top parameter.

import sys
import collections

def find_most_common_words(textfile, top=10):    
    """ Return the most common words in a text file. """

    textfile = open(textfile)
    text = textfile.read().lower()
    textfile.close()
    words = collections.Counter(text.split()) # how often each word appears

    return dict(words.most_common(top))

filename = sys.argv[1]
top_five_words = find_most_common_words(filename, 5)
\$\endgroup\$
  • 1
    \$\begingroup\$ @Ludisposed I have been using defaultdict for counters. Did not know Counter existed. \$\endgroup\$ – Hindol Oct 1 '17 at 11:47
  • \$\begingroup\$ @Hindol Ah sorry for the misunderstanding, now I get your frustration. \$\endgroup\$ – Ludisposed Oct 1 '17 at 12:24
  • 3
    \$\begingroup\$ Please do not change the code after reviews have been posted. If you have a new variant, ask another question. What you may and may not do after receiving answers. \$\endgroup\$ – Zeta Oct 11 '17 at 8:44
  • \$\begingroup\$ @Zeta, I've just read the instructions. Thank you. \$\endgroup\$ – Srisaila Oct 11 '17 at 9:30
10
\$\begingroup\$

This is actually quite good. Good use of the collections module.

  • One improvement I can think of is switching to the with open(...) as: structure, that way the file will automatically be closed when finished processing.

  • Secondly it is standard in python to use a if __name__ == '__main__': block.

  • Lastly sys.argv will work ok for programs with not many arguments, but Id recommend looking at the argparse module.

\$\endgroup\$
7
\$\begingroup\$

Instead of opening sys.argv[1] yourself, consider taking advantage of the fileinput module. Your code will be more versatile, accepting input from standard input or from multiple files.

Also, you are reading the entire file into memory at once. Processing the text a line at a time would scale better to large files.

Converting the result to a dict would scramble the order, so don't do that.

import collections
import fileinput

def find_most_common_words(lines, top=10):    
    """Return the most common words in the lines of text."""
    words = collections.Counter()
    for line in lines:
        words.update(line.lower().split())
    return words.most_common(top)

top_five_words = find_most_common_words(fileinput.input(), 5)

As per PEP 257, docstrings should be worded in the imperative rather than the indicative mood, and should be delimited with three double-quotes.

\$\endgroup\$
  • \$\begingroup\$ The Counter.most_common() method returns a list of tuples sorted from the most common to the least common, and I’ve just tried dict([('x', 10), ('y', 8), ('z', 6)]) returning {'x': 10, 'y': 8, 'z': 6}. As you see, the order isn’t scrambled. Am I missing something? Thanks for the advice on docstrings. I’ll look into the fileinput module. \$\endgroup\$ – Srisaila Oct 1 '17 at 5:02
  • 3
    \$\begingroup\$ Python dictionaries do not guarantee any iteration order. To preserve the order, you need collections.OrderedDict. If you get the dict results in the same order as the original, that is by luck, not by design. (That is the reason why most_common() returns a list of pairs, rather than a dict.) \$\endgroup\$ – 200_success Oct 1 '17 at 5:07
  • 1
5
\$\begingroup\$

Firstly, I would like to congratulate you on having quite clear and readable code. That said, there is one main inefficiency that will make this rather unsuitable for large files. The following block

textfile = open(textfile)
text = textfile.read().lower()
textfile.close()

has the problem that it reads the entire file into memory. This will make the program very slow for large files. The way to fix this is to read bit by bit, and add to the counter incrementally.

def find_most_common_words(textfile, top=10):    
    ''' Returns the most common words in the textfile.'''
    words = collections.Counter()
    with open(textfile) as textfile:
         for line in textfile:
              #how often each word appears
              words.update(line.lower().split())

    return dict(words.most_common(top))

You should also probably put the last two lines outside the function in an if __name__ == '__main__' so other files can use your most common words piece.

\$\endgroup\$
  • \$\begingroup\$ Isn't that the default? Even so, clarity is good. \$\endgroup\$ – Oscar Smith Sep 30 '17 at 17:32
  • 3
    \$\begingroup\$ 6 MB is not large. Reading the entire thing into memory at once probably saved on some I/O overhead (vs. reading line by line). \$\endgroup\$ – neverendingqs Sep 30 '17 at 20:39
  • 7
    \$\begingroup\$ Want to emphasize what @neverendingqs said. It's very important to identify approximately how large your inputs will be, and the OP explicitly mentions that this code is for "a text file that has about 1.1 million words." This "optimization" is completely unnecessary—and may well be a pessimization: if you read the whole file into memory, then you work in sequential RAM, instead of jumping back and forth between disk and memory. If performance matters, you must profile. But for this problem it simply does not. \$\endgroup\$ – wchargin Oct 1 '17 at 4:07
  • 2
    \$\begingroup\$ There's no reason for reading into memory causing any slowdown, unless you run out of physical memory. Otherwise, it may be faster than streaming. \$\endgroup\$ – maaartinus Oct 1 '17 at 12:23
  • 1
    \$\begingroup\$ The reason it makes a difference is caching. The OP reads sequentially through memory several times, while a more optimized solution will work in chunks to keep cache coherency. \$\endgroup\$ – Oscar Smith Oct 1 '17 at 23:48
0
\$\begingroup\$

Even if you have a 32-bits operating system, your virtual address space (VAS) is 4GB. Here is a Microsoft Windows reference for what I am saying. And you can confirm that, if you are using Ubuntu, by running: cat /proc/meminfo | grep 'VmallocTotal'. If you have a 64-bits OS, your VAS is even larger.

This means your processor is not impressed by the size of the file you are dealing with in your question. And since speed is your concern, I suggest you to map the whole file into the VAS by using the mmap module (which stands for memory mapping).

The example provided in the documentation I linked to, show how to map the whole file into the virtual memory by setting the size to 0. So you can improve your work by relying on that trick:

import mmap


with open('text_file.txt', 'rb') as text_file:
  # Map the file into the virtual memory
  mapped_file = mmap.mmap(text_file.fileno(), 0, prot=mmap.PROT_READ)
  # Any line you red, from now on, will be too fast:
  line = mapped_file.readline()
\$\endgroup\$
-1
\$\begingroup\$

I'd read a select amount of the file at a time. Split it into characters, and then split on each empty space. This is better than splitting on each new line as the file may be one line.

To do the former in Python 3 is fairly simple:

def read_chunks(file, chunk_size):
    while True:
        chunk = file.read(chunk_size)
        if not chunk:
            break
        yield from chunk

This has \$O(\text{chunk_size})\$ memory usage, which is \$O(1)\$ as it's a constant. It also correctly ends the iterator, when the file ends.

After this, you want to split the words up. Since we're using str.split without any arguments, we should write just that method of splitting. We can use a fairly simple algorithm:

from string import whitespace

def split_whitespace(it):
    chunk = []
    for char in it:
        if char not in whitespace:
            chunk.append(char)
        elif chunk:
            yield tuple(chunk)
            chunk = []
    if chunk:
        yield tuple(chunk)

This has \$O(k)\$ memory, where \$k\$ is the size of the largest word. What we'd expect of a splitting function.

Finally we'd change from tuples to strings, using ''.join, and then use the collections.Counter. And split the word reading, and finding the most common into two different functions.

And so for an \$O(k)\$ memory usage version of your code, I'd use:

import sys
from collections import Counter
from string import whitespace


def read_chunks(file, chunk_size):
    while True:
        chunk = file.read(chunk_size)
        if not chunk:
            break
        yield from chunk


def split_whitespace(it):
    chunk = []
    for char in it:
        if char not in whitespace:
            chunk.append(char)
        elif chunk:
            yield tuple(chunk)
            chunk = []
    if chunk:
        yield tuple(chunk)


def read_words(path, chunk_size=1024):
    with open(path) as f:
        chars = read_chunks(f, chunk_size)
        tuple_words = split_whitespace(chars)
        yield from map(''.join, tuple_words)


def most_common_words(words, top=10):
    return dict(Counter(words).most_common(top))


if __name__ == '__main__':
    words = read_words(sys.argv[1])
    top_five_words = most_common_words(words, 5)
\$\endgroup\$
  • 5
    \$\begingroup\$ This is 4.7 times slower than OP's solution: 0.33±0.006s for yours vs. 0.07±0.005s for OP, with a dictionary of 1.2MB in size. Just briefly looking at the code, the if char not in whitespace: chunk.append(char) loop and all your memory-copies seem very wasteful. \$\endgroup\$ – wchargin Oct 1 '17 at 4:21
  • \$\begingroup\$ I would be interested to see how this works with pypy, as the slowdown here is in the re-implementation of split in C with one in Python, which PYPY should fix. That said, I think this code is broken, as if a word spans two chunks, I think this might split it in two. \$\endgroup\$ – Oscar Smith Oct 1 '17 at 6:11
  • \$\begingroup\$ @OscarSmith It works fine with words in different chunks, this is as yield from merges them into one \$\endgroup\$ – Peilonrayz Oct 1 '17 at 9:36
  • \$\begingroup\$ @wchargin I'm genuinely surprised that this is 4.7 times slower, I thought it would be much slower, as we all know C is way faster than Python. \$\endgroup\$ – Peilonrayz Oct 1 '17 at 9:37
  • \$\begingroup\$ My guess is that it comes from locality. The OP goes through 1mb sequentially 3 times, once for lower, once for split, once to add to dictionary, whereas this takes only one pass through the data, allowing most work to be done from L1/L2 cache. \$\endgroup\$ – Oscar Smith Oct 1 '17 at 21:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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