Python Cookbook

Counting Items and Sorting by Incidence (Histograms)

Credit: John Jensen, Fred Bremmer

Problem

You need to produce ascending- or descending-count histograms, such as the most or least common words in a file, popular pages on a web site, etc.

Solution

Histogramming is basically an issue of counting item occurrences (a Python dictionary makes this quite easy) and sorting by the counts. In Python, the two actions, and the dictionary that holds the counts, are easily wrapped into a class:

class Counter:
    def _ _init_ _(self):
        self.dict = {}
    def add(self, item):
        count = self.dict.get(item, 0)
        self.dict[item] = count + 1
    def counts(self, desc=None):
        """ Returns list of keys sorted by values.
        Pass desc as 1 if you want a descending sort. """
        result = map(None, self.dict.values(), self.dict.keys(  ))
        result.sort(  )
        if desc: result.reverse(  )
        return result

Discussion

The add method shows the normal Python idiom for counting occurrences of arbitrary (but hashable) items, using a dictionary to hold the counts. The counts method is where all the action is. It takes the dictionary and produces an ascending or descending sort of keys by values, returning a list of pairs representing the desired histogram. The map call takes advantage of an interesting but little-known tidbit of documented Python behavior. While the values and keys methods of a dictionary return their results in an arbitrary order, the ordering is compatible when the two methods are called without any intervening modification to the ...