Data Structures¶

Data structures, such as lists, can represent complex data. While lists are quite useful on their own, Python provides several other built-in data structures to make it easier to represent complex data. By the end of this lesson, students will be able to:

  • Apply list comprehensions to define basic list sequences.
  • Apply set operations to store and retrieve values in a set.
  • Apply dict operations to store and retrieve values in a dictionary.
  • Describe the difference between the various data structures' properties (list, set, dict, tuple).
In [71]:
import doctest

List comprehensions¶

Another one of the best features of Python is the list comprehension. A list comprehension provides a concise expression for building-up a list of values by looping over any type of sequence.

We already know how to create a list counting all the numbers between 0 and 10 (exclusive) by looping over a range.

In [4]:
nums = []
for i in range(10):
    nums.append(i ** 2)
nums
Out[4]:
[0, 1, 4, 9, 16, 25, 36, 49, 64, 81]

A list comprehension provides a shorter expression for achieving the same result.

In [3]:
[i for i in range(10)]
Out[3]:
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

What if we wanted to compute all these values squared? A list comprehension can help us with this as well.

In [5]:
[i ** 2 for i in range(10)]
Out[5]:
[0, 1, 4, 9, 16, 25, 36, 49, 64, 81]

Or, what if we wanted to only include values of i that are even?

In [6]:
[i ** 2 for i in range(10) if i % 2 == 0]
Out[6]:
[0, 4, 16, 36, 64]

Before running the next block of code, what do you think will output?

In [8]:
words
Out[8]:
['I', 'saw', 'a', 'dog', 'today']
In [7]:
words = "I saw a dog today".split()
[word[0] for word in words if len(word) >= 2]
Out[7]:
['s', 'd', 't']

Practice: Fun numbers¶

Fill in the blank with a list comprehension to complete the definition for fun_numbers.

In [10]:
def fun_numbers(start, stop):
    """
    Returns an increasing list of all fun numbers between start (inclusive) and stop (exclusive).
    A fun number is defined as a number that is either divisible by 2 or divisible by 5.

    >>> fun_numbers(2, 16, words)
    [2, 4, 5, 6, 8, 10, 12, 14, 15]
    """
    return [i for i in range(start, stop) if i % 2 == 0 or i % 5 == 0]
    # Making list comprehensions more complicated---trade-off with code quality


doctest.run_docstring_examples(fun_numbers, globals())
# "globals" is part of the "Python environment" model
In [ ]:
# This list comprehension (at this level of complexity) is still
# relatively self-documenting
[i for i in range(start, stop) if i % 2 == 0 or i % 5 == 0]

Tuples¶

Whereas lists represent mutable sequences of any elements, tuples (pronounced "two pull" or like "supple") represent immutable sequences of any elements. Just like strings, tuples are immutable, so the sequence of elements in a tuple cannot be modified after the tuple has been created.

While lists are defined with square brackets, tuples are defined by commas alone as in the expression 1, 2, 3. We often add parentheses around the structure for clarity. In fact, when representing a tuple, Python will use parentheses to indicate a tuple.

In [11]:
1, 2, 3
Out[11]:
(1, 2, 3)
In [12]:
1,2,3
Out[12]:
(1, 2, 3)
In [16]:
print(2, 3)

2 3
In [15]:
example = 2, 3
print(example)

(2, 3)
In [18]:
print((2, 3))

(2, 3)

We learned that there are many list functions, most of which modify the original list. Since tuples are immutable, there isn't an equivalent list of tuple functions. So why use tuples when we could just use lists instead?

Your choice of data structure communicates information to other programmers. If you know exactly how many elements should go in your data structure and those elements don't need to change, a tuple is right for the job. By choosing to use a tuple in this situation, we communicate to other programmers that the sequence of elements in this data structure cannot change! Everyone working on your project doesn't have to worry about passing a tuple to a function and that function somehow destroying the data.

Tuples provide a helpful way return more than one value from a function. For example, we can write a function that returns both the first letter and the second letter from a word.

In [19]:
def first_two_letters(word):
    return word[0], word[1]


# Tuple unpacking
a, b = first_two_letters("goodbye")
a
Out[19]:
'g'
In [20]:
b
Out[20]:
'o'
In [24]:
example = first_two_letters("goodbye")
example
Out[24]:
('g', 'o')
In [30]:
example[1] = "hello"

---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
Cell In[30], line 1
----> 1 example[1] = "hello"

TypeError: 'tuple' object does not support item assignment
In [45]:
first, second, third, *rest = tuple([0] * 10)
first, second, third
Out[45]:
(0, 0, 0)
In [44]:
rest
Out[44]:
[0, 0, 0, 0, 0, 0, 0]
In [46]:
example = 1,
example
Out[46]:
(1,)
In [47]:
1
Out[47]:
1

Sets¶

Whereas lists represent mutable sequences of any elements, sets represent mutable unordered collections of unique elements. Unlike lists, sets are not sequences so we cannot index into a set in the same way that we could for lists and tuples. Sets only represent unique elements, so attempts to add duplicate elements are ignored.

In [48]:
nums = set()
nums.add(1)
nums.add(2)
nums.add(3)
nums.add(2) # duplicate ignored
nums.add(-1)
nums
Out[48]:
{-1, 1, 2, 3}
In [49]:
nums[0]

---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
Cell In[49], line 1
----> 1 nums[0]

TypeError: 'set' object is not subscriptable

So what's the point of using a set over a list? Sets are often much faster than lists at determining whether a particular element is contained in the set. We can see this in action by comparing the time it takes to count the number of unique words in a large document. Using a list results in much slower code.

In [63]:
def count_unique(path):
    unique = set() # []
    with open(path) as f:
        for line in f.readlines():
            for token in line.split():
                # if token not in unique:
                unique.add(token) # used to be append
    return len(unique)


%time count_unique("moby-dick.txt")

CPU times: user 53.5 ms, sys: 2.96 ms, total: 56.4 ms
Wall time: 55.4 ms
Out[63]:
32553

By combining sets and list comprehensions, we can compose our programs in more "Pythonic" ways.

In [85]:
# Pythonic programs utilize the properties of your structures to great effect!
def count_unique(path):
    with open(path) as f:
        return len(set([token for line in f.readlines() for token in line.split()]))
        return len(set([token for token in f.read().split()]))
        return len(set(f.read().split()))


%time count_unique("moby-dick.txt")

CPU times: user 23.7 ms, sys: 7.19 ms, total: 30.9 ms
Wall time: 30.6 ms
Out[85]:
32553

Practice: Area codes¶

Fill in the blank to compose a "Pythonic" program that returns the number of unique area codes from the given list of phone numbers formatted as strings like "123-456-7890". The area code is defined as the first 3 digits in a phone number.

In [73]:
def area_codes(phone_numbers):
    """
    Returns the number of unique area codes in the given sequence.

    >>> area_codes([
    ...    '123-456-7890',
    ...    '206-123-4567',
    ...    '123-000-0000',
    ...    '425-999-9999'
    ... ])
    3
    """
    # Maybe split on "-" character and then grab the first group
    # pn.split("-") ==> ["123", "456", "7890"]
    return len(set([pn.split("-")[0] for pn in phone_numbers]))
    return len(set([pn[:3] for pn in phone_numbers]))


doctest.run_docstring_examples(area_codes, globals())

Dictionaries¶

A dictionary represents mutable unordered collections of key-value pairs, where the keys are immutable and unique. In other words, dictionaries are more flexible than lists. A list could be considered a dictionary where the "keys" are non-negative integers counting from 0 to the length minus 1.

Dictionaries are often helpful for counting occurrences. Whereas the above example counted the total number of unique words in a text file, a dictionary can help us count the number of occurrences of each unique word in that file.

In [ ]:
def count_tokens(path):
    counts = {}
    with open(path) as f:
        for token in f.read().split():
            if token not in counts:
                counts[token] = 1
            else:
                counts[token] += 1
    return counts


%time count_tokens("moby-dick.txt")

As an aside, there's also a more Pythonic way to write this program using collections.Counter, which is a specialized dictionary. The Counter type also sorts the results in order from greatest to least.

In [ ]:
def count_tokens(path):
    from collections import Counter
    with open(path) as f:
        return Counter(f.read().split())


%time count_tokens("moby-dick.txt")

Practice: Count lengths¶

Suppose we want to compute a histogram (counts) for the number of words that begin with each character in a given text file. Your coworker has written the following code and would like your help to finish the program. Explain your fix.

In [88]:
def count_lengths(words):
    counts = {}
    for word in words:
        first_letter = word[0]
        if first_letter not in counts:
            counts[first_letter] = 0
        counts[first_letter] += 1
    return counts


count_lengths(['cats', 'dogs', 'deers'])
Out[88]:
{'c': 1, 'd': 2}