A deque is an alternative implementation for lists. While a list is based on arrays, a deque is based on a doubly linked list. Hence, a deque is much faster when you need to insert something into its middle or head but much slower when you need to access an arbitrary index.

Of course, thanks to the overallocation of an internal array in the Python list type, not every list.append() call requires memory reallocation, and the average complexity of this method is O(1). Still, pops and appends are generally faster when performed on linked lists instead of arrays. The situation changes dramatically when the element needs to be added on arbitrary point of sequence. Because all elements on the right of the new one need to be shifted in an array, the complexity of list.insert() is O(n). If you need to perform a lot of pops, appends, and inserts, the deque in place of the list may provide substantial performance improvement. But always be sure to profile your code before switching from a list to the deque, because a few things that are fast in arrays (such as accessing arbitrary index) are extremely inefficient in linked lists.

For example, if we measure the time of appending one element and removing it from the sequence with timeit, the difference between list and deque may not even be noticeable:

$ python3 -m timeit 
> -s 'sequence=list(range(10))' 
> 'sequence.append(0); sequence.pop();'
1000000 loops, best of 3: 0.168 usec per loop

$ python3 -m timeit  
> -s 'from collections import deque; sequence=deque(range(10))' 
> 'sequence.append(0); sequence.pop();'
1000000 loops, best of 3: 0.168 usec per loop

But if we do similar comparison for situations when we want to add and remove the first element of the sequence, the performance difference is impressive:

$ python3 -m timeit 
> -s 'sequence=list(range(10))' 
> 'sequence.insert(0, 0); sequence.pop(0)'

1000000 loops, best of 3: 0.392 usec per loop
$ python3 -m timeit 
> -s 'from collections import deque; sequence=deque(range(10))' 
> 'sequence.appendleft(0); sequence.popleft()'
10000000 loops, best of 3: 0.172 usec per loop

And the difference is, it gets bigger when the size of the sequence grows. Here is an example of the same test performed on lists containing 10,000 elements:

$ python3 -m timeit 
> -s 'sequence=list(range(10000))' 
> 'sequence.insert(0, 0); sequence.pop(0)'
100000 loops, best of 3: 14 usec per loop
$ python3 -m timeit 
> -s 'from collections import deque; sequence=deque(range(10000))'  
> 'sequence.appendleft(0); sequence.popleft()'
10000000 loops, best of 3: 0.168 usec per loop

Thanks to efficient append() and pop() methods that work at the same speed from both ends of the sequence, deque makes a perfect type for implementing queues. For example, a FIFO (First In First Out) queue will definitely be much more efficient if implemented with a deque instead of list.

The defaultdict type is similar to the dict type but adds a default factory for new keys. This avoids writing an extra test to initialize the mapping entry and is more efficient than the dict.setdefault method.

defaultdict seems just like syntactic sugar over dict that simply allows you to write shorter code. In fact, the fallback to a predefined value on a failed key lookup is also slightly faster than the dict.setdefault() method:

$ python3 -m timeit 
> -s 'd = {}' 
> 'd.setdefault("x", None)'
10000000 loops, best of 3: 0.153 usec per loop
$ python3 -m timeit  
> -s 'from collections import defaultdict; d=defaultdict(lambda: None)' 
> 'd["x"]'
10000000 loops, best of 3: 0.0447 usec per loop

The difference isn't great because the computational complexity hasn't changed. The dict.setdefault method consist of two steps (key lookup and key set), both of which have a complexity of O(1), as we have seen in the Dictionaries section in Chapter 2, Syntax Best Practices – below the Class Level. There is no way to have a complexity class lower than O(1). But it is indisputably faster in some situations and it is worth knowing because every small speed improvement counts when optimizing critical code sections.

The defaultdict type takes a factory as a parameter and can therefore be used with built-in types or classes whose constructor does not take arguments. Here is an example from the official documentation that shows how to use defaultdict for counting:

>>> s = 'mississippi'
>>> d = defaultdict(int)
>>> for k in s:
...     d[k] += 1
...
>>> list(d.items())
[('i', 4), ('p', 2), ('s', 4), ('m', 1)]

namedtuple is a class factory that takes a type name and a list of attributes and creates a class out of it. The class can then be used to instantiate a tuple-like object and provide accessors for its elements:

>>> from collections import namedtuple 
>>> Customer = namedtuple(
...     'Customer',
...     'firstname lastname'
... )
>>> c = Customer('Tarek', 'Ziadé')
>>> c.firstname
'Tarek'

It can be used to create records that are easier to write compared to a custom class that would require some boilerplate code to initialize values. On the other hand, it is based on tuple, so access to its elements by index is very fast. The generated class can be subclassed to add more operations.

The gain from using namedtuple instead of other datatypes may not be obvious at first. The main advantage is that it is way more easier to use, understand, and interpret than ordinary tuples. Tuple indexes don't carry any semantics, so it is great to access tuple elements by attributes too. However, you could get the same benefit from dictionaries that have an O(1) average complexity of get/set operations.

The first advantage in terms of performance is that namedtuple is still the flavor of tuple. It means that it is immutable, so the underlying array storage is allocated exactly for the needed size. Dictionaries, on the other hand, need to use overallocation of the internal hash table to ensure low average complexity of get/set operations. So, namedtuple wins over dict in terms of memory efficiency.

The fact that namedtuple is based on a tuple may also be beneficial for performance. Its elements may be accessed by an integer index, like in two other simple sequence objects—lists and tuples. This operation is both simple and fast. In the case of dict or custom class instances (that also use dictionaries for storing attributes), the element access requires hash table lookup. It is highly optimized to ensure good performance independently from collection size, but the mentioned O(1) complexity is actually only the average complexity. The actual, amortized worst case complexity for set/get operations in dict is O(n). The real amount of work when performing such an operation at a given moment is dependent on both collection size and its history. So, in sections of code that are critical for performance, sometimes it may be wise to use lists or tuples instead of dictionaries. This is only because they are more predictable when it comes to performance.

In such a situation, namedtuple is a great type that combines the advantages of dictionaries and tuples: