Sets and Dicts

You write a set as a comma-separated list of elements inside braces { }—for example, you'd type the first three natural numbers as {1, 2, 3}. You can also use Python's built-in set() function. This is usually called with a single sequence argument, and creates a set that contains all the sequence's elements.

Python includes two separate data types for handling sets. As with lists and tuples, you build regular sets, then you can add or remove elements. You can also build frozen sets, which stay the same once you have created them and raise an exception at any attempt to change them. A set is an unordered collection of items with no duplicate elements; lists are ordered and sets are not. Set objects also support various operations like union, intersection, and difference. If any of these terms are new to you, don't panic! We'll go over all of it in detail here and in later lessons.

Okay, now it's time to take a closer look at set operations! Start an interactive terminal session and enter the following commands:

>>> {1, 2, 3, 1, 2, 3, 1, 2, 3, 1}
{1, 2, 3}
>>> vowels1 = {"a", "e", "i", "o", "u"}
>>> vowels2 = set("aieou")
>>> vowels1 == vowels2
True
>>> languages = {"perl", "python", "c++", "ruby"}
>>> languages.add("php")
>>> languages
{'php', 'python', 'ruby', 'c++', 'perl'}
>>> "perl" in languages
True
>>> "java" in languages
False
>>> {'python', 'ruby'} < languages
True
>>> set("the quick brown fox") & vowels1
{'i', 'o', 'e', 'u'}
>>> vowels1 - set("the quick brown fox")
{'a'}
>>> set("the quick brown fox") - vowels1
{'r', 'f', 'x', 't', 'h', 'q', 'w', 'n', ' ', 'b', 'k', 'c'}
>>>

The examples above used integers, characters, and strings, but most Python objects can be elements of a set. You can compute the intersection of two sets using the & operator, and the difference between two sets with the - operator. There are a number of other operations you can perform on sets as well. Many, but not all, of the operations can be performed using either operators or a method call on one of the sets.

Assume that s and t are sets in the following table:

Let's use a set to keep track of how many different words there are in a given piece of text. Create a new file as shown:

"""Count the number of different words in a text."""

text = """\
Baa, baa, black sheep,
Have you any wool?
Yes sir, yes sir,
Three bags full;
One for the master,
And one for the dame,
And one for the little boy
Who lives down the lane."""

for punc in ",?;.":
    text = text.replace(punc, "")
print(text)
words = set(text.lower().split())
print("There are", len(words), "distinct words in the text.")

Save it as word_counter.py and run it.

Baa baa black sheep
Have you any wool
Yes sir yes sir
Three bags full
One for the master
And one for the dame
And one for the little boy
Who lives down the lane
There are 24 distinct words in the text.

This is a classic problem we can run into when working with text in our programs. Python lets you solve it in a unique way. First, it uses a for loop to remove all the punctuation (punc) characters (,?;.) from the string, replacing each one with an empty string (""). Next, it prints the text so you can confirm that the punctuation has been removed. Finally, it converts the text to lower-case, splits the text at each run of white space, and creates a set from the resulting list.

Python removes the punctuation to ensure that only words are present in the text. "Baa" is not the same as "Baa," (with a comma), so the punctuation must be removed. The text is converted to lower case before splitting so that, for example, "One" and "one" will not be treated as unique words. A set cannot contain duplicate entries. The number of elements in the set (given by the len() function) is comprised of the number of different words in the text.

To see another application of sets, let's write a program that compares two inputs and prints out the words they have in common and various other pieces of information. Type the code below as shown:

"""Find matching words in two input lines."""

words1 = set(input("Sentence 1: ").lower().split())
words2 = set(input("Sentence 2: ").lower().split())
print("Words in both strings", words1 & words2)
print("Unique to sentence 1:", words1 - words2)
print("Unique to sentence 2:", words2 - words1)

Save it as word_matcher.py and run it, and then enter two different sentences with some words in common, as shown:

Sentence 1: Four score and seven years ago
Sentence 2: Four and twenty blackbirds were baked in a pie
Words in both strings {'and', 'four'}
Unique to sentence 1: {'seven', 'score', 'years', 'ago'}
Unique to sentence 2: {'pie', 'were', 'a', 'twenty', 'baked', 'blackbirds', 'in'}

The program prints the sets of words, telling you which are common to both sentences and which are unique to each sentence. Because the sets are not sorted, the program prints them in unpredictable order. To overcome this issue, modify the program to make use of Python's sorted() function. Edit your code as shown in blue:

"""Find matching words in two input lines."""

words1 = set(input("Sentence 1: ").lower().split())
words2 = set(input("Sentence 2: ").lower().split())
print("Words in both strings", sorted(words1 & words2))
print("Unique to sentence 1:", sorted(words1 - words2))
print("Unique to sentence 2:", sorted(words2 - words1))

Save and run it, and enter the same two sentences. The output of the first version of this program printed sets as its results, but this modified version prints lists. When applied to a set, the sorted() function sorts the elements of the set into a list. This displays our results in a predictable (alphabetical) order.

Sentence 1: Four score and seven years ago
Sentence 2: Four and twenty blackbirds were baked in a pie
Words in both strings ['and', 'four']
Unique to sentence 1: ['ago', 'score', 'seven', 'years']
Unique to sentence 2: ['a', 'baked', 'blackbirds', 'in', 'pie', 'twenty', 'were']

The dict is a useful structure for storing values against arbitrary keys. Let's take a look. Start an interactive interpreter session and type the commands shown below:

>>> d = {'Steve': 'Python', 'Peter': 'Perl', 'Rob': 'Ruby'}
>>> d['Rob']
'Ruby'
>>> d['Peter'] = "C#"
>>> d
{'Steve': 'Python', 'Peter': 'C#', 'Rob': 'Ruby'}
>>> d['Peter']
'C#'
>>> del d['Peter']
>>> d
{'Steve': 'Python', 'Rob': 'Ruby'}
>>> d['Guido'] = 'Python'
>>> d
{'Steve': 'Python', 'Rob': 'Ruby', 'Guido': 'Python'}
>>> d.keys()
dict_keys(['Steve', 'Rob', 'Guido'])
>>> for k in d.keys():
...   print(k)
...
Steve
Rob
Guido
>>> for k in d.items():
...   print(k)
...
('Steve', 'Python')
('Rob', 'Ruby')
('Guido', 'Python')
>>> d[(1, 2)] = "Tuple"
>>> d[1] = "Integer"
>>> d
{'Steve': 'Python', 'Rob': 'Ruby', 'Guido': 'Python', (1, 2): 'Tuple', 1: 'Integer'}
>>> d[1]
'Integer'
>>> d[1.0] = "Hello there"
>>> d[1+0j]
'Hello there'

Here you can see some of the most important aspects of dict behavior. Dict literals use braces { } like sets do, but each element is represented by a key, followed by a colon and the value associated with that key. In the example above, you can see strings, numbers and tuples being used as keys. There are some types of object you can't use as keys, but you need not worry about that just yet. We've got enough to wrap our brains around for now!

In addition to creating dicts with a literal representation, you can also add new key-value pairs, and replace the value associated with an existing key, using assignment statements. If you assign to an existing key in the dict, then the assigned value replaces the previously associated value. If no value is associated with the key (in other words, if the key does not currently exist in the dict), then the key is added and the assigned value is associated with the key.

Numeric keys receive slightly different treatment. You might expect that d[1], d[1.0], and d[1+0j] would refer to different values in the dict, but those three keys are all numerically equal, and so assigning to d[1.0] overwrites the value assigned to d[1], and the same value can be retrieved by referencing d[1+0j].

You can also see in our example that dicts have a keys() method that returns the keys of the dict. This is known in Python as an iterator. We'll look at iterators in some detail in a later course, but for the moment all you need to know is that you can iterate over it, and each time around the loop, you get another key from the dict. The same is true of the dict's items() method, only this iterator yields key-value pairs rather than the keys from the dict.

The dict is a flexible object type. You can perform the following operations on a dict d:

Remember, the more you experiment the more you learn. Play around with a dict or two in an interactive console until you are comfortable with the way they work.

Now that you know how dicts work, let's apply the concept to a classic text processing problem: counting the occurrences of words within a text. In a previous exercise, we put the words from a piece of text into a set, but there was no way to associate a count with each word—all we can do with a set is detect whether an item is present.

Because the dict is able to associate a value with the key, we can use each word as a key in the dict and have the associated value be the number of times the word appears in the text. Open your word_counter.py program and save it as a new file named word_frequency.py. Then, edit it as shown:

"""Count the frequency of each word in a text."""

text = """\
Baa, baa, black sheep,
Have you any wool?
Yes sir, yes sir,
Three bags full;
One for the master,
And one for the dame,
And one for the little boy
Who lives down the lane."""

for punc in ",?;.":
    text = text.replace(punc, "")

freq = {}
for word in text.lower().split():
    if word in freq:
        freq[word] += 1
    else:
        freq[word] = 1

for word in sorted(freq.keys()):
    print(word, freq[word])

Save and run it. You'll see output showing the number of times each word appears in the text. Word splitting works in the same way as before, but now, each time a word is examined, the program checks to find out whether the word has appeared before. If it has not, then a new entry is made in the dict with a value of one. If it has (if it is already found in the freq dict), the current count is incremented.

and 2
any 1
baa 2
bags 1
black 1
boy 1
dame 1
down 1
for 3
full 1
have 1
lane 1
little 1
lives 1
master 1
one 3
sheep 1
sir 2
the 4
three 1
who 1
wool 1
yes 2
you 1

A slight modification to the program allows us to dispense with the if statement. Edit word_frequency.py as shown:

"""Count the frequency of each word in a text."""

text = """\
Baa, baa, black sheep,
Have you any wool?
Yes sir, yes sir,
Three bags full;
One for the master,
And one for the dame,
And one for the little boy
Who lives down the lane."""

for punc in ",?;.":
    text = text.replace(punc, "")

freq = {}
for word in text.lower().split():
    if word in freq:
        freq[word] += 1
    else:
        freq[word] = 1
    freq[word] = freq.get(word, 0)+1

for word in sorted(freq.keys()):
    print(word, freq[word])

Save and run it. You should see the same results as before. This version of the program uses the same statement to update the count, even if the word has been seen before. It uses the get() method with a default value of zero to retrieve the existing count, so if the word hasn't been seen before, the assignment inserts a value of one against the new key.

In the final example of this lesson, we'll do a slightly more complex counting task. For each word in the input, we will keep a count of the number of times it was followed by each of the other words that immediately follow it in the text. This involves keeping a dict for each word. The keys of this second dict will be the words that immediately follow the original word. The values will be the number of times that particular word followed the original word.

With your word_frequency.py program open, save it as pair_frequency.py. Edit the new program as shown:

"""Count the frequency of each word in a text."""

text = """\
Baa, baa, black sheep,
Have you any wool?
Yes sir, yes sir,
Three bags full;
One for the master,
And one for the dame,
And one for the little boy
Who lives down the lane."""

for punc in ",?;.":
    text = text.replace(punc, "")

freq = {}
for word in text.lower().split():
    freq[word] = freq.get(word, 0)+1
words = {}
textwords = text.lower().split()
firstword = textwords[0]
for nextword in textwords[1:]:
    if firstword not in words:
        words[firstword] = {}
    words[firstword][nextword] = words[firstword].get(nextword, 0)+1
    firstword = nextword

for word in sorted(freq.keys()):
    print(word, freq[word])
for word in sorted(words.keys()):
    d = words[word]
    for word2 in sorted(d.keys()):
        print(word, ":", word2, d[word2])

Save and run it.

and : one 2
any : wool 1
baa : baa 1
baa : black 1
bags : full 1
black : sheep 1
boy : who 1
dame : and 1
down : the 1
for : the 3
full : one 1
have : you 1
little : boy 1
lives : down 1
master : and 1
one : for 3
sheep : have 1
sir : three 1
sir : yes 1
the : dame 1
the : lane 1
the : little 1
the : master 1
three : bags 1
who : lives 1
wool : yes 1
yes : sir 2
you : any 1

Since we have to process words in pairs, we set firstword to be the first word in the text. The loop then loops over the rest of the text (textwords[1:]), assigning the word to nextword. At the end of each pass through the loop, nextword is assigned to firstword, so that at the start of each iteration we have a consecutive pair of words in firstword and nextword.

The program makes sure that there is an entry for the first word in the words dict: each entry starts out as an empty dict, which will be used to store the number of occurrences of individual following words. Then it uses the same technique that the second version of word_frequency.py did to update the count of the following word. The printing of the output has become a little more complex, because each word requires you to print out each following word. So in the output phase, we have nested loops: one loop inside another.

You've just added sets and dicts to your programming tool kit—no easy feat! Excellent! In the next lesson, we'll focus on output, and ways to control the format of the output produced by your programs.

I like what I'm seeing so far! Keep it up and see you in the next lesson...