13.7: Random words
- Page ID
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:
def random_word(h): t =  for word, freq in h.items(): t.extend([word] * freq) return random.choice(t)
[word] * freq creates a list with
freq copies of the string
extend method is similar to append except that the argument is a sequence.
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:
keysto get a list of the words in the book.
- Build a list that contains the cumulative sum of the word frequencies (see Exercise 10.15.2). The last item in this list is the total number of words in the book, \(n\).
- Choose a random number from 1 to \(n\). Use a bisection search (See Exercise 10.15.10) 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.