Data Structures and references

0. Learning objectives

Build dictionaries to store data that can be looked up with a key,
Access values in a dictionary with a key,
Create and access values stored in tuples,
Modify mutable data structures, such as lists and dictionaries,
Identify when Python creates a new box for a variable, and when it stores a reference,

Long Room, Trinity College Library, Dublin. Wikipmedia Commons

After covering lists, you can probably start to see how large data will get stored in the computer, and how you might design a program to process a large chunk of data stored in a list. However, lists are not the only data structure available to us. But before we continue, what is a data structure?

Data structures are specialized ways of organizing and storing data in computers. They are typically considered compound (or composite) data types as they contain collections of different values and possibly types. We saw, for example, that you can have list of numbers, of strings, of mixed types, and even lists of lists! Definitely compound data type. Languages in general also have primitive data types. In Python, for example, these are integer, float, string, and Booleans.

Data structures allows us to work at different level of abstraction. You can think of them as a whole (a list), or you can work on individual items. Also, they are usually designed to address common recurring necessities. You can imagine that there might be multiple occasions, when trying to solve problems with algorithms, where you might want to have a collection of items stored in a list. Furthermore, they will typically come with specific techniques that go beyond a particular programming language. For example, if you are thinking of solving a problem that might require a list, independently of the language you will be using, you might find that you might need to be able to do one or more of the following to your list:

access by index (i.e., access randomly)
add items
remove items
sort
search
evaluate its length

and maybe you might want to use them in general computational patterns: map, filter, and reduce. So, independently of the specific language, you might find that these types of data structure are available to you and there might be functionality attached to them that allows you to do the above actions.

Let'ex explore another couple of data structures that Python has to offer.

1. Tuples

Some people pronounce this "tuh-ple" and some pronounce it as "too-ple". Honestly, I haven't heard anyone say one way is right and one way is wrong, so.... Tuples aren't that special, but they exist for a reason. You can create them using two parentheses (). So, for example, tp = (1, 2, 3) will create a tuple. You can also create a tuple using the tuple(iterable) function and pass an iterable. The resulting tuple will have the items in or generated by the iterable. For example tp = tuple(range(5)) will create a tuple with integers from 0 to 4 in it. This brings the interesting point that you can go back and forth between tuples and lists using the tuple() and list() functions. Try to see what happens in Brython if you type the statement above, and then you follow it by ls = list(tp). You can also go the other way around. Try to append something to ls and then run tp = tuple(ls). Cool, right?

Tuples are basically the immutable version of lists and, because of that, they come with much less attached functionality (less methods when you look at dir(tuple)). They are still an ordered sequence of items so you can do things like indexing and slicing. len will still give you the number of items in the tuple but, whereas lists are mutable, tuples are immutable. Just like for strings, the immutability is important: if you create a tuple tp = (1, 2, 3), you will not be able to say tp[1] = 4. Try to see what happens if you do.

So what are tuples useful for anyway? They're useful if you want to return multiple values from a function, and also to swap values.

So? What is really the point of tuples? They are typically used to pass around small bundle of associated information. Pieces of data that make sense to keep together. There is a strong culture in Python to use list for homogeneous items (all the same type) and tuples for heterogenous items (different types) but there is no such restriction in the language.

2. Dictionaries

If we want to retrieve a specific value in a list or a tuple, we need to know the index of that value in the list. But what if we don't have indices? For example, consider retrieving Boo's door in the big warehouse of doors in Monster's Inc. Maybe we store all the doors in a list of doors in which each door has a label corresponding to who the door belongs to. Now, if we want to retrieve Boo's door without knowing the index of her door, then we have to loop through every door in the list, and check if each door label matches "Boo". As you can see, if there are many doors, this could be really inefficient, especially if Boo's door is stored at the end of the list.

Because this is a pretty recurring problem in computing, a new data structure was developed to address this type of problem: a dictionary. In Dictionaries each value is associated with a key and together they make an item in the dictionary. This is in different from to lists and tuples where each item is associated with an index (a specific location - remember, lists are ordered collections). Continuing the example above, we can directly associate someone's door (the value) with their name (the key)!

Keys can be anything immutable (so, for example, you can use strings, numbers, tuples, but not lists as keys). The specific problem you are solving will lend to more natural choices for your keys. In our Monster's Inc. example, we want to find doors by someone's name (a string), so it makes sense to use strings as the keys. (We will see examples where it makes more sense to use integers). We can then use these keys to retrieve a value (a door). This is the central concept when using dictionaries: key-value pairs are stored at the same time and they are associated with each other. Let's now see how to build dictionaries, add key-value pairs and retrieve a value from a dictionary using a key.

2.1. Operations on dictionaries

The most frequent operations you will do with dictionaries are: create a dictionary, access the value at a key, and add a key-value pair, and iterate through key-value pairs:

Creating a dictionary: can be done by enclosing key-value pairs within curly-braces ({}). An empty dictionary (to which you can add key-value pairs later) is created using curly braces, e.g. d = {} creates an empty dictionary and assigns it to the variable d. You could also create an empty dictionary with d = dict(). To create a dictionary with specific key-value pairs, Python expects these key-value pairs (items) to be delimited by a comma (again, these pairs should be within {}). The association between the key and the value is specified by a colon. For example, d = { 'boo': 'pink' , 'mike': 'green' } creates a dictionary d with 2 key-value pairs (items). The first item has the value 'pink' (a string) which is associated with the key 'boo' (also a string). The second item has the value 'green' which is associated with the key 'mike'. This dictionary could be used to look up the color of someone's door in the Monsters Inc. warehouse (assuming Mike has a green door and Boo has a pink door).
Accessing the value at a particular key: just like with lists, we can do this with square brackets []. With dictionaries, however, inside the square brackets we have to use the key we are looking for. Therefore, we can retrieve the value associated with a particular key using d[key]. For example, to retrieve the color of Boo's door (which has the key 'boo'), we would use boo_door_color = d['boo'] (which in our example should be 'pink').
Adding a key-value pair: given a dictionary d, we can add a new key-value pair using square brackets [] on d and assigning the new value stored at the key. Specifically, you would type d[key] = value to insert a key into the dictionary with a particular value. If the key doesn't yet exist in the dictionary, Python will create one for it, otherwise, the value will be re-assigned. This is quite different from ordered sequences where, if we try to add something using an index that is not within the length of the sequence, we get an indexing error telling us that we are out of range. For example, if Sully has a blue door, we could add this to our dictionary with d['sully'] = 'blue'. You could also re-assign Mike's door using d['mike'] = 'teal'. It is important to notice that we can only have unique keys. In other words, keys can only appear once in your dictionary (which make sense, otherwise how would Python know what to give you when you look for d[key]?) On the other hand, you can have as many identical values as you want.
Iterate through key-value pairs: use the in keyword just like we did with lists and strings. If you just use the name of the dictionary, each "iterable" will be a key. This is important so we'll say it again: "each iterable will be a key." That is, if we write forxind:, then we will iterate through every key in the dictionary d. Upon every iteration, the key will be assigned to the variable x. This means that if you want to retrieve the value for that key, you would need to type d[x]. If you want to iterate on something different, you can use the d.values() to retrieve the values or d.items(). The latter will give you one tuple for each item in the dictionary containing the corresponding (key, value). Try them in Brython!

All of these operations are summarized in the example below. You'll notice that we can also retrieve the number of key-value pairs stored in a dictionary d using the len function (just like we did with lists and strings).

You'll notice that there is yet another way to create a dictionary: using zip. To use zip you need to pass two lists (one list for the keys, and another list for the values). zip will take one element from each of the lists you passed and create a tuple and pass it to the dict() function that will use them to create an item in your dictionary. Pretty sweet if you have a piece of code that creates the two lists and you want to combine them in a dictionary.

1.2. Dictionaries are mutable

Remember how we were able to assign a value at a particular index in a list? Something like x[2] = 'banana' is valid, assuming x is a list with at least 3 items. Also, remember that we can assign a value for a particular key in a dictionary? So something like d['banana'] = 0.25 is valid, assuming d is a dictionary. By contrast, remember that if s = 'piper' (a string), then we can retrieve the value at index 2 with s[2], but we cannot assign a different character to index 2 in the string: s[2] = 'x' will make Python angry. Try it out (maybe in the interpreter below).

The reason for this behavior is because, as we have seen, some data structures are mutable (their items can be assigned new values) whereas others are immutable (their items cannot be assigned new values). Based on this definition, think back to all the data structures we have seen so far: numbers (ints, floats), Boolean, strings, lists and dictionaries. Which ones are mutable? Which are immutable?

solution

Lists and dictionaries are mutable. Numbers, Booleans, and strings are immutable.

Example O: Price of fruit

Say you're programming a cash register and you want to be able to pull up the price of a particular item given the string representing that item. This is where a dictionary will be useful! In the example below, we first create a dictionary in which the keys are the food names, and the values are the price for that food. Notice that some foods might have the same price. Given a list of grocery items (maybe coming off the conveyor belt), try to complete the get_grocery_cost(cart) function to determine the cost of all the items in the cart. What should you do if an item is not in the store!

Note that in a conventional cash register, you would probably associate an integer (as the key) with a particular price (a float), since foods are usually labelled with PLUs (integers). This could also be achieved with dictionaries! Remember, the keys could be anything that is immutable, and the values could be anything too.

Example 1: Character frequency

Given a word (a string), how frequently does each character show up? Let's write a function to find out!

To tackle this problem, you might want to notice that, because dictionaries are mutable, you can update individual items. In particular, if d = {'a': 0, 'b': 0}, it is a totally legit operation to do: d['a'] += 1. This because the value associated with the key 'a' is numeric.

Hint: The solution to this problem (other solutions are possible too), is to create a dictionary that keeps track of the "count" of every character. In other words, we create a dictionary with keys for every letter we find, initialize the counter (the value for the letter key) to 1 the first time we encounter this character, and then increase this counter whenever we find the letter again.

Example 2: Fibonacci with memoization

One more example! Remember when we looked at Fibonacci numbers? The equation we had to compute the $n$-th Fibonacci number is $F(n) = F(n-1) + F(n-2)$ with $F(0) = 0$ and $F(1) = 1$. The problem we initially had was that directly applying this formula recursively meant that we recomputed a lot of Fibonacci numbers. But what if we could remember them the first time we compute them? This is a technique known as memoization. In our Fibonacci example, we will store known Fibonacci numbers in a dictionary, in which the keys are integers (corresponding to $n$) and the values are the $F(n)$. This makes for a solution that is both readable and fast!

3. References and values

Do you remember that we've been saying that variables are like little boxes where we store values? This is a really good model, but it isn't perfect (it was good enough when we were starting out). The reason it isn't perfect is because, under the hood, Python actually stores both references and values. We know what values are (e.g., 5) but what about references? The reference is a unique identifier that Python assigns to variables and values. If you like, you can think about this as the "address" of this variable in your computer's memory. Python has a useful function for determining the unique identifier assigned to a variable: it's called the id() and gives you the reference of the argument. So if you say x = 2 and then print(id(x)), you'll see some integer that is the "id" of x.

Now comes the confusing part (which put a kink in our model). When we write y = x, Python doesn't create a new box in memory and stores another value 2 in there and then gives the location as reference to y. What it does is to actually copy the reference it had for 2, the same one it used for x, and assigns it to y. This means both x and y "point" to the same value. Try it out: type y = x and then print(id(y)): you should see the same "id" for x and y! What is even wilder is that, if you write z = 1 + 1, Python will evaluate the result 2, notice that it already has that value and give its reference to z as well!

The reason for this is that, in many cases, we are not dealing with simple values, we are dealing with very large data structures and, it would not make sense (would not be efficient) to copy the same thing over and over again. So what Python does is to pass around the reference.

To complicate things, mutability comes into play here. If we re-assign the value for y (e.g., y = 7), then Python creates a new box for y. Why? Because 7 (and also 2) are numbers, which are immutable! As soon as you type y = 7, Python says "oh, numbers are immutable, so I need a new box for 7"!

Now, if you use mutable types, like lists and dictionaries, and you assign one variable to another as in x = [1, 2, 3] and y = x, Python gives the same reference to the same list to both variables (this is called aliasing). Modifying one variable will modify the other - because they "point" to the same thing in memory! For example:

The same is true if you pass a mutable data type into a function. You can actually modify the contents of the mutable type inside the function and you will see the changes outside the function too. Check the following:

To prevent this from happening, what you can do is to create a copy either by using the slice operator y = x[:] or by using the .copy() method that comes with many mutable types: y = x.copy(). Check the difference in this example:

You can always use the is operator to check if two variables are pointing to the same "thing". If they do, the result is going to be True (e.g., x is y will give True if they both have the same id.

This is a challenging concept to grasp, so we encourage you to play with the following code to help you better understand what happens. There is no right or wrong way of doing things. You just have to make sure that your code does what you expect it to do!