Chapter 6. Python Data Structures
In our examples so far, we've already seen many of the built-in Python data structures in action. You've probably also covered many of them in introductory books or tutorials. In this chapter, we'll be discussing the object-oriented features of these data structures, when they should be used instead of a regular class, and when they should not be used. In particular, we'll be covering:
- Tuples and named tuples
- Dictionaries
- Lists and sets
- How and why to extend built-in objects
- Three types of queues
Empty objects
Let's start with the most basic Python built-in, one that we've seen many times already, the one that we've extended in every class we have created: the object. Technically, we can instantiate an object without writing a subclass:
>>> o = object() >>> o.x = 5 Traceback (most recent call last): File "<stdin>", line 1, in <module> AttributeError: 'object' object has no attribute 'x'
Unfortunately, as you can see, it's not possible to set any attributes on an object that was instantiated directly. This isn't because the Python developers wanted to force us to write our own classes, or anything so sinister. They did this to save memory; a lot of memory. When Python allows an object to have arbitrary attributes, it takes a certain amount of system memory to keep track of what attributes each object has, for storing both the attribute name and its value. Even if no attributes are stored, memory is allocated for potential new attributes. Given the dozens, hundreds, or thousands of objects (every class extends object) in a typical Python program; this small amount of memory would quickly become a large amount of memory. So, Python disables arbitrary properties on object, and several other built-ins, by default.
Note
It is possible to restrict arbitrary properties on our own classes using slots. Slots are beyond the scope of this book, but you now have a search term if you are looking for more information. In normal use, there isn't much benefit to using slots, but if you're writing an object that will be duplicated thousands of times throughout the system, they can help save memory, just as they do for object.
It is, however, trivial to create an empty object class of our own; we saw it in our earliest example:
class MyObject:
passAnd, as we've already seen, it's possible to set attributes on such classes:
>>> m = MyObject() >>> m.x = "hello" >>> m.x 'hello'
If we wanted to group properties together, we could store them in an empty object like this. But we are usually better off using other built-ins designed for storing data. It has been stressed throughout this book that classes and objects should only be used when you want to specify both data and behaviors. The main reason to write an empty class is to quickly block something out, knowing we'll come back later to add behavior. It is much easier to adapt behaviors to a class than it is to replace a data structure with an object and change all references to it. Therefore, it is important to decide from the outset if the data is just data, or if it is an object in disguise. Once that design decision is made, the rest of the design naturally falls into place.
Tuples and named tuples
Tuples are objects that can store a specific number of other objects in order. They are immutable, so we can't add, remove, or replace objects on the fly. This may seem like a massive restriction, but the truth is, if you need to modify a tuple, you're using the wrong data type (usually a list would be more suitable). The primary benefit of tuples' immutability is that we can use them as keys in dictionaries, and in other locations where an object requires a hash value.
Tuples are used to store data; behavior cannot be stored in a tuple. If we require behavior to manipulate a tuple, we have to pass the tuple into a function (or method on another object) that performs the action.
Tuples should generally store values that are somehow different from each other. For example, we would not put three stock symbols in a tuple, but we might create a tuple of stock symbol, current price, high, and low for the day. The primary purpose of a tuple is to aggregate different pieces of data together into one container. Thus, a tuple can be the easiest tool to replace the "object with no data" idiom.
We can create a tuple by separating the values with a comma. Usually, tuples are wrapped in parentheses to make them easy to read and to separate them from other parts of an expression, but this is not always mandatory. The following two assignments are identical (they record a stock, the current price, the high, and the low for a rather profitable company):
>>> stock = "FB", 75.00, 75.03, 74.90 >>> stock2 = ("FB", 75.00, 75.03, 74.90)
If we're grouping a tuple inside of some other object, such as a function call, list comprehension, or generator, the parentheses are required. Otherwise, it would be impossible for the interpreter to know whether it is a tuple or the next function parameter. For example, the following function accepts a tuple and a date, and returns a tuple of the date and the middle value between the stock's high and low value:
import datetime
def middle(stock, date):
symbol, current, high, low = stock
return (((high + low) / 2), date)
mid_value, date = middle(("FB", 75.00, 75.03, 74.90),
datetime.date(2014, 10, 31))
The tuple is created directly inside the function call by separating the values with commas and enclosing the entire tuple in parenthesis. This tuple is then followed by a comma to separate it from the second argument.
This example also illustrates tuple unpacking. The first line inside the function unpacks the stock parameter into four different variables. The tuple has to be exactly the same length as the number of variables, or it will raise an exception. We can also see an example of tuple unpacking on the last line, where the tuple returned inside the function is unpacked into two values, mid_value and date. Granted, this is a strange thing to do, since we supplied the date to the function in the first place, but it gave us a chance to see unpacking at work.
Unpacking is a very useful feature in Python. We can group variables together to make storing and passing them around simpler, but the moment we need to access all of them, we can unpack them into separate variables. Of course, sometimes we only need access to one of the variables in the tuple. We can use the same syntax that we use for other sequence types (lists and strings, for example) to access an individual value:
>>> stock = "FB", 75.00, 75.03, 74.90 >>> high = stock[2] >>> high 75.03
We can even use slice notation to extract larger pieces of tuples:
>>> stock[1:3] (75.00, 75.03)
These examples, while illustrating how flexible tuples can be, also demonstrate one of their major disadvantages: readability. How does someone reading this code know what is in the second position of a specific tuple? They can guess, from the name of the variable we assigned it to, that it is high of some sort, but if we had just accessed the tuple value in a calculation without assigning it, there would be no such indication. They would have to paw through the code to find where the tuple was declared before they could discover what it does.
Accessing tuple members directly is fine in some circumstances, but don't make a habit of it. Such so-called "magic numbers" (numbers that seem to come out of thin air with no apparent meaning within the code) are the source of many coding errors and lead to hours of frustrated debugging. Try to use tuples only when you know that all the values are going to be useful at once and it's normally going to be unpacked when it is accessed. If you have to access a member directly or using a slice and the purpose of that value is not immediately obvious, at least include a comment explaining where it came from.
Named tuples
So, what do we do when we want to group values together, but know we're frequently going to need to access them individually? Well, we could use an empty object, as discussed in the previous section (but that is rarely useful unless we anticipate adding behavior later), or we could use a dictionary (most useful if we don't know exactly how many or which specific data will be stored), as we'll cover in the next section.
If, however, we do not need to add behavior to the object, and we know in advance what attributes we need to store, we can use a named tuple. Named tuples are tuples with attitude. They are a great way to group read-only data together.
Constructing a named tuple takes a bit more work than a normal tuple. First, we have to import namedtuple, as it is not in the namespace by default. Then, we describe the named tuple by giving it a name and outlining its attributes. This returns a class-like object that we can instantiate with the required values as many times as we want:
from collections import namedtuple
Stock = namedtuple("Stock", "symbol current high low")
stock = Stock("FB", 75.00, high=75.03, low=74.90)The namedtuple constructor accepts two arguments. The first is an identifier for the named tuple. The second is a string of space-separated attributes that the named tuple can have. The first attribute should be listed, followed by a space (or comma if you prefer), then the second attribute, then another space, and so on. The result is an object that can be called just like a normal class to instantiate other objects. The constructor must have exactly the right number of arguments that can be passed in as arguments or keyword arguments. As with normal objects, we can create as many instances of this "class" as we like, with different values for each.
The resulting namedtuple can then be packed, unpacked, and otherwise treated like a normal tuple, but we can also access individual attributes on it as if it were an object:
>>> stock.high 75.03 >>> symbol, current, high, low = stock >>> current 75.00
Tip
Remember that creating named tuples is a two-step process. First, use collections.namedtuple to create a class, and then construct instances of that class.
Named tuples are perfect for many "data only" representations, but they are not ideal for all situations. Like tuples and strings, named tuples are immutable, so we cannot modify an attribute once it has been set. For example, the current value of my company's stock has gone down since we started this discussion, but we can't set the new value:
>>> stock.current = 74.98 Traceback (most recent call last): File "<stdin>", line 1, in <module> AttributeError: can't set attribute
If we need to be able to change stored data, a dictionary may be what we need instead.
Named tuples
So, what do we do when we want to group values together, but know we're frequently going to need to access them individually? Well, we could use an empty object, as discussed in the previous section (but that is rarely useful unless we anticipate adding behavior later), or we could use a dictionary (most useful if we don't know exactly how many or which specific data will be stored), as we'll cover in the next section.
If, however, we do not need to add behavior to the object, and we know in advance what attributes we need to store, we can use a named tuple. Named tuples are tuples with attitude. They are a great way to group read-only data together.
Constructing a named tuple takes a bit more work than a normal tuple. First, we have to import namedtuple, as it is not in the namespace by default. Then, we describe the named tuple by giving it a name and outlining its attributes. This returns a class-like object that we can instantiate with the required values as many times as we want:
from collections import namedtuple
Stock = namedtuple("Stock", "symbol current high low")
stock = Stock("FB", 75.00, high=75.03, low=74.90)The namedtuple constructor accepts two arguments. The first is an identifier for the named tuple. The second is a string of space-separated attributes that the named tuple can have. The first attribute should be listed, followed by a space (or comma if you prefer), then the second attribute, then another space, and so on. The result is an object that can be called just like a normal class to instantiate other objects. The constructor must have exactly the right number of arguments that can be passed in as arguments or keyword arguments. As with normal objects, we can create as many instances of this "class" as we like, with different values for each.
The resulting namedtuple can then be packed, unpacked, and otherwise treated like a normal tuple, but we can also access individual attributes on it as if it were an object:
>>> stock.high 75.03 >>> symbol, current, high, low = stock >>> current 75.00
Tip
Remember that creating named tuples is a two-step process. First, use collections.namedtuple to create a class, and then construct instances of that class.
Named tuples are perfect for many "data only" representations, but they are not ideal for all situations. Like tuples and strings, named tuples are immutable, so we cannot modify an attribute once it has been set. For example, the current value of my company's stock has gone down since we started this discussion, but we can't set the new value:
>>> stock.current = 74.98 Traceback (most recent call last): File "<stdin>", line 1, in <module> AttributeError: can't set attribute
If we need to be able to change stored data, a dictionary may be what we need instead.
Dictionaries
Dictionaries are incredibly useful containers that allow us to map objects directly to other objects. An empty object with attributes to it is a sort of dictionary; the names of the properties map to the property values. This is actually closer to the truth than it sounds; internally, objects normally represent attributes as a dictionary, where the values are properties or methods on the objects (see the __dict__ attribute if you don't believe me). Even the attributes on a module are stored, internally, in a dictionary.
Dictionaries are extremely efficient at looking up a value, given a specific key object that maps to that value. They should always be used when you want to find one object based on some other object. The object that is being stored is called the value; the object that is being used as an index is called the key. We've already seen dictionary syntax in some of our previous examples.
Dictionaries can be created either using the dict() constructor or using the {} syntax shortcut. In practice, the latter format is almost always used. We can prepopulate a dictionary by separating the keys from the values using a colon, and separating the key value pairs using a comma.
For example, in a stock application, we would most often want to look up prices by the stock symbol. We can create a dictionary that uses stock symbols as keys, and tuples of current, high, and low as values like this:
stocks = {"GOOG": (613.30, 625.86, 610.50),
"MSFT": (30.25, 30.70, 30.19)}As we've seen in previous examples, we can then look up values in the dictionary by requesting a key inside square brackets. If the key is not in the dictionary, it will raise an exception:
>>> stocks["GOOG"] (613.3, 625.86, 610.5) >>> stocks["RIM"] Traceback (most recent call last): File "<stdin>", line 1, in <module> KeyError: 'RIM'
We can, of course, catch the KeyError and handle it. But we have other options. Remember, dictionaries are objects, even if their primary purpose is to hold other objects. As such, they have several behaviors associated with them. One of the most useful of these methods is the get method; it accepts a key as the first parameter and an optional default value if the key doesn't exist:
>>> print(stocks.get("RIM")) None >>> stocks.get("RIM", "NOT FOUND") 'NOT FOUND'
For even more control, we can use the setdefault method. If the key is in the dictionary, this method behaves just like get; it returns the value for that key. Otherwise, if the key is not in the dictionary, it will not only return the default value we supply in the method call (just like get does), it will also set the key to that same value. Another way to think of it is that setdefault sets a value in the dictionary only if that value has not previously been set. Then it returns the value in the dictionary, either the one that was already there, or the newly provided default value.
>>> stocks.setdefault("GOOG", "INVALID") (613.3, 625.86, 610.5) >>> stocks.setdefault("BBRY", (10.50, 10.62, 10.39)) (10.50, 10.62, 10.39) >>> stocks["BBRY"] (10.50, 10.62, 10.39)
The GOOG stock was already in the dictionary, so when we tried to setdefault it to an invalid value, it just returned the value already in the dictionary. BBRY was not in the dictionary, so setdefault returned the default value and set the new value in the dictionary for us. We then check that the new stock is, indeed, in the dictionary.
Three other very useful dictionary methods are keys(), values(), and items(). The first two return an iterator over all the keys and all the values in the dictionary. We can use these like lists or in for loops if we want to process all the keys or values. The items() method is probably the most useful; it returns an iterator over tuples of (key, value) pairs for every item in the dictionary. This works great with tuple unpacking in a for loop to loop over associated keys and values. This example does just that to print each stock in the dictionary with its current value:
>>> for stock, values in stocks.items(): ... print("{} last value is {}".format(stock, values[0])) ... GOOG last value is 613.3 BBRY last value is 10.50 MSFT last value is 30.25
Each key/value tuple is unpacked into two variables named stock and values (we could use any variable names we wanted, but these both seem appropriate) and then printed in a formatted string.
Notice that the stocks do not show up in the same order in which they were inserted. Dictionaries, due to the efficient algorithm (known as hashing) that is used to make key lookup so fast, are inherently unsorted.
So, there are numerous ways to retrieve data from a dictionary once it has been instantiated; we can use square brackets as index syntax, the get method, the setdefault method, or iterate over the items method, among others.
Finally, as you likely already know, we can set a value in a dictionary using the same indexing syntax we use to retrieve a value:
>>> stocks["GOOG"] = (597.63, 610.00, 596.28) >>> stocks['GOOG'] (597.63, 610.0, 596.28)
Google's price is lower today, so I've updated the tuple value in the dictionary. We can use this index syntax to set a value for any key, regardless of whether the key is in the dictionary. If it is in the dictionary, the old value will be replaced with the new one; otherwise, a new key/value pair will be created.
We've been using strings as dictionary keys, so far, but we aren't limited to string keys. It is common to use strings as keys, especially when we're storing data in a dictionary to gather it together (instead of using an object with named properties). But we can also use tuples, numbers, or even objects we've defined ourselves as dictionary keys. We can even use different types of keys in a single dictionary:
random_keys = {}
random_keys["astring"] = "somestring"
random_keys[5] = "aninteger"
random_keys[25.2] = "floats work too"
random_keys[("abc", 123)] = "so do tuples"
class AnObject:
def __init__(self, avalue):
self.avalue = avalue
my_object = AnObject(14)
random_keys[my_object] = "We can even store objects"
my_object.avalue = 12
try:
random_keys[[1,2,3]] = "we can't store lists though"
except:
print("unable to store list\n")
for key, value in random_keys.items():
print("{} has value {}".format(key, value))This code shows several different types of keys we can supply to a dictionary. It also shows one type of object that cannot be used. We've already used lists extensively, and we'll be seeing many more details of them in the next section. Because lists can change at any time (by adding or removing items, for example), they cannot hash to a specific value.
Objects that are hashable basically have a defined algorithm that converts the object into a unique integer value for rapid lookup. This hash is what is actually used to look up values in a dictionary. For example, strings map to integers based on the characters in the string, while tuples combine hashes of the items inside the tuple. Any two objects that are somehow considered equal (like strings with the same characters or tuples with the same values) should have the same hash value, and the hash value for an object should never ever change. Lists, however, can have their contents changed, which would change their hash value (two lists should only be equal if their contents are the same). Because of this, they can't be used as dictionary keys. For the same reason, dictionaries cannot be used as keys into other dictionaries.
In contrast, there are no limits on the types of objects that can be used as dictionary values. We can use a string key that maps to a list value, for example, or we can have a nested dictionary as a value in another dictionary.
Dictionary use cases
Dictionaries are extremely versatile and have numerous uses. There are two major ways that dictionaries can be used. The first is dictionaries where all the keys represent different instances of similar objects; for example, our stock dictionary. This is an indexing system. We use the stock symbol as an index to the values. The values could even have been complicated self-defined objects that made buy and sell decisions or set a stop-loss, rather than our simple tuples.
The second design is dictionaries where each key represents some aspect of a single structure; in this case, we'd probably use a separate dictionary for each object, and they'd all have similar (though often not identical) sets of keys. This latter situation can often also be solved with named tuples. These should typically be used when we know exactly what attributes the data must store, and we know that all pieces of the data must be supplied at once (when the item is constructed). But if we need to create or change dictionary keys over time or we don't know exactly what the keys might be, a dictionary is more suitable.
Using defaultdict
We've seen how to use setdefault to set a default value if a key doesn't exist, but this can get a bit monotonous if we need to set a default value every time we look up a value. For example, if we're writing code that counts the number of times a letter occurs in a given sentence, we could do this:
def letter_frequency(sentence):
frequencies = {}
for letter in sentence:
frequency = frequencies.setdefault(letter, 0)
frequencies[letter] = frequency + 1
return frequenciesEvery time we access the dictionary, we need to check that it has a value already, and if not, set it to zero. When something like this needs to be done every time an empty key is requested, we can use a different version of the dictionary, called defaultdict:
from collections import defaultdict def letter_frequency(sentence): frequencies = defaultdict(int) for letter in sentence: frequencies[letter] += 1 return frequencies
This code looks like it couldn't possibly work. The defaultdict accepts a function in its constructor. Whenever a key is accessed that is not already in the dictionary, it calls that function, with no parameters, to create a default value.
In this case, the function it calls is int, which is the constructor for an integer object. Normally, integers are created simply by typing an integer number into our code, and if we do create one using the int constructor, we pass it the item we want to create (for example, to convert a string of digits into an integer). But if we call int without any arguments, it returns, conveniently, the number zero. In this code, if the letter doesn't exist in the defaultdict, the number zero is returned when we access it. Then we add one to this number to indicate we've found an instance of that letter, and the next time we find one, that number will be returned and we can increment the value again.
The defaultdict is useful for creating dictionaries of containers. If we want to create a dictionary of stock prices for the past 30 days, we could use a stock symbol as the key and store the prices in list; the first time we access the stock price, we would want it to create an empty list. Simply pass list into the defaultdict, and it will be called every time an empty key is accessed. We can do similar things with sets or even empty dictionaries if we want to associate one with a key.
Of course, we can also write our own functions and pass them into the defaultdict. Suppose we want to create a defaultdict where each new element contains a tuple of the number of items inserted into the dictionary at that time and an empty list to hold other things. Nobody knows why we would want to create such an object, but let's have a look:
from collections import defaultdict
num_items = 0
def tuple_counter():
global num_items
num_items += 1
return (num_items, [])
d = defaultdict(tuple_counter)
When we run this code, we can access empty keys and insert into the list all in one statement:
>>> d = defaultdict(tuple_counter) >>> d['a'][1].append("hello") >>> d['b'][1].append('world') >>> d defaultdict(<function tuple_counter at 0x82f2c6c>, {'a': (1, ['hello']), 'b': (2, ['world'])})
When we print dict at the end, we see that the counter really was working.
Note
This example, while succinctly demonstrating how to create our own function for defaultdict, is not actually very good code; using a global variable means that if we created four different defaultdict segments that each used tuple_counter, it would count the number of entries in all dictionaries, rather than having a different count for each one. It would be better to create a class and pass a method on that class to defaultdict.
Counter
You'd think that you couldn't get much simpler than defaultdict(int), but the "I want to count specific instances in an iterable" use case is common enough that the Python developers created a specific class for it. The previous code that counts characters in a string can easily be calculated in a single line:
from collections import Counter
def letter_frequency(sentence):
return Counter(sentence)The Counter object behaves like a beefed up dictionary where the keys are the items being counted and the values are the number of such items. One of the most useful functions is the most_common() method. It returns a list of (key, count) tuples ordered by the count. You can optionally pass an integer argument into most_common() to request only the top most common elements. For example, you could write a simple polling application as follows:
from collections import Counter
responses = [
"vanilla",
"chocolate",
"vanilla",
"vanilla",
"caramel",
"strawberry",
"vanilla"
]
print(
"The children voted for {} ice cream".format(
Counter(responses).most_common(1)[0][0]
)
)Presumably, you'd get the responses from a database or by using a complicated vision algorithm to count the kids who raised their hands. Here, we hardcode it so that we can test the most_common method. It returns a list that has only one element (because we requested one element in the parameter). This element stores the name of the top choice at position zero, hence the double [0][0] at the end of the call. I think they look like a surprised face, don't you? Your computer is probably amazed it can count data so easily. It's ancestor, Hollerith's Tabulating Machine for the 1890 US census, must be so jealous!
Dictionary use cases
Dictionaries are extremely versatile and have numerous uses. There are two major ways that dictionaries can be used. The first is dictionaries where all the keys represent different instances of similar objects; for example, our stock dictionary. This is an indexing system. We use the stock symbol as an index to the values. The values could even have been complicated self-defined objects that made buy and sell decisions or set a stop-loss, rather than our simple tuples.
The second design is dictionaries where each key represents some aspect of a single structure; in this case, we'd probably use a separate dictionary for each object, and they'd all have similar (though often not identical) sets of keys. This latter situation can often also be solved with named tuples. These should typically be used when we know exactly what attributes the data must store, and we know that all pieces of the data must be supplied at once (when the item is constructed). But if we need to create or change dictionary keys over time or we don't know exactly what the keys might be, a dictionary is more suitable.
Using defaultdict
We've seen how to use setdefault to set a default value if a key doesn't exist, but this can get a bit monotonous if we need to set a default value every time we look up a value. For example, if we're writing code that counts the number of times a letter occurs in a given sentence, we could do this:
def letter_frequency(sentence):
frequencies = {}
for letter in sentence:
frequency = frequencies.setdefault(letter, 0)
frequencies[letter] = frequency + 1
return frequenciesEvery time we access the dictionary, we need to check that it has a value already, and if not, set it to zero. When something like this needs to be done every time an empty key is requested, we can use a different version of the dictionary, called defaultdict:
from collections import defaultdict def letter_frequency(sentence): frequencies = defaultdict(int) for letter in sentence: frequencies[letter] += 1 return frequencies
This code looks like it couldn't possibly work. The defaultdict accepts a function in its constructor. Whenever a key is accessed that is not already in the dictionary, it calls that function, with no parameters, to create a default value.
In this case, the function it calls is int, which is the constructor for an integer object. Normally, integers are created simply by typing an integer number into our code, and if we do create one using the int constructor, we pass it the item we want to create (for example, to convert a string of digits into an integer). But if we call int without any arguments, it returns, conveniently, the number zero. In this code, if the letter doesn't exist in the defaultdict, the number zero is returned when we access it. Then we add one to this number to indicate we've found an instance of that letter, and the next time we find one, that number will be returned and we can increment the value again.
The defaultdict is useful for creating dictionaries of containers. If we want to create a dictionary of stock prices for the past 30 days, we could use a stock symbol as the key and store the prices in list; the first time we access the stock price, we would want it to create an empty list. Simply pass list into the defaultdict, and it will be called every time an empty key is accessed. We can do similar things with sets or even empty dictionaries if we want to associate one with a key.
Of course, we can also write our own functions and pass them into the defaultdict. Suppose we want to create a defaultdict where each new element contains a tuple of the number of items inserted into the dictionary at that time and an empty list to hold other things. Nobody knows why we would want to create such an object, but let's have a look:
from collections import defaultdict
num_items = 0
def tuple_counter():
global num_items
num_items += 1
return (num_items, [])
d = defaultdict(tuple_counter)
When we run this code, we can access empty keys and insert into the list all in one statement:
>>> d = defaultdict(tuple_counter) >>> d['a'][1].append("hello") >>> d['b'][1].append('world') >>> d defaultdict(<function tuple_counter at 0x82f2c6c>, {'a': (1, ['hello']), 'b': (2, ['world'])})
When we print dict at the end, we see that the counter really was working.
Note
This example, while succinctly demonstrating how to create our own function for defaultdict, is not actually very good code; using a global variable means that if we created four different defaultdict segments that each used tuple_counter, it would count the number of entries in all dictionaries, rather than having a different count for each one. It would be better to create a class and pass a method on that class to defaultdict.
Counter
You'd think that you couldn't get much simpler than defaultdict(int), but the "I want to count specific instances in an iterable" use case is common enough that the Python developers created a specific class for it. The previous code that counts characters in a string can easily be calculated in a single line:
from collections import Counter
def letter_frequency(sentence):
return Counter(sentence)The Counter object behaves like a beefed up dictionary where the keys are the items being counted and the values are the number of such items. One of the most useful functions is the most_common() method. It returns a list of (key, count) tuples ordered by the count. You can optionally pass an integer argument into most_common() to request only the top most common elements. For example, you could write a simple polling application as follows:
from collections import Counter
responses = [
"vanilla",
"chocolate",
"vanilla",
"vanilla",
"caramel",
"strawberry",
"vanilla"
]
print(
"The children voted for {} ice cream".format(
Counter(responses).most_common(1)[0][0]
)
)Presumably, you'd get the responses from a database or by using a complicated vision algorithm to count the kids who raised their hands. Here, we hardcode it so that we can test the most_common method. It returns a list that has only one element (because we requested one element in the parameter). This element stores the name of the top choice at position zero, hence the double [0][0] at the end of the call. I think they look like a surprised face, don't you? Your computer is probably amazed it can count data so easily. It's ancestor, Hollerith's Tabulating Machine for the 1890 US census, must be so jealous!
Using defaultdict
We've seen how to use setdefault to set a default value if a key doesn't exist, but this can get a bit monotonous if we need to set a default value every time we look up a value. For example, if we're writing code that counts the number of times a letter occurs in a given sentence, we could do this:
def letter_frequency(sentence):
frequencies = {}
for letter in sentence:
frequency = frequencies.setdefault(letter, 0)
frequencies[letter] = frequency + 1
return frequenciesEvery time we access the dictionary, we need to check that it has a value already, and if not, set it to zero. When something like this needs to be done every time an empty key is requested, we can use a different version of the dictionary, called defaultdict:
from collections import defaultdict def letter_frequency(sentence): frequencies = defaultdict(int) for letter in sentence: frequencies[letter] += 1 return frequencies
This code looks like it couldn't possibly work. The defaultdict accepts a function in its constructor. Whenever a key is accessed that is not already in the dictionary, it calls that function, with no parameters, to create a default value.
In this case, the function it calls is int, which is the constructor for an integer object. Normally, integers are created simply by typing an integer number into our code, and if we do create one using the int constructor, we pass it the item we want to create (for example, to convert a string of digits into an integer). But if we call int without any arguments, it returns, conveniently, the number zero. In this code, if the letter doesn't exist in the defaultdict, the number zero is returned when we access it. Then we add one to this number to indicate we've found an instance of that letter, and the next time we find one, that number will be returned and we can increment the value again.
The defaultdict is useful for creating dictionaries of containers. If we want to create a dictionary of stock prices for the past 30 days, we could use a stock symbol as the key and store the prices in list; the first time we access the stock price, we would want it to create an empty list. Simply pass list into the defaultdict, and it will be called every time an empty key is accessed. We can do similar things with sets or even empty dictionaries if we want to associate one with a key.
Of course, we can also write our own functions and pass them into the defaultdict. Suppose we want to create a defaultdict where each new element contains a tuple of the number of items inserted into the dictionary at that time and an empty list to hold other things. Nobody knows why we would want to create such an object, but let's have a look:
from collections import defaultdict
num_items = 0
def tuple_counter():
global num_items
num_items += 1
return (num_items, [])
d = defaultdict(tuple_counter)
When we run this code, we can access empty keys and insert into the list all in one statement:
>>> d = defaultdict(tuple_counter) >>> d['a'][1].append("hello") >>> d['b'][1].append('world') >>> d defaultdict(<function tuple_counter at 0x82f2c6c>, {'a': (1, ['hello']), 'b': (2, ['world'])})
When we print dict at the end, we see that the counter really was working.
Note
This example, while succinctly demonstrating how to create our own function for defaultdict, is not actually very good code; using a global variable means that if we created four different defaultdict segments that each used tuple_counter, it would count the number of entries in all dictionaries, rather than having a different count for each one. It would be better to create a class and pass a method on that class to defaultdict.
Counter
You'd think that you couldn't get much simpler than defaultdict(int), but the "I want to count specific instances in an iterable" use case is common enough that the Python developers created a specific class for it. The previous code that counts characters in a string can easily be calculated in a single line:
from collections import Counter
def letter_frequency(sentence):
return Counter(sentence)The Counter object behaves like a beefed up dictionary where the keys are the items being counted and the values are the number of such items. One of the most useful functions is the most_common() method. It returns a list of (key, count) tuples ordered by the count. You can optionally pass an integer argument into most_common() to request only the top most common elements. For example, you could write a simple polling application as follows:
from collections import Counter
responses = [
"vanilla",
"chocolate",
"vanilla",
"vanilla",
"caramel",
"strawberry",
"vanilla"
]
print(
"The children voted for {} ice cream".format(
Counter(responses).most_common(1)[0][0]
)
)Presumably, you'd get the responses from a database or by using a complicated vision algorithm to count the kids who raised their hands. Here, we hardcode it so that we can test the most_common method. It returns a list that has only one element (because we requested one element in the parameter). This element stores the name of the top choice at position zero, hence the double [0][0] at the end of the call. I think they look like a surprised face, don't you? Your computer is probably amazed it can count data so easily. It's ancestor, Hollerith's Tabulating Machine for the 1890 US census, must be so jealous!
Counter
You'd think that you couldn't get much simpler than defaultdict(int), but the "I want to count specific instances in an iterable" use case is common enough that the Python developers created a specific class for it. The previous code that counts characters in a string can easily be calculated in a single line:
from collections import Counter
def letter_frequency(sentence):
return Counter(sentence)The Counter object behaves like a beefed up dictionary where the keys are the items being counted and the values are the number of such items. One of the most useful functions is the most_common() method. It returns a list of (key, count) tuples ordered by the count. You can optionally pass an integer argument into most_common() to request only the top most common elements. For example, you could write a simple polling application as follows:
from collections import Counter
responses = [
"vanilla",
"chocolate",
"vanilla",
"vanilla",
"caramel",
"strawberry",
"vanilla"
]
print(
"The children voted for {} ice cream".format(
Counter(responses).most_common(1)[0][0]
)
)Presumably, you'd get the responses from a database or by using a complicated vision algorithm to count the kids who raised their hands. Here, we hardcode it so that we can test the most_common method. It returns a list that has only one element (because we requested one element in the parameter). This element stores the name of the top choice at position zero, hence the double [0][0] at the end of the call. I think they look like a surprised face, don't you? Your computer is probably amazed it can count data so easily. It's ancestor, Hollerith's Tabulating Machine for the 1890 US census, must be so jealous!
Lists
Lists are the least object-oriented of Python's data structures. While lists are, themselves, objects, there is a lot of syntax in Python to make using them as painless as possible. Unlike many other object-oriented languages, lists in Python are simply available. We don't need to import them and rarely need to call methods on them. We can loop over a list without explicitly requesting an iterator object, and we can construct a list (as with a dictionary) with custom syntax. Further, list comprehensions and generator expressions turn them into a veritable Swiss-army knife of computing functionality.
We won't go into too much detail of the syntax; you've seen it in introductory tutorials across the Web and in previous examples in this book. You can't code Python very long without learning how to use lists! Instead, we'll be covering when lists should be used, and their nature as objects. If you don't know how to create or append to a list, how to retrieve items from a list, or what "slice notation" is, I direct you to the official Python tutorial, post-haste. It can be found online at http://docs.python.org/3/tutorial/.
In Python, lists should normally be used when we want to store several instances of the "same" type of object; lists of strings or lists of numbers; most often, lists of objects we've defined ourselves. Lists should always be used when we want to store items in some kind of order. Often, this is the order in which they were inserted, but they can also be sorted by some criteria.
As we saw in the case study from the previous chapter, lists are also very useful when we need to modify the contents: insert to or delete from an arbitrary location of the list, or update a value within the list.
Like dictionaries, Python lists use an extremely efficient and well-tuned internal data structure so we can worry about what we're storing, rather than how we're storing it. Many object-oriented languages provide different data structures for queues, stacks, linked lists, and array-based lists. Python does provide special instances of some of these classes, if optimizing access to huge sets of data is required. Normally, however, the list data structure can serve all these purposes at once, and the coder has complete control over how they access it.
Don't use lists for collecting different attributes of individual items. We do not want, for example, a list of the properties a particular shape has. Tuples, named tuples, dictionaries, and objects would all be more suitable for this purpose. In some languages, they might create a list in which each alternate item is a different type; for example, they might write ['a', 1, 'b', 3] for our letter frequency list. They'd have to use a strange loop that accesses two elements in the list at once or a modulus operator to determine which position was being accessed.
Don't do this in Python. We can group related items together using a dictionary, as we did in the previous section (if sort order doesn't matter), or using a list of tuples. Here's a rather convoluted example that demonstrates how we could do the frequency example using a list. It is much more complicated than the dictionary examples, and illustrates the effect choosing the right (or wrong) data structure can have on the readability of our code:
import string CHARACTERS = list(string.ascii_letters) + [" "] def letter_frequency(sentence): frequencies = [(c, 0) for c in CHARACTERS] for letter in sentence: index = CHARACTERS.index(letter) frequencies[index] = (letter,frequencies[index][1]+1) return frequencies
This code starts with a list of possible characters. The string.ascii_letters attribute provides a string of all the letters, lowercase and uppercase, in order. We convert this to a list, and then use list concatenation (the plus operator causes two lists to be merged into one) to add one more character, the space. These are the available characters in our frequency list (the code would break if we tried to add a letter that wasn't in the list, but an exception handler could solve this).
The first line inside the function uses a list comprehension to turn the CHARACTERS list into a list of tuples. List comprehensions are an important, non-object-oriented tool in Python; we'll be covering them in detail in the next chapter.
Then we loop over each of the characters in the sentence. We first look up the index of the character in the CHARACTERS list, which we know has the same index in our frequencies list, since we just created the second list from the first. We then update that index in the frequencies list by creating a new tuple, discarding the original one. Aside from the garbage collection and memory waste concerns, this is rather difficult to read!
Like dictionaries, lists are objects too, and they have several methods that can be invoked upon them. Here are some common ones:
- The
append(element)method adds an element to the end of the list - The
insert(index, element)method inserts an item at a specific position - The
count(element)method tells us how many times an element appears in the list - The
index()method tells us the index of an item in the list, raising an exception if it can't find it - The
find()method does the same thing, but returns-1instead of raising an exception for missing items - The
reverse()method does exactly what it says—turns the list around - The
sort()method has some rather intricate object-oriented behaviors, which we'll cover now
Sorting lists
Without any parameters, sort will generally do the expected thing. If it's a list of strings, it will place them in alphabetical order. This operation is case sensitive, so all capital letters will be sorted before lowercase letters, that is Z comes before a. If it is a list of numbers, they will be sorted in numerical order. If a list of tuples is provided, the list is sorted by the first element in each tuple. If a mixture containing unsortable items is supplied, the sort will raise a TypeError exception.
If we want to place objects we define ourselves into a list and make those objects sortable, we have to do a bit more work. The special method __lt__, which stands for "less than", should be defined on the class to make instances of that class comparable. The sort method on list will access this method on each object to determine where it goes in the list. This method should return True if our class is somehow less than the passed parameter, and False otherwise. Here's a rather silly class that can be sorted based on either a string or a number:
class WeirdSortee:
def __init__(self, string, number, sort_num):
self.string = string
self.number = number
self.sort_num = sort_num
def __lt__(self, object):
if self.sort_num:
return self.number < object.number
return self.string < object.string
def __repr__(self):
return"{}:{}".format(self.string, self.number)The __repr__ method makes it easy to see the two values when we print a list. The __lt__ method's implementation compares the object to another instance of the same class (or any duck typed object that has string, number, and sort_num attributes; it will fail if those attributes are missing). The following output illustrates this class in action, when it comes to sorting:
>>> a = WeirdSortee('a', 4, True) >>> b = WeirdSortee('b', 3, True) >>> c = WeirdSortee('c', 2, True) >>> d = WeirdSortee('d', 1, True) >>> l = [a,b,c,d] >>> l [a:4, b:3, c:2, d:1] >>> l.sort() >>> l [d:1, c:2, b:3, a:4] >>> for i in l: ... i.sort_num = False ... >>> l.sort() >>> l [a:4, b:3, c:2, d:1]
The first time we call sort, it sorts by numbers because sort_num is True on all the objects being compared. The second time, it sorts by letters. The __lt__ method is the only one we need to implement to enable sorting. Technically, however, if it is implemented, the class should normally also implement the similar __gt__, __eq__, __ne__, __ge__, and __le__ methods so that all of the <, >, ==, !=, >=, and <= operators also work properly. You can get this for free by implementing __lt__ and __eq__, and then applying the @total_ordering class decorator to supply the rest:
from functools import total_ordering
@total_ordering
class WeirdSortee:
def __init__(self, string, number, sort_num):
self.string = string
self.number = number
self.sort_num = sort_num
def __lt__(self, object):
if self.sort_num:
return self.number < object.number
return self.string < object.string
def __repr__(self):
return"{}:{}".format(self.string, self.number)
def __eq__(self, object):
return all((
self.string == object.string,
self.number == object.number,
self.sort_num == object.number
))This is useful if we want to be able to use operators on our objects. However, if all we want to do is customize our sort orders, even this is overkill. For such a use case, the sort method can take an optional key argument. This argument is a function that can translate each object in a list into an object that can somehow be compared. For example, we can use str.lower as the key argument to perform a case-insensitive sort on a list of strings:
>>> l = ["hello", "HELP", "Helo"] >>> l.sort() >>> l ['HELP', 'Helo', 'hello'] >>> l.sort(key=str.lower) >>> l ['hello', 'Helo', 'HELP']
Remember, even though lower is a method on string objects, it is also a function that can accept a single argument, self. In other words, str.lower(item) is equivalent to item.lower(). When we pass this function as a key, it performs the comparison on lowercase values instead of doing the default case-sensitive comparison.
There are a few sort key operations that are so common that the Python team has supplied them so you don't have to write them yourself. For example, it is often common to sort a list of tuples by something other than the first item in the list. The operator.itemgetter method can be used as a key to do this:
>>> from operator import itemgetter >>> l = [('h', 4), ('n', 6), ('o', 5), ('p', 1), ('t', 3), ('y', 2)] >>> l.sort(key=itemgetter(1)) >>> l [('p', 1), ('y', 2), ('t', 3), ('h', 4), ('o', 5), ('n', 6)]
The itemgetter function is the most commonly used one (it works if the objects are dictionaries, too), but you will sometimes find use for attrgetter and methodcaller, which return attributes on an object and the results of method calls on objects for the same purpose. See the operator module documentation for more information.
Sorting lists
Without any parameters, sort will generally do the expected thing. If it's a list of strings, it will place them in alphabetical order. This operation is case sensitive, so all capital letters will be sorted before lowercase letters, that is Z comes before a. If it is a list of numbers, they will be sorted in numerical order. If a list of tuples is provided, the list is sorted by the first element in each tuple. If a mixture containing unsortable items is supplied, the sort will raise a TypeError exception.
If we want to place objects we define ourselves into a list and make those objects sortable, we have to do a bit more work. The special method __lt__, which stands for "less than", should be defined on the class to make instances of that class comparable. The sort method on list will access this method on each object to determine where it goes in the list. This method should return True if our class is somehow less than the passed parameter, and False otherwise. Here's a rather silly class that can be sorted based on either a string or a number:
class WeirdSortee:
def __init__(self, string, number, sort_num):
self.string = string
self.number = number
self.sort_num = sort_num
def __lt__(self, object):
if self.sort_num:
return self.number < object.number
return self.string < object.string
def __repr__(self):
return"{}:{}".format(self.string, self.number)The __repr__ method makes it easy to see the two values when we print a list. The __lt__ method's implementation compares the object to another instance of the same class (or any duck typed object that has string, number, and sort_num attributes; it will fail if those attributes are missing). The following output illustrates this class in action, when it comes to sorting:
>>> a = WeirdSortee('a', 4, True) >>> b = WeirdSortee('b', 3, True) >>> c = WeirdSortee('c', 2, True) >>> d = WeirdSortee('d', 1, True) >>> l = [a,b,c,d] >>> l [a:4, b:3, c:2, d:1] >>> l.sort() >>> l [d:1, c:2, b:3, a:4] >>> for i in l: ... i.sort_num = False ... >>> l.sort() >>> l [a:4, b:3, c:2, d:1]
The first time we call sort, it sorts by numbers because sort_num is True on all the objects being compared. The second time, it sorts by letters. The __lt__ method is the only one we need to implement to enable sorting. Technically, however, if it is implemented, the class should normally also implement the similar __gt__, __eq__, __ne__, __ge__, and __le__ methods so that all of the <, >, ==, !=, >=, and <= operators also work properly. You can get this for free by implementing __lt__ and __eq__, and then applying the @total_ordering class decorator to supply the rest:
from functools import total_ordering
@total_ordering
class WeirdSortee:
def __init__(self, string, number, sort_num):
self.string = string
self.number = number
self.sort_num = sort_num
def __lt__(self, object):
if self.sort_num:
return self.number < object.number
return self.string < object.string
def __repr__(self):
return"{}:{}".format(self.string, self.number)
def __eq__(self, object):
return all((
self.string == object.string,
self.number == object.number,
self.sort_num == object.number
))This is useful if we want to be able to use operators on our objects. However, if all we want to do is customize our sort orders, even this is overkill. For such a use case, the sort method can take an optional key argument. This argument is a function that can translate each object in a list into an object that can somehow be compared. For example, we can use str.lower as the key argument to perform a case-insensitive sort on a list of strings:
>>> l = ["hello", "HELP", "Helo"] >>> l.sort() >>> l ['HELP', 'Helo', 'hello'] >>> l.sort(key=str.lower) >>> l ['hello', 'Helo', 'HELP']
Remember, even though lower is a method on string objects, it is also a function that can accept a single argument, self. In other words, str.lower(item) is equivalent to item.lower(). When we pass this function as a key, it performs the comparison on lowercase values instead of doing the default case-sensitive comparison.
There are a few sort key operations that are so common that the Python team has supplied them so you don't have to write them yourself. For example, it is often common to sort a list of tuples by something other than the first item in the list. The operator.itemgetter method can be used as a key to do this:
>>> from operator import itemgetter >>> l = [('h', 4), ('n', 6), ('o', 5), ('p', 1), ('t', 3), ('y', 2)] >>> l.sort(key=itemgetter(1)) >>> l [('p', 1), ('y', 2), ('t', 3), ('h', 4), ('o', 5), ('n', 6)]
The itemgetter function is the most commonly used one (it works if the objects are dictionaries, too), but you will sometimes find use for attrgetter and methodcaller, which return attributes on an object and the results of method calls on objects for the same purpose. See the operator module documentation for more information.
Sets
Lists are extremely versatile tools that suit most container object applications. But they are not useful when we want to ensure objects in the list are unique. For example, a song library may contain many songs by the same artist. If we want to sort through the library and create a list of all the artists, we would have to check the list to see if we've added the artist already, before we add them again.
This is where sets come in. Sets come from mathematics, where they represent an unordered group of (usually) unique numbers. We can add a number to a set five times, but it will show up in the set only once.
In Python, sets can hold any hashable object, not just numbers. Hashable objects are the same objects that can be used as keys in dictionaries; so again, lists and dictionaries are out. Like mathematical sets, they can store only one copy of each object. So if we're trying to create a list of song artists, we can create a set of string names and simply add them to the set. This example starts with a list of (song, artist) tuples and creates a set of the artists:
song_library = [("Phantom Of The Opera", "Sarah Brightman"),
("Knocking On Heaven's Door", "Guns N' Roses"),
("Captain Nemo", "Sarah Brightman"),
("Patterns In The Ivy", "Opeth"),
("November Rain", "Guns N' Roses"),
("Beautiful", "Sarah Brightman"),
("Mal's Song", "Vixy and Tony")]
artists = set()
for song, artist in song_library:
artists.add(artist)
print(artists)There is no built-in syntax for an empty set as there is for lists and dictionaries; we create a set using the set() constructor. However, we can use the curly braces (borrowed from dictionary syntax) to create a set, so long as the set contains values. If we use colons to separate pairs of values, it's a dictionary, as in {'key': 'value', 'key2': 'value2'}. If we just separate values with commas, it's a set, as in {'value', 'value2'}. Items can be added individually to the set using its add method. If we run this script, we see that the set works as advertised:
{'Sarah Brightman', "Guns N' Roses", 'Vixy and Tony', 'Opeth'}
If you're paying attention to the output, you'll notice that the items are not printed in the order they were added to the sets. Sets, like dictionaries, are unordered. They both use an underlying hash-based data structure for efficiency. Because they are unordered, sets cannot have items looked up by index. The primary purpose of a set is to divide the world into two groups: "things that are in the set", and, "things that are not in the set". It is easy to check whether an item is in the set or to loop over the items in a set, but if we want to sort or order them, we'll have to convert the set to a list. This output shows all three of these activities:
>>> "Opeth" in artists True >>> for artist in artists: ... print("{} plays good music".format(artist)) ... Sarah Brightman plays good music Guns N' Roses plays good music Vixy and Tony play good music Opeth plays good music >>> alphabetical = list(artists) >>> alphabetical.sort() >>> alphabetical ["Guns N' Roses", 'Opeth', 'Sarah Brightman', 'Vixy and Tony']
While the primary feature of a set is uniqueness, that is not its primary purpose. Sets are most useful when two or more of them are used in combination. Most of the methods on the set type operate on other sets, allowing us to efficiently combine or compare the items in two or more sets. These methods have strange names, since they use the same terminology used in mathematics. We'll start with three methods that return the same result, regardless of which is the calling set and which is the called set.
The union method is the most common and easiest to understand. It takes a second set as a parameter and returns a new set that contains all elements that are in either of the two sets; if an element is in both original sets, it will, of course, only show up once in the new set. Union is like a logical or operation, indeed, the | operator can be used on two sets to perform the union operation, if you don't like calling methods.
Conversely, the intersection method accepts a second set and returns a new set that contains only those elements that are in both sets. It is like a logical and operation, and can also be referenced using the & operator.
Finally, the
symmetric_difference method tells us what's left; it is the set of objects that are in one set or the other, but not both. The following example illustrates these methods by comparing some artists from my song library to those in my sister's:
my_artists = {"Sarah Brightman", "Guns N' Roses",
"Opeth", "Vixy and Tony"}
auburns_artists = {"Nickelback", "Guns N' Roses",
"Savage Garden"}
print("All: {}".format(my_artists.union(auburns_artists)))
print("Both: {}".format(auburns_artists.intersection(my_artists)))
print("Either but not both: {}".format(
my_artists.symmetric_difference(auburns_artists)))If we run this code, we see that these three methods do what the print statements suggest they will do:
All: {'Sarah Brightman', "Guns N' Roses", 'Vixy and Tony', 'Savage Garden', 'Opeth', 'Nickelback'} Both: {"Guns N' Roses"} Either but not both: {'Savage Garden', 'Opeth', 'Nickelback', 'Sarah Brightman', 'Vixy and Tony'}
These methods all return the same result, regardless of which set calls the other. We can say my_artists.union(auburns_artists) or auburns_artists.union(my_artists) and get the same result. There are also methods that return different results depending on who is the caller and who is the argument.
These methods include issubset and issuperset, which are the inverse of each other. Both return a bool. The issubset method returns True, if all of the items in the calling set are also in the set passed as an argument. The issuperset method returns True if all of the items in the argument are also in the calling set. Thus s.issubset(t) and t.issuperset(s) are identical. They will both return True if t contains all the elements in s.
Finally, the difference method returns all the elements that are in the calling set, but not in the set passed as an argument; this is like half a symmetric_difference. The difference method can also be represented by the - operator. The following code illustrates these methods in action:
my_artists = {"Sarah Brightman", "Guns N' Roses",
"Opeth", "Vixy and Tony"}
bands = {"Guns N' Roses", "Opeth"}
print("my_artists is to bands:")
print("issuperset: {}".format(my_artists.issuperset(bands)))
print("issubset: {}".format(my_artists.issubset(bands)))
print("difference: {}".format(my_artists.difference(bands)))
print("*"*20)
print("bands is to my_artists:")
print("issuperset: {}".format(bands.issuperset(my_artists)))
print("issubset: {}".format(bands.issubset(my_artists)))
print("difference: {}".format(bands.difference(my_artists)))This code simply prints out the response of each method when called from one set on the other. Running it gives us the following output:
my_artists is to bands: issuperset: True issubset: False difference: {'Sarah Brightman', 'Vixy and Tony'} ******************** bands is to my_artists: issuperset: False issubset: True difference: set()
The difference method, in the second case, returns an empty set, since there are no items in bands that are not in my_artists.
The union, intersection, and difference methods can all take multiple sets as arguments; they will return, as we might expect, the set that is created when the operation is called on all the parameters.
So the methods on sets clearly suggest that sets are meant to operate on other sets, and that they are not just containers. If we have data coming in from two different sources and need to quickly combine them in some way, to determine where the data overlaps or is different, we can use set operations to efficiently compare them. Or if we have data incoming that may contain duplicates of data that has already been processed, we can use sets to compare the two and process only the new data.
Finally, it is valuable to know that sets are much more efficient than lists when checking for membership using the in keyword. If you use the syntax value in container on a set or a list, it will return True if one of the elements in container is equal to value and False otherwise. However, in a list, it will look at every object in the container until it finds the value, whereas in a set, it simply hashes the value and checks for membership. This means that a set will find the value in the same amount of time no matter how big the container is, but a list will take longer and longer to search for a value as the list contains more and more values.
Extending built-ins
We discussed briefly in Chapter 3, When Objects Are Alike, how built-in data types can be extended using inheritance. Now, we'll go into more detail as to when we would want to do that.
When we have a built-in container object that we want to add functionality to, we have two options. We can either create a new object, which holds that container as an attribute (composition), or we can subclass the built-in object and add or adapt methods on it to do what we want (inheritance).
Composition is usually the best alternative if all we want to do is use the container to store some objects using that container's features. That way, it's easy to pass that data structure into other methods and they will know how to interact with it. But we need to use inheritance if we want to change the way the container actually works. For example, if we want to ensure every item in a list is a string with exactly five characters, we need to extend list and override the append() method to raise an exception for invalid input. We'd also minimally have to override __setitem__(self, index, value), a special method on lists that is called whenever we use the x[index] = "value" syntax, and the extend() method.
Yes, lists are objects. All that special non-object-oriented looking syntax we've been looking at for accessing lists or dictionary keys, looping over containers, and similar tasks is actually "syntactic sugar" that maps to an object-oriented paradigm underneath. We might ask the Python designers why they did this. Isn't object-oriented programming always better? That question is easy to answer. In the following hypothetical examples, which is easier to read, as a programmer? Which requires less typing?
c = a + b c = a.add(b) l[0] = 5 l.setitem(0, 5) d[key] = value d.setitem(key, value) for x in alist: #do something with x it = alist.iterator() while it.has_next(): x = it.next() #do something with x
The highlighted sections show what object-oriented code might look like (in practice, these methods actually exist as special double-underscore methods on associated objects). Python programmers agree that the non-object-oriented syntax is easier both to read and to write. Yet all of the preceding Python syntaxes map to object-oriented methods underneath the hood. These methods have special names (with double-underscores before and after) to remind us that there is a better syntax out there. However, it gives us the means to override these behaviors. For example, we can make a special integer that always returns 0 when we add two of them together:
class SillyInt(int):
def __add__(self, num):
return 0This is an extremely bizarre thing to do, granted, but it perfectly illustrates these object-oriented principles in action:
>>> a = SillyInt(1) >>> b = SillyInt(2) >>> a + b 0
The awesome thing about the __add__ method is that we can add it to any class we write, and if we use the + operator on instances of that class, it will be called. This is how string, tuple, and list concatenation works, for example.
This is true of all the special methods. If we want to use x in myobj syntax for a custom-defined object, we can implement __contains__. If we want to use myobj[i] = value syntax, we supply a __setitem__ method and if we want to use something = myobj[i], we implement __getitem__.
There are 33 of these special methods on the list class. We can use the dir function to see all of them:
>>> dir(list) ['__add__', '__class__', '__contains__', '__delattr__','__delitem__', '__doc__', '__eq__', '__format__', '__ge__', '__getattribute__', '__getitem__', '__gt__', '__hash__', '__iadd__', '__imul__', '__init__', '__iter__', '__le__', '__len__', '__lt__', '__mul__', '__ne__', '__new__', '__reduce__', '__reduce_ex__', '__repr__', '__reversed__', '__rmul__', '__setattr__', '__setitem__', '__sizeof__', '__str__', '__subclasshook__', 'append', 'count', 'extend', 'index', 'insert', 'pop', 'remove', 'reverse', 'sort'
Further, if we desire additional information on how any of these methods works, we can use the help function:
>>> help(list.__add__) Help on wrapper_descriptor: __add__(self, value, /) Return self+value.
The plus operator on lists concatenates two lists. We don't have room to discuss all of the available special functions in this book, but you are now able to explore all this functionality with dir and help. The official online Python reference (https://docs.python.org/3/) has plenty of useful information as well. Focus, especially, on the abstract base classes discussed in the collections module.
So, to get back to the earlier point about when we would want to use composition versus inheritance: if we need to somehow change any of the methods on the class—including the special methods—we definitely need to use inheritance. If we used composition, we could write methods that do the validation or alterations and ask the caller to use those methods, but there is nothing stopping them from accessing the property directly. They could insert an item into our list that does not have five characters, and that might confuse other methods in the list.
Often, the need to extend a built-in data type is an indication that we're using the wrong sort of data type. It is not always the case, but if we are looking to extend a built-in, we should carefully consider whether or not a different data structure would be more suitable.
For example, consider what it takes to create a dictionary that remembers the order in which keys were inserted. One way to do this is to keep an ordered list of keys that is stored in a specially derived subclass of dict. Then we can override the methods keys, values, __iter__, and items to return everything in order. Of course, we'll also have to override __setitem__ and setdefault to keep our list up to date. There are likely to be a few other methods in the output of dir(dict) that need overriding to keep the list and dictionary consistent (clear and __delitem__ come to mind, to track when items are removed), but we won't worry about them for this example.
So we'll be extending dict and adding a list of ordered keys. Trivial enough, but where do we create the actual list? We could include it in the __init__ method, which would work just fine, but we have no guarantees that any subclass will call that initializer. Remember the __new__ method we discussed in Chapter 2, Objects in Python? I said it was generally only useful in very special cases. This is one of those special cases. We know __new__ will be called exactly once, and we can create a list on the new instance that will always be available to our class. With that in mind, here is our entire sorted dictionary:
from collections import KeysView, ItemsView, ValuesView
class DictSorted(dict):
def __new__(*args, **kwargs):
new_dict = dict.__new__(*args, **kwargs)
new_dict.ordered_keys = []
return new_dict
def __setitem__(self, key, value):
'''self[key] = value syntax'''
if key not in self.ordered_keys:
self.ordered_keys.append(key)
super().__setitem__(key, value)
def setdefault(self, key, value):
if key not in self.ordered_keys:
self.ordered_keys.append(key)
return super().setdefault(key, value)
def keys(self):
return KeysView(self)
def values(self):
return ValuesView(self)
def items(self):
return ItemsView(self)
def __iter__(self):
'''for x in self syntax'''
return self.ordered_keys.__iter__()The __new__ method creates a new dictionary and then puts an empty list on that object. We don't override __init__, as the default implementation works (actually, this is only true if we initialize an empty DictSorted object, which is standard behavior. If we want to support other variations of the dict constructor, which accept dictionaries or lists of tuples, we'd need to fix __init__ to also update our ordered_keys list). The two methods for setting items are very similar; they both update the list of keys, but only if the item hasn't been added before. We don't want duplicates in the list, but we can't use a set here; it's unordered!
The keys, items, and values methods all return views onto the dictionary. The collections library provides three read-only View objects onto the dictionary; they use the __iter__ method to loop over the keys, and then use __getitem__ (which we didn't need to override) to retrieve the values. So, we only need to define our custom __iter__ method to make these three views work. You would think the superclass would create these views properly using polymorphism, but if we don't override these three methods, they don't return properly ordered views.
Finally, the __iter__ method is the really special one; it ensures that if we loop over the dictionary's keys (using for...in syntax), it will return the values in the correct order. It does this by returning the __iter__ of the ordered_keys list, which returns the same iterator object that would be used if we used for...in on the list instead. Since ordered_keys is a list of all available keys (due to the way we overrode other methods), this is the correct iterator object for the dictionary as well.
Let's look at a few of these methods in action, compared to a normal dictionary:
>>> ds = DictSorted() >>> d = {} >>> ds['a'] = 1 >>> ds['b'] = 2 >>> ds.setdefault('c', 3) 3 >>> d['a'] = 1 >>> d['b'] = 2 >>> d.setdefault('c', 3) 3 >>> for k,v in ds.items(): ... print(k,v) ... a 1 b 2 c 3 >>> for k,v in d.items(): ... print(k,v) ... a 1 c 3 b 2
Ah, our dictionary is sorted and the normal dictionary is not. Hurray!
Note
If you wanted to use this class in production, you'd have to override several other special methods to ensure the keys are up to date in all cases. However, you don't need to do this; the functionality this class provides is already available in Python, using the OrderedDict object in the collections module. Try importing the class from collections, and use help(OrderedDict) to find out more about it.
Queues
Queues are peculiar data structures because, like sets, their functionality can be handled entirely using lists. However, while lists are extremely versatile general-purpose tools, they are occasionally not the most efficient data structure for container operations. If your program is using a small dataset (up to hundreds or even thousands of elements on today's processors), then lists will probably cover all your use cases. However, if you need to scale your data into the millions, you may need a more efficient container for your particular use case. Python therefore provides three types of queue data structures, depending on what kind of access you are looking for. All three utilize the same API, but differ in both behavior and data structure.
Before we start our queues, however, consider the trusty list data structure. Python lists are the most advantageous data structure for many use cases:
- They support efficient random access to any element in the list
- They have strict ordering of elements
- They support the append operation efficiently
They tend to be slow, however, if you are inserting elements anywhere but the end of the list (especially so if it's the beginning of the list). As we discussed in the section on sets, they are also slow for checking if an element exists in the list, and by extension, searching. Storing data in a sorted order or reordering the data can also be inefficient.
Let's look at the three types of containers provided by the Python queue module.
FIFO queues
FIFO stands for First In First Out and represents the most commonly understood definition of the word "queue". Imagine a line of people standing in line at a bank or cash register. The first person to enter the line gets served first, the second person in line gets served second, and if a new person desires service, they join the end of the line and wait their turn.
The Python Queue class is just like that. It is typically used as a sort of communication medium when one or more objects is producing data and one or more other objects is consuming the data in some way, probably at a different rate. Think of a messaging application that is receiving messages from the network, but can only display one message at a time to the user. The other messages can be buffered in a queue in the order they are received. FIFO queues are utilized a lot in such concurrent applications. (We'll talk more about concurrency in Chapter 12, Testing Object-oriented Programs.)
The Queue class is a good choice when you don't need to access any data inside the data structure except the next object to be consumed. Using a list for this would be less efficient because under the hood, inserting data at (or removing from) the beginning of a list can require shifting every other element in the list.
Queues have a very simple API. A Queue can have "infinite" (until the computer runs out of memory) capacity, but it is more commonly bounded to some maximum size. The primary methods are put() and get(), which add an element to the back of the line, as it were, and retrieve them from the front, in order. Both of these methods accept optional arguments to govern what happens if the operation cannot successfully complete because the queue is either empty (can't get) or full (can't put). The default behavior is to block or idly wait until the Queue object has data or room available to complete the operation. You can have it raise exceptions instead by passing the block=False parameter. Or you can have it wait a defined amount of time before raising an exception by passing a timeout parameter.
The class also has methods to check whether the Queue is full() or empty() and there are a few additional methods to deal with concurrent access that we won't discuss here. Here is a interactive session demonstrating these principles:
>>> from queue import Queue >>> lineup = Queue(maxsize=3) >>> lineup.get(block=False) Traceback (most recent call last): File "<ipython-input-5-a1c8d8492c59>", line 1, in <module> lineup.get(block=False) File "/usr/lib64/python3.3/queue.py", line 164, in get raise Empty queue.Empty >>> lineup.put("one") >>> lineup.put("two") >>> lineup.put("three") >>> lineup.put("four", timeout=1) Traceback (most recent call last): File "<ipython-input-9-4b9db399883d>", line 1, in <module> lineup.put("four", timeout=1) File "/usr/lib64/python3.3/queue.py", line 144, in put raise Full queue.Full >>> lineup.full() True >>> lineup.get() 'one' >>> lineup.get() 'two' >>> lineup.get() 'three' >>> lineup.empty() True
Underneath the hood, Python implements queues on top of the collections.deque data structure. Deques are advanced data structures that permits efficient access to both ends of the collection. It provides a more flexible interface than is exposed by Queue. I refer you to the Python documentation if you'd like to experiment more with it.
LIFO queues
LIFO (Last In First Out) queues are more frequently called stacks. Think of a stack of papers where you can only access the top-most paper. You can put another paper on top of the stack, making it the new top-most paper, or you can take the top-most paper away to reveal the one beneath it.
Traditionally, the operations on stacks are named push and pop, but the Python queue module uses the exact same API as for FIFO queues: put() and get(). However, in a LIFO queue, these methods operate on the "top" of the stack instead of at the front and back of a line. This is an excellent example of polymorphism. If you look at the Queue source code in the Python standard library, you'll actually see that there is a superclass with subclasses for FIFO and LIFO queues that implement the few operations (operating on the top of a stack instead of front and back of a deque instance) that are critically different between the two.
Here's an example of the LIFO queue in action:
>>> from queue import LifoQueue >>> stack = LifoQueue(maxsize=3) >>> stack.put("one") >>> stack.put("two") >>> stack.put("three") >>> stack.put("four", block=False) Traceback (most recent call last): File "<ipython-input-21-5473b359e5a8>", line 1, in <module> stack.put("four", block=False) File "/usr/lib64/python3.3/queue.py", line 133, in put raise Full queue.Full >>> stack.get() 'three' >>> stack.get() 'two' >>> stack.get() 'one' >>> stack.empty() True >>> stack.get(timeout=1) Traceback (most recent call last): File "<ipython-input-26-28e084a84a10>", line 1, in <module> stack.get(timeout=1) File "/usr/lib64/python3.3/queue.py", line 175, in get raise Empty queue.Empty
You might wonder why you couldn't just use the append() and pop() methods on a standard list. Quite frankly, that's probably what I would do. I rarely have occasion to use the LifoQueue class in production code. Working with the end of a list is an efficient operation; so efficient, in fact, that the LifoQueue uses a standard list under the hood!
There are a couple of reasons that you might want to use LifoQueue instead of a list. The most important one is that LifoQueue supports clean concurrent access from multiple threads. If you need stack-like behavior in a concurrent setting, you should leave the list at home. Second, LifoQueue enforces the stack interface. You can't unwittingly insert a value to the wrong position in a LifoQueue, for example (although, as an exercise, you can work out how to do this completely wittingly).
Priority queues
The priority queue enforces a very different style of ordering from the previous queue implementations. Once again, they follow the exact same get() and put() API, but instead of relying on the order that items arrive to determine when they should be returned, the most "important" item is returned. By convention, the most important, or highest priority item is the one that sorts lowest using the less than operator.
A common convention is to store tuples in the priority queue, where the first element in the tuple is the priority for that element, and the second element is the data. Another common paradigm is to implement the __lt__ method, as we discussed earlier in this chapter. It is perfectly acceptable to have multiple elements with the same priority in the queue, although there are no guarantees on which one will be returned first.
A priority queue might be used, for example, by a search engine to ensure it refreshes the content of the most popular web pages before crawling sites that are less likely to be searched for. A product recommendation tool might use one to display information about the most highly ranked products while still loading data for the lower ranks.
Note that a priority queue will always return the most important element currently in the queue. The get() method will block (by default) if the queue is empty, but it will not block and wait for a higher priority element to be added if there is already something in the queue. The queue knows nothing about elements that have not been added yet (or even about elements that have been previously extracted), and only makes decisions based on the current contents of the queue.
This interactive session shows a priority queue in action, using tuples as weights to determine what order items are processed in:
>>> heap.put((3, "three")) >>> heap.put((4, "four")) >>> heap.put((1, "one") ) >>> heap.put((2, "two")) >>> heap.put((5, "five"), block=False) Traceback (most recent call last): File "<ipython-input-23-d4209db364ed>", line 1, in <module> heap.put((5, "five"), block=False) File "/usr/lib64/python3.3/queue.py", line 133, in put raise Full Full >>> while not heap.empty(): print(heap.get()) (1, 'one') (2, 'two') (3, 'three') (4, 'four')
Priority queues are almost universally implemented using the heap data structure. Python's implementation utilizes the heapq module to effectively store a heap inside a normal list. I direct you to an algorithm and data-structure's textbook for more information on heaps, not to mention many other fascinating structures we haven't covered here. No matter what the data structure, you can use object-oriented principles to wrap relevant algorithms (behaviors), such as those supplied in the heapq module, around the data they are structuring in the computer's memory, just as the queue module has done on our behalf in the standard library.
FIFO queues
FIFO stands for First In First Out and represents the most commonly understood definition of the word "queue". Imagine a line of people standing in line at a bank or cash register. The first person to enter the line gets served first, the second person in line gets served second, and if a new person desires service, they join the end of the line and wait their turn.
The Python Queue class is just like that. It is typically used as a sort of communication medium when one or more objects is producing data and one or more other objects is consuming the data in some way, probably at a different rate. Think of a messaging application that is receiving messages from the network, but can only display one message at a time to the user. The other messages can be buffered in a queue in the order they are received. FIFO queues are utilized a lot in such concurrent applications. (We'll talk more about concurrency in Chapter 12, Testing Object-oriented Programs.)
The Queue class is a good choice when you don't need to access any data inside the data structure except the next object to be consumed. Using a list for this would be less efficient because under the hood, inserting data at (or removing from) the beginning of a list can require shifting every other element in the list.
Queues have a very simple API. A Queue can have "infinite" (until the computer runs out of memory) capacity, but it is more commonly bounded to some maximum size. The primary methods are put() and get(), which add an element to the back of the line, as it were, and retrieve them from the front, in order. Both of these methods accept optional arguments to govern what happens if the operation cannot successfully complete because the queue is either empty (can't get) or full (can't put). The default behavior is to block or idly wait until the Queue object has data or room available to complete the operation. You can have it raise exceptions instead by passing the block=False parameter. Or you can have it wait a defined amount of time before raising an exception by passing a timeout parameter.
The class also has methods to check whether the Queue is full() or empty() and there are a few additional methods to deal with concurrent access that we won't discuss here. Here is a interactive session demonstrating these principles:
>>> from queue import Queue >>> lineup = Queue(maxsize=3) >>> lineup.get(block=False) Traceback (most recent call last): File "<ipython-input-5-a1c8d8492c59>", line 1, in <module> lineup.get(block=False) File "/usr/lib64/python3.3/queue.py", line 164, in get raise Empty queue.Empty >>> lineup.put("one") >>> lineup.put("two") >>> lineup.put("three") >>> lineup.put("four", timeout=1) Traceback (most recent call last): File "<ipython-input-9-4b9db399883d>", line 1, in <module> lineup.put("four", timeout=1) File "/usr/lib64/python3.3/queue.py", line 144, in put raise Full queue.Full >>> lineup.full() True >>> lineup.get() 'one' >>> lineup.get() 'two' >>> lineup.get() 'three' >>> lineup.empty() True
Underneath the hood, Python implements queues on top of the collections.deque data structure. Deques are advanced data structures that permits efficient access to both ends of the collection. It provides a more flexible interface than is exposed by Queue. I refer you to the Python documentation if you'd like to experiment more with it.
LIFO queues
LIFO (Last In First Out) queues are more frequently called stacks. Think of a stack of papers where you can only access the top-most paper. You can put another paper on top of the stack, making it the new top-most paper, or you can take the top-most paper away to reveal the one beneath it.
Traditionally, the operations on stacks are named push and pop, but the Python queue module uses the exact same API as for FIFO queues: put() and get(). However, in a LIFO queue, these methods operate on the "top" of the stack instead of at the front and back of a line. This is an excellent example of polymorphism. If you look at the Queue source code in the Python standard library, you'll actually see that there is a superclass with subclasses for FIFO and LIFO queues that implement the few operations (operating on the top of a stack instead of front and back of a deque instance) that are critically different between the two.
Here's an example of the LIFO queue in action:
>>> from queue import LifoQueue >>> stack = LifoQueue(maxsize=3) >>> stack.put("one") >>> stack.put("two") >>> stack.put("three") >>> stack.put("four", block=False) Traceback (most recent call last): File "<ipython-input-21-5473b359e5a8>", line 1, in <module> stack.put("four", block=False) File "/usr/lib64/python3.3/queue.py", line 133, in put raise Full queue.Full >>> stack.get() 'three' >>> stack.get() 'two' >>> stack.get() 'one' >>> stack.empty() True >>> stack.get(timeout=1) Traceback (most recent call last): File "<ipython-input-26-28e084a84a10>", line 1, in <module> stack.get(timeout=1) File "/usr/lib64/python3.3/queue.py", line 175, in get raise Empty queue.Empty
You might wonder why you couldn't just use the append() and pop() methods on a standard list. Quite frankly, that's probably what I would do. I rarely have occasion to use the LifoQueue class in production code. Working with the end of a list is an efficient operation; so efficient, in fact, that the LifoQueue uses a standard list under the hood!
There are a couple of reasons that you might want to use LifoQueue instead of a list. The most important one is that LifoQueue supports clean concurrent access from multiple threads. If you need stack-like behavior in a concurrent setting, you should leave the list at home. Second, LifoQueue enforces the stack interface. You can't unwittingly insert a value to the wrong position in a LifoQueue, for example (although, as an exercise, you can work out how to do this completely wittingly).
Priority queues
The priority queue enforces a very different style of ordering from the previous queue implementations. Once again, they follow the exact same get() and put() API, but instead of relying on the order that items arrive to determine when they should be returned, the most "important" item is returned. By convention, the most important, or highest priority item is the one that sorts lowest using the less than operator.
A common convention is to store tuples in the priority queue, where the first element in the tuple is the priority for that element, and the second element is the data. Another common paradigm is to implement the __lt__ method, as we discussed earlier in this chapter. It is perfectly acceptable to have multiple elements with the same priority in the queue, although there are no guarantees on which one will be returned first.
A priority queue might be used, for example, by a search engine to ensure it refreshes the content of the most popular web pages before crawling sites that are less likely to be searched for. A product recommendation tool might use one to display information about the most highly ranked products while still loading data for the lower ranks.
Note that a priority queue will always return the most important element currently in the queue. The get() method will block (by default) if the queue is empty, but it will not block and wait for a higher priority element to be added if there is already something in the queue. The queue knows nothing about elements that have not been added yet (or even about elements that have been previously extracted), and only makes decisions based on the current contents of the queue.
This interactive session shows a priority queue in action, using tuples as weights to determine what order items are processed in:
>>> heap.put((3, "three")) >>> heap.put((4, "four")) >>> heap.put((1, "one") ) >>> heap.put((2, "two")) >>> heap.put((5, "five"), block=False) Traceback (most recent call last): File "<ipython-input-23-d4209db364ed>", line 1, in <module> heap.put((5, "five"), block=False) File "/usr/lib64/python3.3/queue.py", line 133, in put raise Full Full >>> while not heap.empty(): print(heap.get()) (1, 'one') (2, 'two') (3, 'three') (4, 'four')
Priority queues are almost universally implemented using the heap data structure. Python's implementation utilizes the heapq module to effectively store a heap inside a normal list. I direct you to an algorithm and data-structure's textbook for more information on heaps, not to mention many other fascinating structures we haven't covered here. No matter what the data structure, you can use object-oriented principles to wrap relevant algorithms (behaviors), such as those supplied in the heapq module, around the data they are structuring in the computer's memory, just as the queue module has done on our behalf in the standard library.
LIFO queues
LIFO (Last In First Out) queues are more frequently called stacks. Think of a stack of papers where you can only access the top-most paper. You can put another paper on top of the stack, making it the new top-most paper, or you can take the top-most paper away to reveal the one beneath it.
Traditionally, the operations on stacks are named push and pop, but the Python queue module uses the exact same API as for FIFO queues: put() and get(). However, in a LIFO queue, these methods operate on the "top" of the stack instead of at the front and back of a line. This is an excellent example of polymorphism. If you look at the Queue source code in the Python standard library, you'll actually see that there is a superclass with subclasses for FIFO and LIFO queues that implement the few operations (operating on the top of a stack instead of front and back of a deque instance) that are critically different between the two.
Here's an example of the LIFO queue in action:
>>> from queue import LifoQueue >>> stack = LifoQueue(maxsize=3) >>> stack.put("one") >>> stack.put("two") >>> stack.put("three") >>> stack.put("four", block=False) Traceback (most recent call last): File "<ipython-input-21-5473b359e5a8>", line 1, in <module> stack.put("four", block=False) File "/usr/lib64/python3.3/queue.py", line 133, in put raise Full queue.Full >>> stack.get() 'three' >>> stack.get() 'two' >>> stack.get() 'one' >>> stack.empty() True >>> stack.get(timeout=1) Traceback (most recent call last): File "<ipython-input-26-28e084a84a10>", line 1, in <module> stack.get(timeout=1) File "/usr/lib64/python3.3/queue.py", line 175, in get raise Empty queue.Empty
You might wonder why you couldn't just use the append() and pop() methods on a standard list. Quite frankly, that's probably what I would do. I rarely have occasion to use the LifoQueue class in production code. Working with the end of a list is an efficient operation; so efficient, in fact, that the LifoQueue uses a standard list under the hood!
There are a couple of reasons that you might want to use LifoQueue instead of a list. The most important one is that LifoQueue supports clean concurrent access from multiple threads. If you need stack-like behavior in a concurrent setting, you should leave the list at home. Second, LifoQueue enforces the stack interface. You can't unwittingly insert a value to the wrong position in a LifoQueue, for example (although, as an exercise, you can work out how to do this completely wittingly).
Priority queues
The priority queue enforces a very different style of ordering from the previous queue implementations. Once again, they follow the exact same get() and put() API, but instead of relying on the order that items arrive to determine when they should be returned, the most "important" item is returned. By convention, the most important, or highest priority item is the one that sorts lowest using the less than operator.
A common convention is to store tuples in the priority queue, where the first element in the tuple is the priority for that element, and the second element is the data. Another common paradigm is to implement the __lt__ method, as we discussed earlier in this chapter. It is perfectly acceptable to have multiple elements with the same priority in the queue, although there are no guarantees on which one will be returned first.
A priority queue might be used, for example, by a search engine to ensure it refreshes the content of the most popular web pages before crawling sites that are less likely to be searched for. A product recommendation tool might use one to display information about the most highly ranked products while still loading data for the lower ranks.
Note that a priority queue will always return the most important element currently in the queue. The get() method will block (by default) if the queue is empty, but it will not block and wait for a higher priority element to be added if there is already something in the queue. The queue knows nothing about elements that have not been added yet (or even about elements that have been previously extracted), and only makes decisions based on the current contents of the queue.
This interactive session shows a priority queue in action, using tuples as weights to determine what order items are processed in:
>>> heap.put((3, "three")) >>> heap.put((4, "four")) >>> heap.put((1, "one") ) >>> heap.put((2, "two")) >>> heap.put((5, "five"), block=False) Traceback (most recent call last): File "<ipython-input-23-d4209db364ed>", line 1, in <module> heap.put((5, "five"), block=False) File "/usr/lib64/python3.3/queue.py", line 133, in put raise Full Full >>> while not heap.empty(): print(heap.get()) (1, 'one') (2, 'two') (3, 'three') (4, 'four')
Priority queues are almost universally implemented using the heap data structure. Python's implementation utilizes the heapq module to effectively store a heap inside a normal list. I direct you to an algorithm and data-structure's textbook for more information on heaps, not to mention many other fascinating structures we haven't covered here. No matter what the data structure, you can use object-oriented principles to wrap relevant algorithms (behaviors), such as those supplied in the heapq module, around the data they are structuring in the computer's memory, just as the queue module has done on our behalf in the standard library.
Priority queues
The priority queue enforces a very different style of ordering from the previous queue implementations. Once again, they follow the exact same get() and put() API, but instead of relying on the order that items arrive to determine when they should be returned, the most "important" item is returned. By convention, the most important, or highest priority item is the one that sorts lowest using the less than operator.
A common convention is to store tuples in the priority queue, where the first element in the tuple is the priority for that element, and the second element is the data. Another common paradigm is to implement the __lt__ method, as we discussed earlier in this chapter. It is perfectly acceptable to have multiple elements with the same priority in the queue, although there are no guarantees on which one will be returned first.
A priority queue might be used, for example, by a search engine to ensure it refreshes the content of the most popular web pages before crawling sites that are less likely to be searched for. A product recommendation tool might use one to display information about the most highly ranked products while still loading data for the lower ranks.
Note that a priority queue will always return the most important element currently in the queue. The get() method will block (by default) if the queue is empty, but it will not block and wait for a higher priority element to be added if there is already something in the queue. The queue knows nothing about elements that have not been added yet (or even about elements that have been previously extracted), and only makes decisions based on the current contents of the queue.
This interactive session shows a priority queue in action, using tuples as weights to determine what order items are processed in:
>>> heap.put((3, "three")) >>> heap.put((4, "four")) >>> heap.put((1, "one") ) >>> heap.put((2, "two")) >>> heap.put((5, "five"), block=False) Traceback (most recent call last): File "<ipython-input-23-d4209db364ed>", line 1, in <module> heap.put((5, "five"), block=False) File "/usr/lib64/python3.3/queue.py", line 133, in put raise Full Full >>> while not heap.empty(): print(heap.get()) (1, 'one') (2, 'two') (3, 'three') (4, 'four')
Priority queues are almost universally implemented using the heap data structure. Python's implementation utilizes the heapq module to effectively store a heap inside a normal list. I direct you to an algorithm and data-structure's textbook for more information on heaps, not to mention many other fascinating structures we haven't covered here. No matter what the data structure, you can use object-oriented principles to wrap relevant algorithms (behaviors), such as those supplied in the heapq module, around the data they are structuring in the computer's memory, just as the queue module has done on our behalf in the standard library.
Case study
To tie everything together, we'll be writing a simple link collector, which will visit a website and collect every link on every page it finds in that site. Before we start, though, we'll need some test data to work with. Simply write some HTML files to work with that contain links to each other and to other sites on the Internet, something like this:
<html>
<body>
<a href="contact.html">Contact us</a>
<a href="blog.html">Blog</a>
<a href="esme.html">My Dog</a>
<a href="/hobbies.html">Some hobbies</a>
<a href="/contact.html">Contact AGAIN</a>
<a href="http://www.archlinux.org/">Favorite OS</a>
</body>
</html>Name one of the files index.html so it shows up first when pages are served. Make sure the other files exist, and keep things complicated so there is lots of linking between them. The examples for this chapter include a directory called case_study_serve (one of the lamest personal websites in existence!) if you would rather not set them up yourself.
Now, start a simple web server by entering the directory containing all these files and run the following command:
python3 -m http.server
This will start a server running on port 8000; you can see the pages you made by visiting http://localhost:8000/ in your web browser.
Note
I doubt anyone can get a website up and running with less work! Never let it be said, "you can't do that easily with Python."
The goal will be to pass our collector the base URL for the site (in this case: http://localhost:8000/), and have it create a list containing every unique link on the site. We'll need to take into account three types of URLs (links to external sites, which start with http://, absolute internal links, which start with a / character, and relative links, for everything else). We also need to be aware that pages may link to each other in a loop; we need to be sure we don't process the same page multiple times, or it may never end. With all this uniqueness going on, it sounds like we're going to need some sets.
Before we get into that, let's start with the basics. What code do we need to connect to a page and parse all the links from that page?
from urllib.request import urlopen
from urllib.parse import urlparse
import re
import sys
LINK_REGEX = re.compile(
"<a [^>]*href=['\"]([^'\"]+)['\"][^>]*>")
class LinkCollector:
def __init__(self, url):
self.url = "" + urlparse(url).netloc
def collect_links(self, path="/"):
full_url = self.url + path
page = str(urlopen(full_url).read())
links = LINK_REGEX.findall(page)
print(links)
if __name__ == "__main__":
LinkCollector(sys.argv[1]).collect_links()This is a short piece of code, considering what it's doing. It connects to the server in the argument passed on the command line, downloads the page, and extracts all the links on that page. The __init__ method uses the urlparse function to extract just the hostname from the URL; so even if we pass in http://localhost:8000/some/page.html, it will still operate on the top level of the host http://localhost:8000/. This makes sense, because we want to collect all the links on the site, although it assumes every page is connected to the index by some sequence of links.
The collect_links method connects to and downloads the specified page from the server, and uses a regular expression to find all the links in the page. Regular expressions are an extremely powerful string processing tool. Unfortunately, they have a steep learning curve; if you haven't used them before, I strongly recommend studying any of the entire books or websites on the topic. If you don't think they're worth knowing, try writing the preceding code without them and you'll change your mind.
The example also stops in the middle of the collect_links method to print the value of links. This is a common way to test a program as we're writing it: stop and output the value to ensure it is the value we expect. Here's what it outputs for our example:
['contact.html', 'blog.html', 'esme.html', '/hobbies.html', '/contact.html', 'http://www.archlinux.org/']
So now we have a collection of all the links in the first page. What can we do with it? We can't just pop the links into a set to remove duplicates because links may be relative or absolute. For example, contact.html and /contact.html point to the same page. So the first thing we should do is normalize all the links to their full URL, including hostname and relative path. We can do this by adding a normalize_url method to our object:
def normalize_url(self, path, link):
if link.startswith("http://"):
return link
elif link.startswith("/"):
return self.url + link
else:
return self.url + path.rpartition(
'/')[0] + '/' + linkThis method converts each URL to a complete address that includes protocol and hostname. Now the two contact pages have the same value and we can store them in a set. We'll have to modify __init__ to create the set, and collect_links to put all the links into it.
Then, we'll have to visit all the non-external links and collect them too. But wait a minute; if we do this, how do we keep from revisiting a link when we encounter the same page twice? It looks like we're actually going to need two sets: a set of collected links, and a set of visited links. This suggests that we were wise to choose a set to represent our data; we know that sets are most useful when we're manipulating more than one of them. Let's set these up:
class LinkCollector:
def __init__(self, url):
self.url = "http://+" + urlparse(url).netloc
self.collected_links = set()
self.visited_links = set()
def collect_links(self, path="/"):
full_url = self.url + path
self.visited_links.add(full_url)
page = str(urlopen(full_url).read())
links = LINK_REGEX.findall(page)
links = {self.normalize_url(path, link
) for link in links}
self.collected_links = links.union(
self.collected_links)
unvisited_links = links.difference(
self.visited_links)
print(links, self.visited_links,
self.collected_links, unvisited_links)
The line that creates the normalized list of links uses a set comprehension, no different from a list comprehension, except that the result is a set of values. We'll be covering these in detail in the next chapter. Once again, the method stops to print out the current values, so we can verify that we don't have our sets confused, and that difference really was the method we wanted to call to collect unvisited_links. We can then add a few lines of code that loop over all the unvisited links and add them to the collection as well:
for link in unvisited_links:
if link.startswith(self.url):
self.collect_links(urlparse(link).path)The if statement ensures that we are only collecting links from the one website; we don't want to go off and collect all the links from all the pages on the Internet (unless we're Google or the Internet Archive!). If we modify the main code at the bottom of the program to output the collected links, we can see it seems to have collected them all:
if __name__ == "__main__":
collector = LinkCollector(sys.argv[1])
collector.collect_links()
for link in collector.collected_links:
print(link)It displays all the links we've collected, and only once, even though many of the pages in my example linked to each other multiple times:
$ python3 link_collector.py http://localhost:8000 http://localhost:8000/ http://en.wikipedia.org/wiki/Cavalier_King_Charles_Spaniel http://beluminousyoga.com http://archlinux.me/dusty/ http://localhost:8000/blog.html http://ccphillips.net/ http://localhost:8000/contact.html http://localhost:8000/taichi.html http://www.archlinux.org/ http://localhost:8000/esme.html http://localhost:8000/hobbies.html
Even though it collected links to external pages, it didn't go off collecting links from any of the external pages we linked to. This is a great little program if we want to collect all the links in a site. But it doesn't give me all the information I might need to build a site map; it tells me which pages I have, but it doesn't tell me which pages link to other pages. If we want to do that instead, we're going to have to make some modifications.
The first thing we should do is look at our data structures. The set of collected links doesn't work anymore; we want to know which links were linked to from which pages. The first thing we could do, then, is turn that set into a dictionary of sets for each page we visit. The dictionary keys will represent the exact same data that is currently in the set. The values will be sets of all the links on that page. Here are the changes:
from urllib.request import urlopen
from urllib.parse import urlparse
import re
import sys
LINK_REGEX = re.compile(
"<a [^>]*href=['\"]([^'\"]+)['\"][^>]*>")
class LinkCollector:
def __init__(self, url):
self.url = "http://%s" % urlparse(url).netloc
self.collected_links = {}
self.visited_links = set()
def collect_links(self, path="/"):
full_url = self.url + path
self.visited_links.add(full_url)
page = str(urlopen(full_url).read())
links = LINK_REGEX.findall(page)
links = {self.normalize_url(path, link
) for link in links}
self.collected_links[full_url] = links
for link in links:
self.collected_links.setdefault(link, set())
unvisited_links = links.difference(
self.visited_links)
for link in unvisited_links:
if link.startswith(self.url):
self.collect_links(urlparse(link).path)
def normalize_url(self, path, link):
if link.startswith("http://"):
return link
elif link.startswith("/"):
return self.url + link
else:
return self.url + path.rpartition('/'
)[0] + '/' + link
if __name__ == "__main__":
collector = LinkCollector(sys.argv[1])
collector.collect_links()
for link, item in collector.collected_links.items():
print("{}: {}".format(link, item))
It is a surprisingly small change; the line that originally created a union of two sets has been replaced with three lines that update the dictionary. The first of these simply tells the dictionary what the collected links for that page are. The second creates an empty set for any items in the dictionary that have not already been added to the dictionary, using setdefault. The result is a dictionary that contains all the links as its keys, mapped to sets of links for all the internal links, and empty sets for the external links.
Finally, instead of recursively calling collect_links, we can use a queue to store the links that haven't been processed yet. This implementation won't support it, but this would be a good first step to creating a multithreaded version that makes multiple requests in parallel to save time.
from urllib.request import urlopen
from urllib.parse import urlparse
import re
import sys
from queue import Queue
LINK_REGEX = re.compile("<a [^>]*href=['\"]([^'\"]+)['\"][^>]*>")
class LinkCollector:
def __init__(self, url):
self.url = "http://%s" % urlparse(url).netloc
self.collected_links = {}
self.visited_links = set()
def collect_links(self):
queue = Queue()
queue.put(self.url)
while not queue.empty():
url = queue.get().rstrip('/')
self.visited_links.add(url)
page = str(urlopen(url).read())
links = LINK_REGEX.findall(page)
links = {
self.normalize_url(urlparse(url).path, link)
for link in links
}
self.collected_links[url] = links
for link in links:
self.collected_links.setdefault(link, set())
unvisited_links = links.difference(self.visited_links)
for link in unvisited_links:
if link.startswith(self.url):
queue.put(link)
def normalize_url(self, path, link):
if link.startswith("http://"):
return link.rstrip('/')
elif link.startswith("/"):
return self.url + link.rstrip('/')
else:
return self.url + path.rpartition('/')[0] + '/' + link.rstrip('/')
if __name__ == "__main__":
collector = LinkCollector(sys.argv[1])
collector.collect_links()
for link, item in collector.collected_links.items():
print("%s: %s" % (link, item))I had to manually strip any trailing forward slashes in the normalize_url method to remove duplicates in this version of the code.
Because the end result is an unsorted dictionary, there is no restriction on what order the links should be processed in. Therefore, we could just as easily have used a LifoQueue instead of a Queue here. A priority queue probably wouldn't make a lot of sense since there is no obvious priority to attach to a link in this case.
Exercises
The best way to learn how to choose the correct data structure is to do it wrong a few times. Take some code you've recently written, or write some new code that uses a list. Try rewriting it using some different data structures. Which ones make more sense? Which ones don't? Which have the most elegant code?
Try this with a few different pairs of data structures. You can look at examples you've done for previous chapter exercises. Are there objects with methods where you could have used namedtuple or dict instead? Attempt both and see. Are there dictionaries that could have been sets because you don't really access the values? Do you have lists that check for duplicates? Would a set suffice? Or maybe several sets? Would one of the queue implementations be more efficient? Is it useful to restrict the API to the top of a stack rather than allowing random access to the list?
If you want some specific examples to work with, try adapting the link collector to also save the title used for each link. Perhaps you can generate a site map in HTML that lists all the pages on the site, and contains a list of links to other pages, named with the same link titles.
Have you written any container objects recently that you could improve by inheriting a built-in and overriding some of the "special" double-underscore methods? You may have to do some research (using dir and help, or the Python library reference) to find out which methods need overriding. Are you sure inheritance is the correct tool to apply; could a composition-based solution be more effective? Try both (if it's possible) before you decide. Try to find different situations where each method is better than the other.
If you were familiar with the various Python data structures and their uses before you started this chapter, you may have been bored. But if that is the case, there's a good chance you use data structures too much! Look at some of your old code and rewrite it to use more self-made objects. Carefully consider the alternatives and try them all out; which one makes for the most readable and maintainable system?
Always critically evaluate your code and design decisions. Make a habit of reviewing old code and take note if your understanding of "good design" has changed since you've written it. Software design has a large aesthetic component, and like artists with oil on canvas, we all have to find the style that suits us best.
Summary
We've covered several built-in data structures and attempted to understand how to choose one for specific applications. Sometimes, the best thing we can do is create a new class of objects, but often, one of the built-ins provides exactly what we need. When it doesn't, we can always use inheritance or composition to adapt them to our use cases. We can even override special methods to completely change the behavior of built-in syntaxes.
In the next chapter, we'll discuss how to integrate the object-oriented and not-so-object-oriented aspects of Python. Along the way, we'll discover that it's more object-oriented than it looks at first sight!