View source for Archive:Think Python/Case study: data structure selection

{{Think Python/Page}}

== Chapter&#XA0;13&#XA0;&#XA0;Case study: data structure selection ==

=== 13.1&#XA0;&#XA0;Word frequency analysis ===




As usual, you should at least attempt the following exercises
before you read my solutions.
<DIV CLASS="theorem">'''Exercise&#XA0;1'''&#XA0;&#XA0;''
Write a program that reads a file, breaks each line into
words, strips whitespace and punctuation from the words, and
converts them to lowercase.''
''
''

''Hint: The ''''<TT>string</TT>'''' module provides strings named ''''<TT>whitespace</TT>'''',
which contains space, tab, newline, etc., and ''''<TT>punctuation</TT>'''' which contains the punctuation characters. Let&#X2019;s see
if we can make Python swear:''
<PRE CLASS="verbatim">''&gt;&gt;&gt; import string
&gt;&gt;&gt; print string.punctuation
!"#$%&amp;'()*+,-./:;&lt;=&gt;?@[\]^_`{|}~
''</PRE>
''Also, you might consider using the string methods ''''<TT>strip</TT>'''',
''''<TT>replace</TT>'''' and ''''<TT>translate</TT>''''.''

''
''''
''''
''''
''''
''
</DIV><DIV CLASS="theorem">'''Exercise&#XA0;2'''&#XA0;&#XA0;

''Go to Project Gutenberg (''''<TT>gutenberg.net</TT>'''') and download 
your favorite out-of-copyright book in plain text format.''

''
''

''Modify your program from the previous exercise to read the book
you downloaded, skip over the header information at the beginning
of the file, and process the rest of the words as before.''

''Then modify the program to count the total number of words in
the book, and the number of times each word is used.''

''
''

''Print the number of different words used in the book. Compare
different books by different authors, written in different eras.
Which author uses the most extensive vocabulary?
''
</DIV><DIV CLASS="theorem">'''Exercise&#XA0;3'''&#XA0;&#XA0;''
Modify the program from the previous exercise to print the
20 most frequently-used words in the book.
''</DIV><DIV CLASS="theorem">'''Exercise&#XA0;4'''&#XA0;&#XA0;''
Modify the previous program to read a word list (see
Section&#XA0;''''9.1'''') and then print all the words in the book that
are not in the word list. How many of them are typos? How many of
them are common words that ''should'' be in the word list, and how
many of them are really obscure?
''</DIV>=== 13.2&#XA0;&#XA0;Random numbers ===






Given the same inputs, most computer programs generate the same
outputs every time, so they are said to be '''deterministic'''.
Determinism is usually a good thing, since we expect the same
calculation to yield the same result. For some applications, though,
we want the computer to be unpredictable. Games are an obvious
example, but there are more.

Making a program truly nondeterministic turns out to be not so easy,
but there are ways to make it at least seem nondeterministic. One of
them is to use algorithms that generate '''pseudorandom''' numbers.
Pseudorandom numbers are not truly random because they are generated
by a deterministic computation, but just by looking at the numbers it
is all but impossible to distinguish them from random.




The <TT>random</TT> module provides functions that generate
pseudorandom numbers (which I will simply call &#X201C;random&#X201D; from
here on).




The function <TT>random</TT> returns a random float
between 0.0 and 1.0 (including 0.0 but not 1.0). Each time you
call <TT>random</TT>, you get the next number in a long series. To see a
sample, run this loop:
<PRE CLASS="verbatim">import random

for i in range(10):
    x = random.random()
    print x
</PRE>
The function <TT>randint</TT> takes parameters <TT>low</TT> and
<TT>high</TT> and returns an integer between <TT>low</TT> and
<TT>high</TT> (including both).



<PRE CLASS="verbatim">&gt;&gt;&gt; random.randint(5, 10)
5
&gt;&gt;&gt; random.randint(5, 10)
9
</PRE>
To choose an element from a sequence at random, you can use
<TT>choice</TT>:



<PRE CLASS="verbatim">&gt;&gt;&gt; t = [1, 2, 3]
&gt;&gt;&gt; random.choice(t)
2
&gt;&gt;&gt; random.choice(t)
3
</PRE>
The <TT>random</TT> module also provides functions to generate
random values from continuous distributions including
Gaussian, exponential, gamma, and a few more.
<DIV CLASS="theorem">'''Exercise&#XA0;5'''&#XA0;&#XA0;

''Write a function named ''<CODE>''choose_from_hist''</CODE>'' that takes
a histogram as defined in Section&#XA0;''''11.1'''' and returns a 
random value from the histogram, chosen with probability
in proportion to frequency. For example, for this histogram:''
<PRE CLASS="verbatim">''&gt;&gt;&gt; t = ['a', 'a', 'b']
&gt;&gt;&gt; h = histogram(t)
&gt;&gt;&gt; print h
{'a': 2, 'b': 1}
''</PRE>
''your function should ''''<TT>&#X2019;a&#X2019;</TT>'''' with probability ''''2/3'''' and ''<CODE>'''b'''</CODE>''
with probability ''''1/3''''.
''
</DIV>=== 13.3&#XA0;&#XA0;Word histogram ===

Here is a program that reads a file and builds a histogram of the
words in the file:

<PRE CLASS="verbatim">import string

def process_file(filename):
    h = dict()
    fp = open(filename)
    for line in fp:
        process_line(line, h)
    return h

def process_line(line, h):
    line = line.replace('-', ' ')
    
    for word in line.split():
        word = word.strip(string.punctuation + string.whitespace)
        word = word.lower()

        h[word] = h.get(word, 0) + 1

hist = process_file('emma.txt')
</PRE>
This program reads <TT>emma.txt</TT>, which contains the text of ''Emma'' by Jane Austen.

<CODE>process_file</CODE> loops through the lines of the file,
passing them one at a time to <CODE>process_line</CODE>. The histogram
<TT>h</TT> is being used as an accumulator.




<CODE>process_line</CODE> uses the string method <TT>replace</TT> to replace
hyphens with spaces before using <TT>split</TT> to break the line into a
list of strings. It traverses the list of words and uses <TT>strip</TT>
and <TT>lower</TT> to remove punctuation and convert to lower case. (It
is a shorthand to say that strings are &#X201C;converted;&#X201D; remember that
string are immutable, so methods like <TT>strip</TT> and <TT>lower</TT>
return new strings.)

Finally, <CODE>process_line</CODE> updates the histogram by creating a new
item or incrementing an existing one.

To count the total number of words in the file, we can add up
the frequencies in the histogram:
<PRE CLASS="verbatim">def total_words(h):
    return sum(h.values())
</PRE>
The number of different words is just the number of items in
the dictionary:
<PRE CLASS="verbatim">def different_words(h):
    return len(h)
</PRE>
Here is some code to print the results:
<PRE CLASS="verbatim">print 'Total number of words:', total_words(hist)
print 'Number of different words:', different_words(hist)
</PRE>
And the results:
<PRE CLASS="verbatim">Total number of words: 161073
Number of different words: 7212
</PRE>=== 13.4&#XA0;&#XA0;Most common words ===




To find the most common words, we can apply the DSU pattern;
<CODE>most_common</CODE> takes a histogram and returns a list of
word-frequency tuples, sorted in reverse order by frequency:
<PRE CLASS="verbatim">def most_common(h):
    t = []
    for key, value in h.items():
        t.append((value, key))

    t.sort(reverse=True)
    return t
</PRE>
Here is a loop that prints the ten most common words:
<PRE CLASS="verbatim">t = most_common(hist)
print 'The most common words are:'
for freq, word in t[0:10]:
    print word, '\t', freq
</PRE>
And here are the results from ''Emma'':
<PRE CLASS="verbatim">The most common words are:
to      5242
the     5204
and     4897
of      4293
i       3191
a       3130
it      2529
her     2483
was     2400
she     2364
</PRE>=== 13.5&#XA0;&#XA0;Optional parameters ===




We have seen built-in functions and methods that take a variable
number of arguments. It is possible to write user-defined functions
with optional arguments, too. For example, here is a function that
prints the most common words in a histogram
<PRE CLASS="verbatim">def print_most_common(hist, num=10)
    t = most_common(hist)
    print 'The most common words are:'
    for freq, word in t[0:num]:
        print word, '\t', freq
</PRE>
The first parameter is required; the second is optional.
The '''default value''' of <TT>num</TT> is 10.




If you only provide one argument:
<PRE CLASS="verbatim">print_most_common(hist)
</PRE>
<TT>num</TT> gets the default value. If you provide two arguments:
<PRE CLASS="verbatim">print_most_common(hist, 20)
</PRE>
<TT>num</TT> gets the value of the argument instead. In other
words, the optional argument '''overrides''' the default value.

If a function has both required and optional parameters, all
the required parameters have to come first, followed by the
optional ones.
=== 13.6&#XA0;&#XA0;Dictionary subtraction ===




Finding the words from the book that are not in the word list
from <TT>words.txt</TT> is a problem you might recognize as set
subtraction; that is, we want to find all the words from one
set (the words in the book) that are not in another set (the
words in the list).

<TT>subtract</TT> takes dictionaries <TT>d1</TT> and <TT>d2</TT> and returns a
new dictionary that contains all the keys from <TT>d1</TT> that are not
in <TT>d2</TT>. Since we don&#X2019;t really care about the values, we
set them all to None.
<PRE CLASS="verbatim">def subtract(d1, d2):
    res = dict()
    for key in d1:
        if key not in d2:
            res[key] = None
    return res
</PRE>
To find the words in the book that are not in <TT>words.txt</TT>,
we can use <CODE>process_file</CODE> to build a histogram for
<TT>words.txt</TT>, and then subtract:
<PRE CLASS="verbatim">words = process_file('words.txt')
diff = subtract(hist, words)

print "The words in the book that aren't in the word list are:"
for word in diff.keys():
    print word,
</PRE>
Here are some of the results from ''Emma'':
<PRE CLASS="verbatim">The words in the book that aren't in the word list are:
 rencontre jane's blanche woodhouses disingenuousness 
friend's venice apartment ...
</PRE>
Some of these words are names and possessives. Others, like
&#X201C;rencontre,&#X201D; are no longer in common use. But a few are common
words that should really be in the list!
<DIV CLASS="theorem">'''Exercise&#XA0;6'''&#XA0;&#XA0;
''
''

''Python provides a data structure called ''''<TT>set</TT>'''' that provides many
common set operations. Read the documentation at
''''<TT>docs.python.org/lib/types-set.html</TT>'''' and write a program
that uses set subtraction to find words in the book that are not in
the word list.
''
</DIV>=== 13.7&#XA0;&#XA0;Random words ===




To choose a random word from the histogram, the simplest algorithm
is to build a list with multiple copies of each word, according
to the observed frequency, and then choose from the list:
<PRE CLASS="verbatim">def random_word(h):
    t = []
    for word, freq in h.items():
        t.extend([word] * freq)

    return random.choice(t)
</PRE>
The expression <TT>[word] * freq</TT> creates a list with <TT>freq</TT>
copies of the string <TT>word</TT>. The <TT>extend</TT>
method is similar to <TT>append</TT> except that the argument is
a sequence.
<DIV CLASS="theorem">'''Exercise&#XA0;7'''&#XA0;&#XA0;''
''

''This algorithm works, but it is not very efficient; each time you
choose a random word, it rebuilds the list, which is as big as
the original book. An obvious improvement is to build the list
once and then make multiple selections, but the list is still big.''

''An alternative is:''

*''Use ''''<TT>keys</TT>'''' to get a list of the words in the book.''

*''Build a list that contains the cumulative sum of the word
frequencies (see Exercise&#XA0;''''10.1''''). The last item
in this list is the total number of words in the book, ''''<I>n</I>''''.''

*''Choose a random number from 1 to ''''<I>n</I>''''. Use a bisection search
(See Exercise&#XA0;''''10.8'''') to find the index where the random
number would be inserted in the cumulative sum.''

*''Use the index to find the corresponding word in the word list.''

''Write a program that uses this algorithm to choose a random
word from the book.
''
</DIV>=== 13.8&#XA0;&#XA0;Markov analysis ===

If you choose words from the book at random, you can get a
sense of the vocabulary, you probably won&#X2019;t get a sentence:
<PRE CLASS="verbatim">this the small regard harriet which knightley's it most things
</PRE>
A series of random words seldom makes sense because there
is no relationship between successive words. For example, in
a real sentence you would expect an article like &#X201C;the&#X201D; to
be followed by an adjective or a noun, and probably not a verb
or adverb.

One way to measure these kinds of relationships is Markov
analysis, which characterizes, for a given sequence of words,
the probability of the word that comes next. For example,
the song ''Eric, the Half a Bee'' begins:
<BLOCKQUOTE CLASS="quote">
Half a bee, philosophically,<BR>
Must, ipso facto, half not be.<BR>
But half the bee has got to be<BR>
Vis a vis, its entity. D&#X2019;you see?<BR><BR>
But can a bee be said to be<BR>
Or not to be an entire bee<BR>
When half the bee is not a bee<BR>
Due to some ancient injury?<BR>
</BLOCKQUOTE>

In this text,
the phrase &#X201C;half the&#X201D; is always followed by the word &#X201C;bee,&#X201D;
but the phrase &#X201C;the bee&#X201D; might be followed by either
&#X201C;has&#X201D; or &#X201C;is&#X201D;.





The result of Markov analysis is a mapping from each prefix
(like &#X201C;half the&#X201D; and &#X201C;the bee&#X201D;) to all possible suffixes
(like &#X201C;has&#X201D; and &#X201C;is&#X201D;).




Given this mapping, you can generate a random text by
starting with any prefix and choosing at random from the
possible suffixes. Next, you can combine the end of the
prefix and the new suffix to form the next prefix, and repeat.

For example, if you start with the prefix &#X201C;Half a,&#X201D; then the
next word has to be &#X201C;bee,&#X201D; because the prefix only appears
once in the text. The next prefix is &#X201C;a bee,&#X201D; so the
next suffix might be &#X201C;philosophically,&#X201D; &#X201C;be&#X201D; or &#X201C;due.&#X201D;

In this example the length of the prefix is always two, but
you can do Markov analysis with any prefix length. The length
of the prefix is called the &#X201C;order&#X201D; of the analysis.
<DIV CLASS="theorem">'''Exercise&#XA0;8'''&#XA0;&#XA0;''
Markov analysis:''

*''Write a program to read a text from a file and perform Markov
analysis. The result should be a dictionary that maps from
prefixes to a collection of possible suffixes. The collection
might be a list, tuple, or dictionary; it is up to you to make
an appropriate choice. You can test your program with prefix
length two, but you should write the program in a way that makes
it easy to try other lengths.''

*''Add a function to the previous program to generate random text
based on the Markov analysis. Here is an example from ''Emma''
with prefix length 2:''<BLOCKQUOTE CLASS="quote">''''
He was very clever, be it sweetness or be angry, ashamed or only
amused, at such a stroke. She had never thought of Hannah till you
were never meant for me?" "I cannot make speeches, Emma:" he soon cut
it all himself.
''''</BLOCKQUOTE>
''''For this example, I left the punctuation attached to the words.
The result is almost syntactically correct, but not quite.
Semantically, it almost makes sense, but not quite.''''

''''What happens if you increase the prefix length? Does the random
text make more sense?''''

*''''Once your program is working, you might want to try a mash-up:
if you analyze text from two or more books, the random
text you generate will blend the vocabulary and phrases from
the sources in interesting ways.''''

</DIV>=== 13.9&#XA0;&#XA0;Data structures ===

Using Markov analysis to generate random text is fun, but there is
also a point to this exercise: data structure selection. In your
solution to the previous exercises, you had to choose:

*How to represent the prefixes.

*How to represent the collection of possible suffixes.

*How to represent the mapping from each prefix to
the collection of possible suffixes.

Ok, the last one is the easy; the only mapping type we have
seen is a dictionary, so it is the natural choice.

For the prefixes, the most obvious options are string,
list of strings, or tuple of strings. For the suffixes,
one option is a list; another is a histogram (dictionary).

How should you choose? The first step is to think about
the operations you will need to implement for each data structure.
For the prefixes, we need to be able to remove words from
the beginning and add to the end. For example, if the current
prefix is &#X201C;Half a,&#X201D; and the next word is &#X201C;bee,&#X201D; you need
to be able to form the next prefix, &#X201C;a bee.&#X201D;

Your first choice might be a list, since it is easy to add
and remove elements, but we also need to be able to use the
prefixes as keys in a dictionary, so that rules out lists.
With tuples, you can&#X2019;t append or remove, but you can use
the addition operator to form a new tuple:
<PRE CLASS="verbatim">def shift(prefix, word):
    return prefix[1:] + (word,)
</PRE>
<TT>shift</TT> takes a tuple of words, <TT>prefix</TT>, and a string, 
<TT>word</TT>, and forms a new tuple that has all the words
in <TT>prefix</TT> except the first, and <TT>word</TT> added to
the end.

For the collection of suffixes, the operations we need to
perform include adding a new suffix (or increasing the frequency
of an existing one), and choosing a random suffix.

Adding a new suffix is equally easy for the list implementation
or the histogram. Choosing a random element from a list
is easy; choosing from a histogram is harder to do
efficiently (see Exercise&#XA0;13.7).

So far we have been talking mostly about ease of implementation,
but there are other factors to consider in choosing data structures.
One is run time. Sometimes there is a theoretical reason to expect
one data structure to be faster than other; for example, I mentioned
that the <TT>in</TT> operator is faster for dictionaries than for lists,
at least when the number of elements is large.

But often you don&#X2019;t know ahead of time which implementation will
be faster. One option is to implement both of them and see which
is better. This approach is called '''benchmarking'''. A practical
alternative is to choose the data structure that is
easiest to implement, and then see if it is fast enough for the
intended application. If so, there is no need to go on. If not,
there are tools, like the <TT>profile</TT> module, that can identify
the places in a program that take the most time.





The other factor to consider is storage space. For example, using a
histogram for the collection of suffixes might take less space because
you only have to store each word once, no matter how many times it
appears in the text. In some cases, saving space can also make your
program run faster, and in the extreme, your program might not run at
all if you run out of memory. But for many applications, space is a
secondary consideration after run time.

One final thought: in this discussion, I have implied that
we should use one data structure for both analysis and generation. But
since these are separate phases, it would also be possible to use one
structure for analysis and then convert to another structure for
generation. This would be a net win if the time saved during
generation exceeded the time spent in conversion.
=== 13.10&#XA0;&#XA0;Debugging ===




When you are debugging a program, and especially if you are
working on a hard bug, there are four things to try:
<DL CLASS="description"><DT CLASS="dt-description">'''reading:'''</DT><DD CLASS="dd-description"> Examine your code, read it back to yourself, and
check that it says what you meant to say.</DD><DT CLASS="dt-description">'''running:'''</DT><DD CLASS="dd-description"> Experiment by making changes and running different
versions. Often if you display the right thing at the right place
in the program, the problem becomes obvious, but sometimes you have to
spend some time to build scaffolding.</DD><DT CLASS="dt-description">'''ruminating:'''</DT><DD CLASS="dd-description"> Take some time to think! What kind of error
is it: syntax, runtime, semantic? What information can you get from
the error messages, or from the output of the program? What kind of
error could cause the problem you&#X2019;re seeing? What did you change
last, before the problem appeared?</DD><DT CLASS="dt-description">'''retreating:'''</DT><DD CLASS="dd-description"> At some point, the best thing to do is back
off, undoing recent changes, until you get back to a program that
works and that you understand. Then you can starting rebuilding.</DD></DL>
Beginning programmers sometimes get stuck on one of these activities
and forget the others. Each activity comes with its own failure
mode.

For example, reading your code might help if the problem is a
typographical error, but not if the problem is a conceptual
misunderstanding. If you don&#X2019;t understand what your program does, you
can read it 100 times and never see the error, because the error is in
your head.

Running experiments can help, especially if you run small, simple
tests. But if you run experiments without thinking or reading your
code, you might fall into a pattern I call &#X201C;random walk programming,&#X201D;
which is the process of making random changes until the program
does the right thing. Needless to say, random walk programming
can take a long time.




You have to take time to think. Debugging is like an
experimental science. You should have at least one hypothesis about
what the problem is. If there are two or more possibilities, try to
think of a test that would eliminate one of them.

Taking a break helps with the thinking. So does talking.
If you explain the problem to someone else (or even yourself), you
will sometimes find the answer before you finish asking the question.

But even the best debugging techniques will fail if there are too many
errors, or if the code you are trying to fix is too big and
complicated. Sometimes the best option is to retreat, simplifying the
program until you get to something that works and that you
understand.

Beginning programmers are often reluctant to retreat because
they can&#X2019;t stand to delete a line of code (even if it&#X2019;s wrong).
If it makes you feel better, copy your program into another file
before you start stripping it down. Then you can paste the pieces
back in a little bit at a time.

Finding a hard bug requires reading, running, ruminating, and
sometimes retreating. If you get stuck on one of these activities,
try the others.
=== 13.11&#XA0;&#XA0;Glossary ===

<DL CLASS="description"><DT CLASS="dt-description">'''deterministic:'''</DT><DD CLASS="dd-description"> Pertaining to a program that does the same
thing each time it runs, given the same inputs.
</DD><DT CLASS="dt-description">'''pseudorandom:'''</DT><DD CLASS="dd-description"> Pertaining to a sequence of numbers that appear
to be random, but are generated by a deterministic program.
</DD><DT CLASS="dt-description">'''default value:'''</DT><DD CLASS="dd-description"> The value given to an optional parameter if no
argument is provided.
</DD><DT CLASS="dt-description">'''override:'''</DT><DD CLASS="dd-description"> To replace a default value with an argument.
</DD><DT CLASS="dt-description">'''benchmarking:'''</DT><DD CLASS="dd-description"> The process of choosing between data structures
by implementing alternatives and testing them on a sample of the
possible inputs. 
</DD></DL>=== 13.12&#XA0;&#XA0;Exercises ===

<DIV CLASS="theorem">'''Exercise&#XA0;9'''&#XA0;&#XA0;
''
''''
''

''The &#X201C;rank&#X201D; of a word is its position in a list of words
sorted by frequency: the most common word has rank 1, the
second most common has rank 2, etc.''

''Zipf&#X2019;s law describes a relationship between the ranks and frequencies
of words in natural languages''<SUP>''1''</SUP>''. Specifically, it
predicts that the frequency, ''''<I>f</I>'''', of the word with rank ''''<I>r</I>'''' is:''
<TABLE CLASS="display dcenter"><TR VALIGN="middle"><TD CLASS="dcell">''<I>f</I>&#XA0;=&#XA0;<I>c</I>&#XA0;<I>r</I>''<SUP>''&#X2212;<I>s</I>''</SUP>''&#XA0;''</TD></TR>
</TABLE>
''
where ''''<I>s</I>'''' and ''''<I>c</I>'''' are parameters that depend on the language and the
text. If you take the logarithm of both sides of this equation, you
get:''

<TABLE CLASS="display dcenter"><TR VALIGN="middle"><TD CLASS="dcell">''log''''<I>f</I>&#XA0;=&#XA0;''''log''''<I>c</I>&#XA0;&#X2212;&#XA0;<I>s</I>&#XA0;''''log''''<I>r</I>&#XA0;''</TD></TR>
</TABLE>
''
So if you plot ''''log''''<I>f</I>'''' versus ''''log''''<I>r</I>'''', you should get
a straight line with slope ''''&#X2212;<I>s</I>'''' and intercept ''''log''''<I>c</I>''''.''

''Write a program that reads a text from a file, counts
word frequencies, and prints one line
for each word, in descending order of frequency, with
''''log''''<I>f</I>'''' and ''''log''''<I>r</I>''''. Use the graphing program of your
choice to plot the results and check whether they form
a straight line. Can you estimate the value of ''''<I>s</I>''''?
''
</DIV><HR CLASS="footnoterule"><DL CLASS="thefootnotes"><DT CLASS="dt-thefootnotes">
1</DT><DD CLASS="dd-thefootnotes">See
<TT>wikipedia.org/wiki/Zipf's_law</TT>
</DD></DL>
<HR>
<IMG SRC="previous_motif.gif" ALT="Previous">
<IMG SRC="contents_motif.gif" ALT="Up">
<IMG SRC="next_motif.gif" ALT="Next">