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 [1]:
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 [2]:
nums = []
for i in range(10):
    nums.append(i)
nums
Out[2]:
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

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

Its basic structure is: [item_to_select for loop if condition [more nested list comp] ]

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 [4]:
[i ** 2 for i in range(10)]
Out[4]:
[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 [5]:
[i ** 2 for i in range(10) if i % 2 == 0]
Out[5]:
[0, 4, 16, 36, 64]

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

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

Now let's try to rewrite the count_odd function from the file processing lesson with list comprehension:

def count_odd(path):
    """
    For the file path, prints out each line number followed by the number of odd-length tokens.

    >>> count_odd("poem.txt")
    1 2
    2 1
    3 0
    4 3
    """
    with open(path) as f:
        lines = f.readlines()
        line_num = 1
        for line in lines:
            tokens = line.split()
            odd_count = 0
            for token in tokens:
                if len(token) % 2 == 1:
                    odd_count += 1
            print(line_num, odd_count)
            line_num += 1

doctest.run_docstring_examples(count_odd, globals())
In [7]:
def count_odd(path):
    """
    For the file path, prints out each line number followed by the number of odd-length tokens.

    >>> count_odd("poem.txt")
    1 2
    2 1
    3 0
    4 3
    """
    with open(path) as f:
        lines = f.readlines()
        line_num = 1
        for line in lines:
            tokens = line.split()
            odd_count = len([token for token in tokens if len(token) % 2 == 1])
            print(line_num, odd_count)
            line_num += 1

doctest.run_docstring_examples(count_odd, globals())

Practice: Fun numbers¶

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

In [ ]:
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)
    [2, 4, 5, 6, 8, 10, 12, 14, 15]
    """
    return ...

doctest.run_docstring_examples(fun_numbers, globals())
Answer (hint: write it as a usual for loop first and then convert it to list comprehension)

[num for num in range(start, stop) if num % 2 == 0 or num % 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 [8]:
1, 2, 3
Out[8]:
(1, 2, 3)
In [9]:
a = tuple([1, 2, 3])
a
Out[9]:
(1, 2, 3)
In [10]:
a[2]
Out[10]:
3
In [11]:
a[2] = 0 # tuples are immutable!

---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
Cell In[11], line 1
----> 1 a[2] = 0 # tuples are immutable!

TypeError: 'tuple' object does not support item assignment
In [12]:
len(a)
Out[12]:
3
In [13]:
for value in a:
    print(value)

1
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 [14]:
def first_two_letters(word):
    return word[0], word[1]

a, b = first_two_letters('goodbye')
a
Out[14]:
'g'
In [16]:
returnvalue = first_two_letters('goodbye')
returnvalue[0]
Out[16]:
'g'

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 [17]:
nums = set()
nums.add(1)
nums.add(2)
nums.add(3)
nums.add(2) # duplicate ignored
nums.add(-1)
nums
Out[17]:
{-1, 1, 2, 3}

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 [18]:
def count_unique(path):
    unique = []
    with open(path) as f:
        for line in f.readlines():
            for token in line.split():
                if token not in unique:
                    unique.append(token)
    return len(unique)


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

CPU times: user 7.53 s, sys: 13.3 ms, total: 7.54 s
Wall time: 7.54 s
Out[18]:
32553

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

In [19]:
def count_unique(path):
    with open(path) as f:
        return len(set([token for line in f.readlines() for token in line.split()]))

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

CPU times: user 29.7 ms, sys: 13.1 ms, total: 42.8 ms
Wall time: 41.1 ms
Out[19]:
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 [ ]:
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
    """
    return len(set(...))

doctest.run_docstring_examples(area_codes, globals())
Answer (hint: recall split() or string slicing)

[number[:3] for number in phone_numbers] or [number.split('-')[0] for number in phone_numbers]

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.

In [20]:
empty_dictionary = dict()
empty_dictionary
Out[20]:
{}
In [21]:
lecture_schedule = dict()
lecture_schedule["06/17"] = "welcome-and-control-structures"
lecture_schedule["06/19"] = "holiday: Juneteenth"
lecture_schedule["06/21"] = "files-and-data-structures"
lecture_schedule
Out[21]:
{'06/17': 'welcome-and-control-structures',
 '06/19': 'holiday: Juneteenth',
 '06/21': 'files-and-data-structures'}
In [22]:
lecture_schedule.keys()
Out[22]:
dict_keys(['06/17', '06/19', '06/21'])
In [23]:
for i in range(len(lecture_schedule.keys())):
    print(lecture_schedule.keys()[i])

---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
Cell In[23], line 2
      1 for i in range(len(lecture_schedule.keys())):
----> 2     print(lecture_schedule.keys()[i])

TypeError: 'dict_keys' object is not subscriptable
In [24]:
for k in lecture_schedule.keys():
    print(k)

06/17
06/19
06/21
In [25]:
lecture_schedule.values()
Out[25]:
dict_values(['welcome-and-control-structures', 'holiday: Juneteenth', 'files-and-data-structures'])
In [26]:
lecture_schedule.items()
Out[26]:
dict_items([('06/17', 'welcome-and-control-structures'), ('06/19', 'holiday: Juneteenth'), ('06/21', 'files-and-data-structures')])
In [27]:
for k, v in lecture_schedule.items():
    print(k, v)

06/17 welcome-and-control-structures
06/19 holiday: Juneteenth
06/21 files-and-data-structures

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 words by first letters¶

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 [ ]:
def count_by_first_letter(words):
    counts = {}
    for word in words:
        first_letter = word[0]
        counts[first_letter] += 1
    return counts

count_by_first_letter(['cats', 'dogs', 'deers'])
Answer (hint: reference `count_tokens`)

counts[first_letter] += 1 may cause errors because accessing a key that does not exist in a dictionary will cause a key error. We should first check whether the key exists. If not, we initialize the value. If yes, we can add 1 to it.

So, the fix for the line counts[first_letter] += 1 will be

if first_letter in counts:
    counts[first_letter] += 1
else:
    counts[first_letter] = 1

Review of today's lecture¶

In [ ]:
with open(...) as f:
    f.read()
    f.readlines()
    f.readline()
In [ ]:
[item for .. in ... if .. ]
In [ ]:
tuple() [] len
In [ ]:
set()
In [ ]:
dict() .keys() .values() .items()