Archive:Think Python/Case study: data structure selection: Difference between revisions
wikademia>Whiteknight m Think Python: Automatically uploading HTML source of this book from http://www.greenteapress.com/thinkpython/html/. Will convert to wikitext in a separate step |
wikademia>Wikademia m moved Think Python/Case study: data structure selection to Archive:Think Python/Case study: data structure selection |
||
| (2 intermediate revisions by 2 users not shown) | |||
| Line 1: | Line 1: | ||
{{Think Python/Page}} | |||
== Chapter 13  Case study: data structure selection == | |||
=== 13.1  Word frequency analysis === | |||
As usual, you should at least attempt the following exercises | |||
before you read my solutions. | |||
<DIV CLASS="theorem">'''Exercise 1'''  '' | |||
before you read my solutions. | |||
Write a program that reads a file, breaks each line into | Write a program that reads a file, breaks each line into | ||
words, strips whitespace and punctuation from the words, and | words, strips whitespace and punctuation from the words, and | ||
converts them to lowercase. | converts them to lowercase.'' | ||
'' | |||
which contains space, tab, newline, etc., and | '' | ||
if we can make Python swear: | |||
''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’s see | |||
if we can make Python swear:'' | |||
<PRE CLASS="verbatim">''>>> import string | |||
>>> print string.punctuation | >>> print string.punctuation | ||
!"#$%&'()*+,-./:;<=>?@[\]^_`{|}~ | !"#$%&'()*+,-./:;<=>?@[\]^_`{|}~ | ||
''</PRE> | |||
''Also, you might consider using the string methods ''''<TT>strip</TT>'''', | |||
''''<TT>replace</TT>'''' and ''''<TT>translate</TT>''''.'' | |||
'' | |||
'''' | |||
'''' | |||
your favorite out-of-copyright book in plain text format. | '''' | ||
'''' | |||
'' | |||
</DIV><DIV CLASS="theorem">'''Exercise 2'''   | |||
''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 | you downloaded, skip over the header information at the beginning | ||
of the file, and process the rest of the words as before. | of the file, and process the rest of the words as before.'' | ||
the book, and the number of times each word is used. | |||
''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. | different books by different authors, written in different eras. | ||
Which author uses the most extensive vocabulary? | Which author uses the most extensive vocabulary? | ||
'' | |||
</DIV><DIV CLASS="theorem">'''Exercise 3'''  '' | |||
Modify the program from the previous exercise to print the | Modify the program from the previous exercise to print the | ||
20 most frequently-used words in the book. | 20 most frequently-used words in the book. | ||
''</DIV><DIV CLASS="theorem">'''Exercise 4'''  '' | |||
Modify the previous program to read a word list (see | Modify the previous program to read a word list (see | ||
Section  | Section ''''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 | are not in the word list. How many of them are typos? How many of | ||
them are common words that | them are common words that ''should'' be in the word list, and how | ||
many of them are really obscure? | many of them are really obscure? | ||
''</DIV>=== 13.2  Random numbers === | |||
outputs every time, so they are said to be | |||
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 | Determinism is usually a good thing, since we expect the same | ||
calculation to yield the same result. For some applications, though, | calculation to yield the same result. For some applications, though, | ||
we want the computer to be unpredictable. Games are an obvious | we want the computer to be unpredictable. Games are an obvious | ||
example, but there are more. | 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 | but there are ways to make it at least seem nondeterministic. One of | ||
them is to use algorithms that generate | them is to use algorithms that generate '''pseudorandom''' numbers. | ||
Pseudorandom numbers are not truly random because they are generated | Pseudorandom numbers are not truly random because they are generated | ||
by a deterministic computation, but just by looking at the numbers it | by a deterministic computation, but just by looking at the numbers it | ||
is all but impossible to distinguish them from random. | 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 “random” from | pseudorandom numbers (which I will simply call “random” from | ||
here on). | 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 | between 0.0 and 1.0 (including 0.0 but not 1.0). Each time you | ||
call | call <TT>random</TT>, you get the next number in a long series. To see a | ||
sample, run this loop: | sample, run this loop: | ||
<PRE CLASS="verbatim">import random | |||
for i in range(10): | for i in range(10): | ||
x = random.random() | x = random.random() | ||
print x | 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">>>> random.randint(5, 10) | |||
5 | 5 | ||
>>> random.randint(5, 10) | >>> random.randint(5, 10) | ||
9 | 9 | ||
</PRE> | |||
To choose an element from a sequence at random, you can use | |||
<TT>choice</TT>: | |||
<PRE CLASS="verbatim">>>> t = [1, 2, 3] | |||
>>> random.choice(t) | >>> random.choice(t) | ||
2 | 2 | ||
>>> random.choice(t) | >>> random.choice(t) | ||
3 | 3 | ||
</PRE> | |||
The <TT>random</TT> module also provides functions to generate | |||
random values from continuous distributions including | random values from continuous distributions including | ||
Gaussian, exponential, gamma, and a few more. | Gaussian, exponential, gamma, and a few more. | ||
a histogram as defined in Section  | <DIV CLASS="theorem">'''Exercise 5'''   | ||
''Write a function named ''<CODE>''choose_from_hist''</CODE>'' that takes | |||
a histogram as defined in Section ''''11.1'''' and returns a | |||
random value from the histogram, chosen with probability | random value from the histogram, chosen with probability | ||
in proportion to frequency. For example, for this histogram: | in proportion to frequency. For example, for this histogram:'' | ||
<PRE CLASS="verbatim">''>>> t = ['a', 'a', 'b'] | |||
>>> h = histogram(t) | >>> h = histogram(t) | ||
>>> print h | >>> print h | ||
{'a': 2, 'b': 1} | {'a': 2, 'b': 1} | ||
''</PRE> | |||
with probability | ''your function should ''''<TT>’a’</TT>'''' with probability ''''2/3'''' and ''<CODE>'''b'''</CODE>'' | ||
with probability ''''1/3''''. | |||
words in the file: | '' | ||
</DIV>=== 13.3  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): | def process_file(filename): | ||
| Line 119: | Line 168: | ||
hist = process_file('emma.txt') | hist = process_file('emma.txt') | ||
</PRE> | |||
passing them one at a time to | 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, | |||
hyphens with spaces before using | passing them one at a time to <CODE>process_line</CODE>. The histogram | ||
list of strings. It traverses the list of words and uses | <TT>h</TT> is being used as an accumulator. | ||
and | |||
<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 “converted;” remember that | is a shorthand to say that strings are “converted;” remember that | ||
string are immutable, so methods like | string are immutable, so methods like <TT>strip</TT> and <TT>lower</TT> | ||
return new strings.) | return new strings.) | ||
item or incrementing an existing one. | |||
the frequencies in the histogram: | 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()) | return sum(h.values()) | ||
</PRE> | |||
the dictionary: | The number of different words is just the number of items in | ||
the dictionary: | |||
<PRE CLASS="verbatim">def different_words(h): | |||
return len(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) | 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 | Number of different words: 7212 | ||
</PRE>=== 13.4  Most common words === | |||
word-frequency tuples, sorted in reverse order by frequency: | |||
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 = [] | t = [] | ||
for key, value in h.items(): | for key, value in h.items(): | ||
| Line 149: | Line 221: | ||
t.sort(reverse=True) | t.sort(reverse=True) | ||
return t | 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:' | print 'The most common words are:' | ||
for freq, word in t[0:10]: | for freq, word in t[0:10]: | ||
print word, '\t', freq | print word, '\t', freq | ||
</PRE> | |||
And here are the results from ''Emma'': | |||
<PRE CLASS="verbatim">The most common words are: | |||
to 5242 | to 5242 | ||
the 5204 | the 5204 | ||
| Line 164: | Line 240: | ||
was 2400 | was 2400 | ||
she 2364 | she 2364 | ||
</PRE>=== 13.5  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 | number of arguments. It is possible to write user-defined functions | ||
with optional arguments, too. For example, here is a function that | with optional arguments, too. For example, here is a function that | ||
prints the most common words in a histogram | prints the most common words in a histogram | ||
<PRE CLASS="verbatim">def print_most_common(hist, num=10) | |||
t = most_common(hist) | t = most_common(hist) | ||
print 'The most common words are:' | print 'The most common words are:' | ||
for freq, word in t[0:num]: | for freq, word in t[0:num]: | ||
print word, '\t', freq | print word, '\t', freq | ||
</PRE> | |||
The | The first parameter is required; the second is optional. | ||
The '''default value''' of <TT>num</TT> is 10. | |||
words, the optional argument | |||
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 | the required parameters have to come first, followed by the | ||
optional ones. | optional ones. | ||
=== 13.6  Dictionary subtraction === | |||
from | |||
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 | 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 | set (the words in the book) that are not in another set (the | ||
words in the list). | words in the list). | ||
new dictionary that contains all the keys from | |||
in | <TT>subtract</TT> takes dictionaries <TT>d1</TT> and <TT>d2</TT> and returns a | ||
set them all to None. | new dictionary that contains all the keys from <TT>d1</TT> that are not | ||
in <TT>d2</TT>. Since we don’t really care about the values, we | |||
set them all to None. | |||
<PRE CLASS="verbatim">def subtract(d1, d2): | |||
res = dict() | res = dict() | ||
for key in d1: | for key in d1: | ||
| Line 194: | Line 294: | ||
res[key] = None | res[key] = None | ||
return res | return res | ||
</PRE> | |||
we can use | 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) | diff = subtract(hist, words) | ||
| Line 202: | Line 304: | ||
for word in diff.keys(): | for word in diff.keys(): | ||
print word, | 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 | rencontre jane's blanche woodhouses disingenuousness | ||
friend's venice apartment ... | friend's venice apartment ... | ||
</PRE> | |||
Some of these words are names and possessives. Others, like | |||
“rencontre,” are no longer in common use. But a few are common | “rencontre,” are no longer in common use. But a few are common | ||
words that should really be in the list! | words that should really be in the list! | ||
<DIV CLASS="theorem">'''Exercise 6'''   | |||
'' | |||
'' | |||
''Python provides a data structure called ''''<TT>set</TT>'''' that provides many | |||
common set operations. Read the documentation at | 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 | that uses set subtraction to find words in the book that are not in | ||
the word list. | the word list. | ||
'' | |||
</DIV>=== 13.7  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 | is to build a list with multiple copies of each word, according | ||
to the observed frequency, and then choose from the list: | to the observed frequency, and then choose from the list: | ||
<PRE CLASS="verbatim">def random_word(h): | |||
t = [] | t = [] | ||
for word, freq in h.items(): | for word, freq in h.items(): | ||
| Line 222: | Line 337: | ||
return random.choice(t) | return random.choice(t) | ||
</PRE> | |||
copies of the string | The expression <TT>[word] * freq</TT> creates a list with <TT>freq</TT> | ||
method is similar to | copies of the string <TT>word</TT>. The <TT>extend</TT> | ||
a sequence. | method is similar to <TT>append</TT> except that the argument is | ||
a sequence. | |||
<DIV CLASS="theorem">'''Exercise 7'''  '' | |||
'' | |||
''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 | choose a random word, it rebuilds the list, which is as big as | ||
the original book. An obvious improvement is to build the list | the original book. An obvious improvement is to build the list | ||
once and then make multiple selections, but the list is still big. | once and then make multiple selections, but the list is still big.'' | ||
frequencies (see Exercise  | |||
in this list is the total number of words in the book, | ''An alternative is:'' | ||
(See Exercise  | |||
number would be inserted in the cumulative sum. | *''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 ''''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 ''''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. | word from the book. | ||
'' | |||
sense of the vocabulary, you probably won’t get a sentence: | </DIV>=== 13.8  Markov analysis === | ||
If you choose words from the book at random, you can get a | |||
sense of the vocabulary, you probably won’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 | is no relationship between successive words. For example, in | ||
a real sentence you would expect an article like “the” to | a real sentence you would expect an article like “the” to | ||
be followed by an adjective or a noun, and probably not a verb | be followed by an adjective or a noun, and probably not a verb | ||
or adverb. | or adverb. | ||
One way to measure these kinds of relationships is Markov | |||
analysis, which characterizes, for a given sequence of words, | analysis, which characterizes, for a given sequence of words, | ||
the probability of the word that comes next. For example, | the probability of the word that comes next. For example, | ||
the song | the song ''Eric, the Half a Bee'' begins: | ||
<BLOCKQUOTE CLASS="quote"> | |||
Half a bee, philosophically,<BR> | Half a bee, philosophically,<BR> | ||
Must, ipso facto, half not be.<BR> | Must, ipso facto, half not be.<BR> | ||
| Line 253: | Line 392: | ||
When half the bee is not a bee<BR> | When half the bee is not a bee<BR> | ||
Due to some ancient injury?<BR> | Due to some ancient injury?<BR> | ||
</BLOCKQUOTE> | |||
In this text, | In this text, | ||
the phrase “half the” is always followed by the word “bee,” | the phrase “half the” is always followed by the word “bee,” | ||
but the phrase “the bee” might be followed by either | but the phrase “the bee” might be followed by either | ||
“has” or “is”. | “has” or “is”. | ||
The result of Markov analysis is a mapping from each prefix | |||
(like “half the” and “the bee”) to all possible suffixes | (like “half the” and “the bee”) to all possible suffixes | ||
(like “has” and “is”). | (like “has” and “is”). | ||
Given this mapping, you can generate a random text by | |||
starting with any prefix and choosing at random from the | starting with any prefix and choosing at random from the | ||
possible suffixes. Next, you can combine the end of the | possible suffixes. Next, you can combine the end of the | ||
prefix and the new suffix to form the next prefix, and repeat. | prefix and the new suffix to form the next prefix, and repeat. | ||
For example, if you start with the prefix “Half a,” then the | |||
next word has to be “bee,” because the prefix only appears | next word has to be “bee,” because the prefix only appears | ||
once in the text. The next prefix is “a bee,” so the | once in the text. The next prefix is “a bee,” so the | ||
next suffix might be “philosophically,” “be” or “due.” | next suffix might be “philosophically,” “be” or “due.” | ||
In this example the length of the prefix is always two, but | |||
you can do Markov analysis with any prefix length. The length | you can do Markov analysis with any prefix length. The length | ||
of the prefix is called the “order” of the analysis. | of the prefix is called the “order” of the analysis. | ||
Markov analysis: | <DIV CLASS="theorem">'''Exercise 8'''  '' | ||
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 | analysis. The result should be a dictionary that maps from | ||
prefixes to a collection of possible suffixes. The collection | prefixes to a collection of possible suffixes. The collection | ||
| Line 277: | Line 432: | ||
an appropriate choice. You can test your program with prefix | an appropriate choice. You can test your program with prefix | ||
length two, but you should write the program in a way that makes | length two, but you should write the program in a way that makes | ||
it easy to try other lengths. | it easy to try other lengths.'' | ||
based on the Markov analysis. Here is an example from | |||
with prefix length 2: | *''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 | 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 | 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 | were never meant for me?" "I cannot make speeches, Emma:" he soon cut | ||
it all himself. | it all himself. | ||
''''</BLOCKQUOTE> | |||
''''For this example, I left the punctuation attached to the words. | |||
The result is almost syntactically correct, but not quite. | The result is almost syntactically correct, but not quite. | ||
Semantically, it almost makes sense, but not quite. | Semantically, it almost makes sense, but not quite.'''' | ||
text make more sense? | |||
''''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 | if you analyze text from two or more books, the random | ||
text you generate will blend the vocabulary and phrases from | text you generate will blend the vocabulary and phrases from | ||
the sources in interesting ways. | the sources in interesting ways.'''' | ||
</DIV>=== 13.9  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 | also a point to this exercise: data structure selection. In your | ||
solution to the previous exercises, you had to choose: | solution to the previous exercises, you had to choose: | ||
the collection of possible suffixes. | |||
seen is a dictionary, so it is the natural choice. | *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, | list of strings, or tuple of strings. For the suffixes, | ||
one option is a list; another is a histogram (dictionary). | 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. | the operations you will need to implement for each data structure. | ||
For the prefixes, we need to be able to remove words from | For the prefixes, we need to be able to remove words from | ||
the beginning and add to the end. For example, if the current | the beginning and add to the end. For example, if the current | ||
prefix is “Half a,” and the next word is “bee,” you need | prefix is “Half a,” and the next word is “bee,” you need | ||
to be able to form the next prefix, “a bee.” | to be able to form the next prefix, “a bee.” | ||
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 | and remove elements, but we also need to be able to use the | ||
prefixes as keys in a dictionary, so that rules out lists. | prefixes as keys in a dictionary, so that rules out lists. | ||
With tuples, you can’t append or remove, but you can use | With tuples, you can’t append or remove, but you can use | ||
the addition operator to form a new tuple: | the addition operator to form a new tuple: | ||
<PRE CLASS="verbatim">def shift(prefix, word): | |||
return prefix[1:] + (word,) | return prefix[1:] + (word,) | ||
</PRE> | |||
<TT>shift</TT> takes a tuple of words, <TT>prefix</TT>, and a string, | |||
in | <TT>word</TT>, and forms a new tuple that has all the words | ||
the end. | 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 | perform include adding a new suffix (or increasing the frequency | ||
of an existing one), and choosing a random suffix. | 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 | or the histogram. Choosing a random element from a list | ||
is easy; choosing from a histogram is harder to do | is easy; choosing from a histogram is harder to do | ||
efficiently (see Exercise  | efficiently (see Exercise 13.7). | ||
So far we have been talking mostly about ease of implementation, | |||
but there are other factors to consider in choosing data structures. | but there are other factors to consider in choosing data structures. | ||
One is run time. Sometimes there is a theoretical reason to expect | One is run time. Sometimes there is a theoretical reason to expect | ||
one data structure to be faster than other; for example, I mentioned | one data structure to be faster than other; for example, I mentioned | ||
that the | that the <TT>in</TT> operator is faster for dictionaries than for lists, | ||
at least when the number of elements is large. | at least when the number of elements is large. | ||
But often you don’t know ahead of time which implementation will | |||
be faster. One option is to implement both of them and see which | be faster. One option is to implement both of them and see which | ||
is better. This approach is called | is better. This approach is called '''benchmarking'''. A practical | ||
alternative is to choose the data structure that is | alternative is to choose the data structure that is | ||
easiest to implement, and then see if it is fast enough for the | 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, | intended application. If so, there is no need to go on. If not, | ||
there are tools, like the | there are tools, like the <TT>profile</TT> module, that can identify | ||
the places in a program that take the most time. | 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 | 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 | you only have to store each word once, no matter how many times it | ||
| Line 335: | Line 529: | ||
program run faster, and in the extreme, your program might not run at | 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 | all if you run out of memory. But for many applications, space is a | ||
secondary consideration after run time. | 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 | 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 | since these are separate phases, it would also be possible to use one | ||
structure for analysis and then convert to another structure for | structure for analysis and then convert to another structure for | ||
generation. This would be a net win if the time saved during | generation. This would be a net win if the time saved during | ||
generation exceeded the time spent in conversion. | generation exceeded the time spent in conversion. | ||
=== 13.10  Debugging === | |||
working on a hard bug, there are four things to try: | |||
check that it says what you meant to say. | |||
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 | versions. Often if you display the right thing at the right place | ||
in the program, the problem becomes obvious, but sometimes you have to | in the program, the problem becomes obvious, but sometimes you have to | ||
spend some time to build scaffolding. | 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 | is it: syntax, runtime, semantic? What information can you get from | ||
the error messages, or from the output of the program? What kind of | the error messages, or from the output of the program? What kind of | ||
error could cause the problem you’re seeing? What did you change | error could cause the problem you’re seeing? What did you change | ||
last, before the problem appeared? | 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 | off, undoing recent changes, until you get back to a program that | ||
works and that you understand. Then you can starting rebuilding. | 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 | and forget the others. Each activity comes with its own failure | ||
mode. | mode. | ||
For example, reading your code might help if the problem is a | |||
typographical error, but not if the problem is a conceptual | typographical error, but not if the problem is a conceptual | ||
misunderstanding. If you don’t understand what your program does, you | misunderstanding. If you don’t understand what your program does, you | ||
can read it 100 times and never see the error, because the error is in | can read it 100 times and never see the error, because the error is in | ||
your head. | your head. | ||
Running experiments can help, especially if you run small, simple | |||
tests. But if you run experiments without thinking or reading your | tests. But if you run experiments without thinking or reading your | ||
code, you might fall into a pattern I call “random walk programming,” | code, you might fall into a pattern I call “random walk programming,” | ||
which is the process of making random changes until the program | which is the process of making random changes until the program | ||
does the right thing. Needless to say, random walk programming | does the right thing. Needless to say, random walk programming | ||
can take a long time. | 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 | experimental science. You should have at least one hypothesis about | ||
what the problem is. If there are two or more possibilities, try to | what the problem is. If there are two or more possibilities, try to | ||
think of a test that would eliminate one of them. | 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 | If you explain the problem to someone else (or even yourself), you | ||
will sometimes find the answer before you finish asking the question. | 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 | errors, or if the code you are trying to fix is too big and | ||
complicated. Sometimes the best option is to retreat, simplifying the | complicated. Sometimes the best option is to retreat, simplifying the | ||
program until you get to something that works and that you | program until you get to something that works and that you | ||
understand. | understand. | ||
Beginning programmers are often reluctant to retreat because | |||
they can’t stand to delete a line of code (even if it’s wrong). | they can’t stand to delete a line of code (even if it’s wrong). | ||
If it makes you feel better, copy your program into another file | If it makes you feel better, copy your program into another file | ||
before you start stripping it down. Then you can paste the pieces | before you start stripping it down. Then you can paste the pieces | ||
back in a little bit at a time. | 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, | sometimes retreating. If you get stuck on one of these activities, | ||
try the others. | try the others. | ||
=== 13.11  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. | 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. | 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. | 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 | by implementing alternatives and testing them on a sample of the | ||
possible inputs. | possible inputs. | ||
</DD></DL>=== 13.12  Exercises === | |||
<DIV CLASS="theorem">'''Exercise 9'''   | |||
'' | |||
'''' | |||
'' | |||
''The “rank” of a word is its position in a list of words | |||
sorted by frequency: the most common word has rank 1, the | sorted by frequency: the most common word has rank 1, the | ||
second most common has rank 2, etc. | second most common has rank 2, etc.'' | ||
of words in natural languages | |||
predicts that the frequency, | ''Zipf’s law describes a relationship between the ranks and frequencies | ||
</TABLE> | of words in natural languages''<SUP>''1''</SUP>''. Specifically, it | ||
where | 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> = <I>c</I> <I>r</I>''<SUP>''−<I>s</I>''</SUP>'' ''</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 | text. If you take the logarithm of both sides of this equation, you | ||
get: | get:'' | ||
</TABLE> | |||
So if you plot | <TABLE CLASS="display dcenter"><TR VALIGN="middle"><TD CLASS="dcell">''log''''<I>f</I> = ''''log''''<I>c</I> − <I>s</I> ''''log''''<I>r</I> ''</TD></TR> | ||
a straight line with slope | </TABLE> | ||
'' | |||
So if you plot ''''log''''<I>f</I>'''' versus ''''log''''<I>r</I>'''', you should get | |||
a straight line with slope ''''−<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 | word frequencies, and prints one line | ||
for each word, in descending order of frequency, with | 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 | choice to plot the results and check whether they form | ||
a straight line. Can you estimate the value of | 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> | <TT>wikipedia.org/wiki/Zipf's_law</TT> | ||
</DD></DL> | |||
<HR> | <HR> | ||
<IMG SRC="previous_motif.gif" ALT="Previous"> | |||
<IMG SRC="contents_motif.gif" ALT="Up"> | |||
<IMG SRC="next_motif.gif" ALT="Next"> | |||