Sorting and Sets
Sorting, Sets & Tuples
- You should already know
- Lists, sort() and changing a list versus replacing it (chapter 5); reading Shakespeare (chapter 6); the word-counting loop (chapter 7).
- You'll build
- A top-ten list of Shakespeare's most common words, and a game that asks which of two words he used more.
- You'll be able to
- Make a sorted copy of a list, take the first few items with a slice, pack and unpack pairs with tuples, loop over a dictionary's keys and values together, and use a set to find distinct items.
- You need
- This page. Python runs in the panel beside it; installing Python on your own computer comes in chapter 17.
At the end of Reading a File, we asked which words Shakespeare uses most. In Dictionaries, we counted every one of them. But the dictionary keeps its words in the order it first met them, not in order of how often they appear. 'love' is in there somewhere, with its count beside it, between words that appear once.
To answer the question, we need to put the counts in order and look at the top few. We'll practice on something small first: a leaderboard for the guessing game from Loops. Then we'll rank all of Shakespeare, find out how many different words he used, and finish with a game that tests how well you know his vocabulary.
A Sorted Copy
In Lists, sort() put a list in order. It changed the list itself, and the original order was gone.
Python has a second way to sort. Open the Python panel and try it. On a small screen, use the Python button. As before, type only what follows >>>.
>>> guesses = [7, 4, 9, 4] >>> sorted(guesses) [4, 4, 7, 9] >>> guesses [7, 4, 9, 4]
sorted() gives back a new list in order. The original list is left alone. That's the difference from sort():
guesses.sort()changesguessesand gives backNone.sorted(guesses)makes a sorted copy and leavesguessesas it was.
To keep the sorted copy, assign it to a name:
>>> in_order = sorted(guesses) >>> in_order [4, 4, 7, 9] >>> sorted(['pear', 'apple', 'fig']) ['apple', 'fig', 'pear'] >>> # Your turn: Make a list of four friends' names and display a >>> # sorted copy. Then display the original list. Has it changed?
Strings come out in alphabetical order, with the same capital-letter surprise you saw in Lists: 'Zoe' comes before 'adam'.
Biggest First
A guessing-game leaderboard wants the fewest guesses first, which is what sorted() gives us. A word count wants the opposite: the biggest number first. In Lists, we sorted and then reversed. sorted() can do both at once:
>>> sorted(guesses, reverse=True) [9, 7, 4, 4]
reverse=True is a keyword argument. Most arguments are just values, and Python knows what each one means from its position. A keyword argument names the setting it changes. Here it switches on reverse order. Leave it out, and sorted() uses its usual order, smallest first.
The First Few
A leaderboard doesn't show everyone, only the top three. We need the first few items of a list. Python calls that a slice:
>>> in_order[:3] [4, 4, 7] >>> in_order[:1] [4] >>> in_order[:10] [4, 4, 7, 9]
[:3] means "from the start, up to but not including position 3", so it gives us positions 0, 1 and 2. That's the same rule as range(): the stop isn't included.
Asking for more items than the list has isn't an error. in_order[:10] just gives back all four.
A slice is a new list, like sorted(). Taking one doesn't change the original. You can put a number before the colon, too: in_order[1:3] starts at position 1. We'll only need the first few items in this chapter.
>>> planets = ['Mercury', 'Venus', 'Earth', 'Mars', 'Jupiter'] >>> planets[:2] ['Mercury', 'Venus'] >>> # Your turn: Show the first three planets. Then show a sorted >>> # copy's first three. Predict each answer before you press Enter.
Pairs That Stay Together
A score on its own isn't much of a leaderboard. We need the name next to the number, and the two have to stay together when we sort.
Python has a small collection for that, called a tuple:
>>> best = ('Ada', 4) >>> best[0] 'Ada' >>> best[1] 4
A tuple looks like a list with parentheses instead of square brackets. You ask for its items by position in the same way. The difference is that a tuple can't be changed once it's made. Try best[1] = 3 and you'll see a TypeError. That suits a pair like this: Ada's name and Ada's score belong together.
You can also take a tuple apart into separate names in one step. This is called unpacking:
>>> name, score = best >>> name 'Ada' >>> score 4 >>> # Your turn: Make a tuple with a city and its population. Unpack it >>> # into two names and display each one.
The first name gets the first item and the second name gets the second. The order is all that matters. If you wrote score, name = best, score would hold 'Ada'. Python can't tell which name you meant for what.
Keys and Values Together
Here are the guessing-game results in a dictionary, a player's name for each key and their number of guesses as its value:
>>> scores = {'Ada': 4, 'Sam': 7, 'Kai': 4, 'Mo': 9} >>> list(scores.items()) [('Ada', 4), ('Sam', 7), ('Kai', 4), ('Mo', 9)]
items() gives each entry as a tuple: the key, then its value. (list() is only there so the panel can display them all at once, just as it was with range().)
That means a loop can unpack each pair as it goes:
# Try it: Add yourself to the dictionary. Then swap the names in the # for line, so it reads for taken, name in ... What prints now, and # why? # Each Run starts fresh. scores = {'Ada': 4, 'Sam': 7, 'Kai': 4, 'Mo': 9} for name, taken in scores.items(): print(name, taken)
In Dictionaries, we looped over the keys and looked up each value with counts[word]. That still works. items() gives us both at once, with a name for each, so the loop is easier to read.
A Leaderboard
Now we can put the pieces together. We'll build a list of tuples, sort it, and show the first three.
# Try it: Add your own name and score to the dictionary. Where do you # land? Then give a new player 4 guesses and predict where they'll # appear before you run it. # Each Run starts fresh. scores = {'Ada': 4, 'Sam': 7, 'Kai': 4, 'Mo': 9, 'Lee': 6} ranking = [] for name, taken in scores.items(): ranking.append((taken, name)) ranking = sorted(ranking) print('Fewest guesses wins!') for taken, name in ranking[:3]: print(name, taken)
You should see Ada and Kai with 4, then Lee with 6.
There are two pairs of parentheses in ranking.append((taken, name)). The outer pair belongs to append(). The inner pair makes the tuple, so each entry in ranking is one tuple, not two separate values.
Notice which way round the tuple goes: the number of guesses first, then the name. That's what makes the sort work. When Python sorts tuples, it compares their first items. Only when those are equal does it look at the second items. So the leaderboard is ordered by guesses, and players with the same number of guesses are in alphabetical order.
Shakespeare's Top Ten
Now for the question we've been carrying since Reading a File. Before you run this, write down the three words you think Shakespeare uses most.
The first half is your counter from Dictionaries, using += from Loops. The second half is the leaderboard, with two changes: the biggest count comes first, and we show ten instead of three.
# Before you run it: write down your guess for the top three words. # Counting a whole book takes a few seconds. # Each Run starts fresh. text = open('shakespeare.txt').read() counts = {} for word in text.split(): word = word.lower() word = word.strip('.,!?;:') if word != '': if word in counts: counts[word] += 1 else: counts[word] = 1 ranking = [] for word, count in counts.items(): ranking.append((count, word)) ranking = sorted(ranking, reverse=True) for count, word in ranking[:10]: print(word, count)
Here's what you should see:
| Word | Count |
|---|---|
| the | 30,429 |
| and | 28,450 |
| i | 21,664 |
| to | 20,673 |
| of | 18,855 |
| a | 16,214 |
| you | 14,370 |
| my | 13,154 |
| in | 12,423 |
| that | 11,780 |
Did you guess 'the'? Most people do. Did you guess 'love'? It isn't there.
This isn't something special about Shakespeare. Count the words in a newspaper, a text message thread or this book, and you'll get almost the same list. The most common words in English are the small ones that hold sentences together. Notice 'i' in third place, though: plays are full of people talking about themselves.
Skip the Dull Words
To find words that say something about Shakespeare, we need to skip the ones that would top any list. Programmers call these stop words. We'll keep our own list of them and leave them out of the ranking.
# Try it: Run it and look at the new top ten. Add the dull ones to the # boring list and run it again. How many words do you need to add # before a word like lord or king reaches the top? # Each Run starts fresh. text = open('shakespeare.txt').read() counts = {} for word in text.split(): word = word.lower() word = word.strip('.,!?;:') if word != '': if word in counts: counts[word] += 1 else: counts[word] = 1 boring = ['the', 'and', 'i', 'to', 'of', 'a', 'you', 'my', 'in', 'that'] ranking = [] for word, count in counts.items(): if word not in boring: ranking.append((count, word)) ranking = sorted(ranking, reverse=True) for count, word in ranking[:10]: print(word, count)
not in is the opposite of in: it's True when the word isn't in the list. Only interesting words get into ranking. The counting loop doesn't change at all. We're choosing which counts to rank, not which words to count.
The first time, you'll see another dull top ten: is, not, with, me, it. Keep going. Somewhere around forty boring words, the first real words arrive: lord (3,082), king (2,991) and sir (2,950). Along the way, you'll pass thou (5,831), thy and thee. Do they count as dull? That's your call. There's no single right list of stop words, only one that suits your question.
How Many Different Words?
Here's another question about Shakespeare's vocabulary. Not which words he used most, but how many different words he used at all.
Python has a collection made for this, called a set. A set keeps one copy of each item, however many times it appears:
>>> votes = ['tea', 'coffee', 'tea', 'water', 'coffee', 'tea'] >>> len(votes) 6 >>> len(set(votes)) 3 >>> sorted(set(votes)) ['coffee', 'tea', 'water'] >>> 'tea' in set(votes) True
set(votes) drops the repeats. len() counts what's left, and sorted() turns it back into an ordered list. Now try set(votes) on its own. The braces look like a dictionary's, but there are no keys and values, just items. The order isn't the one you typed, and it might not even match someone else's screen. A set doesn't keep items in any particular order, which is why we usually sort it before showing it.
A string is a collection of characters, so a set works on one word too:
>>> len(set('banana')) 3 >>> sorted(set('banana')) ['a', 'b', 'n'] >>> # Your turn: How many different letters are in your name? Predict, >>> # then check with len(set(...)). Does a capital letter count as >>> # different?
Now let's ask about Shakespeare:
# Before you run it: will the second number be closer to 900,000, # 100,000 or 10,000? Then compare the second and third numbers. Why # are they different? # Each Run starts fresh. text = open('shakespeare.txt').read() words = text.split() clean_words = [] for word in words: word = word.lower() word = word.strip('.,!?;:') if word != '': clean_words.append(word) print('Words:', len(words)) print('Different strings:', len(set(words))) print('Different cleaned words:', len(set(clean_words))) print(sorted(set(clean_words))[:15])
There are 966,506 words, but only 71,598 different strings. Clean them first and the number halves to 36,161. Without cleaning, 'Love', 'love' and 'love,' are three different strings. With it, they're one word.
That last number should look familiar. It's the same as len(counts) from Dictionaries: a dictionary has one key for each different word, and so does a set. Two routes, one answer.
The last line shows the first fifteen words in sorted order, and they aren't words at all: '#100]', '$5,000)', '&c'. Symbols sort before letters, so the leftovers that our cleaning rule missed all gather at the front. Some of them come from the Gutenberg license at the end of the file. Every count in this chapter includes a little of this noise. It's too small to change the top ten, but it's a good reminder that a program counts what you tell it to, not what you meant.
Which Word Wins?
Let's finish with a game. The program shows two words and asks which one Shakespeare used more. Get it right and your streak goes up. Get it wrong and the game is over.
We need to pick two words at random. In Loops, random.randint() chose a random number. The same module has random.choice(), which chooses a random item from a list:
import random word = random.choice(['love', 'hate', 'life', 'death'])
Here's the game. The top half is the counting loop again.
# Play a few rounds. Then try the changes listed after the program. # Counting the book takes a few seconds before the first question. # Each Run starts fresh. import random text = open('shakespeare.txt').read() counts = {} for word in text.split(): word = word.lower() word = word.strip('.,!?;:') if word != '': if word in counts: counts[word] += 1 else: counts[word] = 1 choices = ['love', 'hate', 'life', 'death', 'day', 'night', 'king', 'queen', 'heaven', 'hell', 'romeo', 'juliet', 'sword', 'crown', 'you', 'thou', 'war', 'peace', 'gold', 'silver'] streak = 0 while True: first = random.choice(choices) second = random.choice(choices) while second == first: second = random.choice(choices) answer = input(f'Which did Shakespeare use more, {first} or {second}? ') answer = answer.lower() if answer == first: other = second elif answer == second: other = first else: print("That isn't one of the two words.") break print(first, counts[first], '|', second, counts[second]) if counts[answer] >= counts[other]: streak += 1 print('Right! Your streak is', streak) else: print('Wrong! Your final streak is', streak) break
A few things to notice:
- Two different words. The inner
whileloop picks again untilsecondisn't the same asfirst. Otherwise you could be asked whetherlovebeatslove. otheris the word you didn't pick. Once we know which word was chosen, comparingcounts[answer]withcounts[other]works whichever way round the question was asked.>=is fair to ties. If two words had the same count, either answer would be right. None of these twenty tie, but the game doesn't need to know that.
Some of these are closer than you'd think. Try life against death before you look anything up.
Make the Game Yours
Pick one change at a time and check it before trying another.
- Choose your own words. Replace the list with words you're curious about. Check each one is a key in
countsfirst, or the lookup will fail with aKeyError. - Let the counts choose. Build
choicesfrom the ranking instead of typing it: sort the counts as in Skip the Dull Words, then loop overranking[:100]and append each word. The game gets harder, because you won't know which words are coming. - Play again. Wrap the game in another loop that asks
Play again? (yes/no)after a wrong answer, like the castle adventure in Loops. Keep abeststreak that survives between games.
Your Turn
# Before you run this, write down what you think each line will print. # Write your prediction below before running. # After the first run, edit the code and predict again. # Each Run starts fresh. numbers = [3, 1, 2] copy = sorted(numbers) result = numbers.sort() print(copy) print(result) print(numbers)
Think about what each one gives back, and what each one changes.
Find the Bug: Swapped Scores
This program should show the three most-played songs, most plays first: the name, then its number of plays. It runs without an error, but the output is wrong.
# Run it and look closely at the output. Then fix one line. # Each Run starts fresh. plays = {'Jolene': 14, 'Hello': 22, 'Formation': 9, 'Dakiti': 17} ranking = [] for song, count in plays.items(): ranking.append((count, song)) ranking = sorted(ranking, reverse=True) for song, count in ranking[:3]: print(song, count)
The names in a for line don't decide what goes where. The order does.
On Your Own: Quiz Champions
# Five friends played a quiz. Display the three highest scores, best # first, one per line: the player's name, then their points. # Check that: # - Sam (18), Mo (15) and Ada (12) appear, in that order. # - Kai and Lee don't appear at all. # - The scores dictionary is unchanged at the end. Print it to check. # Then change Kai's score to 20. Predict the new top three first. # Each Run starts fresh. points = {'Ada': 12, 'Sam': 18, 'Kai': 9, 'Mo': 15, 'Lee': 11}
Hint: What should each entry in the ranking look like?
The leaderboard put the number first and the name second, so sorting compared numbers. Loop over points.items() and append one tuple for each player.
Hint: How do you get the best three?
sorted(..., reverse=True) puts the biggest scores first. Then loop over a slice of the first three and unpack each tuple in the same order you built it.
Optional: Words Used Only Once
How many words did Shakespeare use exactly once? Use your counter, then loop over counts.items() and add one to a total whenever a count is 1. Before you run it, guess what fraction of the 36,161 different words it will be.
Then display a sorted few of them. Are they real words, mistakes in our cleaning, or both?
In Your Own Words
Write one sentence explaining what sorted() gives back that sort() doesn't. Then write one sentence explaining what a set keeps and what it throws away.
What's Next?
Look back at this chapter's Shakespeare programs. Each one starts with the same ten lines of counting. If we improve the cleaning rule, we'd have to change it in every copy.
In Functions, we'll give those lines a name, so one copy can do the counting for every program that needs it.
Optional Projects to Build Next
- Hangman — Build a letter-guessing game, then let Shakespeare choose the secret word.