dict: Your Go-to Dictionary

Because dictionaries are so important, Python features a robust dictionary implementation that’s built directly into the core language: thedict data type.

Python also provides some usefulsyntactic sugar for working with dictionaries in your programs. For example, the curly-brace ({ }) dictionary expression syntax anddictionary comprehensions allow you to conveniently define new dictionary objects:

>>>phonebook={..."bob":7387,..."alice":3719,..."jack":7052,...}>>>squares={x:x*xforxinrange(6)}>>>phonebook["alice"]3719>>>squares{0: 0, 1: 1, 2: 4, 3: 9, 4: 16, 5: 25}

There are some restrictions on which objects can be used as valid keys.

Python’s dictionaries are indexed by keys that can be of anyhashable type. Ahashable object has a hash value that never changes during its lifetime (see__hash__), and it can be compared to other objects (see__eq__). Hashable objects that compare as equal must have the same hash value.

Immutable types likestrings andnumbers are hashable and work well as dictionary keys. You can also usetuple objects as dictionary keys as long as they contain only hashable types themselves.

For most use cases, Python’s built-in dictionary implementation will do everything you need. Dictionaries are highly optimized and underlie many parts of the language. For example,class attributes and variables in astack frame are both stored internally in dictionaries.

Python dictionaries are based on a well-tested and finely tunedhash table implementation that provides the performance characteristics you’d expect:O(1) time complexity for lookup, insert, update, and delete operations in the average case.

There’s little reason not to use the standarddict implementation included with Python. However, specialized third-party dictionary implementations exist, such asskip lists orB-tree–based dictionaries.

Besides plaindict objects, Python’s standard library also includes a number of specialized dictionary implementations. These specialized dictionaries are all based on the built-in dictionary class (and share its performance characteristics) but also include some additional convenience features.

Let’s take a look at them.

collections.OrderedDict: Remember the Insertion Order of Keys

Python includes a specializeddict subclass that remembers the insertion order of keys added to it:collections.OrderedDict.

While standarddict instances preserve the insertion order of keys in CPython 3.6 and above, this was simply aside effect of the CPython implementation and was not defined in the language spec until Python 3.7. So, if key order is important for your algorithm to work, then it’s best to communicate this clearly by explicitly using theOrderedDict class:

>>>importcollections>>>d=collections.OrderedDict(one=1,two=2,three=3)>>>dOrderedDict([('one', 1), ('two', 2), ('three', 3)])>>>d["four"]=4>>>dOrderedDict([('one', 1), ('two', 2),             ('three', 3), ('four', 4)])>>>d.keys()odict_keys(['one', 'two', 'three', 'four'])

UntilPython 3.8, you couldn’t iterate over dictionary items in reverse order usingreversed(). OnlyOrderedDict instances offered that functionality. Even in Python 3.8,dict andOrderedDict objects aren’t exactly the same.OrderedDict instances have a.move_to_end() method that is unavailable on plaindict instance, as well as a more customizable.popitem() method than the one plaindict instances.

collections.defaultdict: Return Default Values for Missing Keys

Thedefaultdict class is another dictionary subclass that accepts a callable in its constructor whose return value will be used if a requested key cannot be found.

This can save you some typing and make your intentions clearer as compared to usingget() or catching aKeyError exception in regular dictionaries:

>>>fromcollectionsimportdefaultdict>>>dd=defaultdict(list)>>># Accessing a missing key creates it and>>># initializes it using the default factory,>>># i.e. list() in this example:>>>dd["dogs"].append("Rufus")>>>dd["dogs"].append("Kathrin")>>>dd["dogs"].append("Mr Sniffles")>>>dd["dogs"]['Rufus', 'Kathrin', 'Mr Sniffles']

collections.ChainMap: Search Multiple Dictionaries as a Single Mapping

Thecollections.ChainMap data structure groups multiple dictionaries into a single mapping. Lookups search the underlying mappings one by one until a key is found. Insertions, updates, and deletions only affect the first mapping added to the chain:

>>>fromcollectionsimportChainMap>>>dict1={"one":1,"two":2}>>>dict2={"three":3,"four":4}>>>chain=ChainMap(dict1,dict2)>>>chainChainMap({'one': 1, 'two': 2}, {'three': 3, 'four': 4})>>># ChainMap searches each collection in the chain>>># from left to right until it finds the key (or fails):>>>chain["three"]3>>>chain["one"]1>>>chain["missing"]Traceback (most recent call last):  File"<stdin>", line1, in<module>KeyError:'missing'

types.MappingProxyType: A Wrapper for Making Read-Only Dictionaries

MappingProxyType is a wrapper around a standard dictionary that provides a read-only view into the wrapped dictionary’s data. This class was added in Python 3.3 and can be used to create immutable proxy versions of dictionaries.

MappingProxyType can be helpful if, for example, you’d like to return a dictionary carrying internal state from a class or module while discouraging write access to this object. UsingMappingProxyType allows you to put these restrictions in place without first having to create a full copy of the dictionary:

>>>fromtypesimportMappingProxyType>>>writable={"one":1,"two":2}>>>read_only=MappingProxyType(writable)>>># The proxy is read-only:>>>read_only["one"]1>>>read_only["one"]=23Traceback (most recent call last):  File"<stdin>", line1, in<module>TypeError:'mappingproxy' object does not support item assignment>>># Updates to the original are reflected in the proxy:>>>writable["one"]=42>>>read_onlymappingproxy({'one': 42, 'two': 2})

Dictionaries in Python: Summary

All the Python dictionary implementations listed in this tutorial are valid implementations that are built into the Python standard library.

If you’re looking for a general recommendation on which mapping type to use in your programs, I’d point you to the built-indict data type. It’s a versatile and optimized hash table implementation that’s built directly into the core language.

I would recommend that you use one of the other data types listed here only if you have special requirements that go beyond what’s provided bydict.

All the implementations are valid options, but your code will be clearer and easier to maintain if it relies on standard Python dictionaries most of the time.

list: Mutable Dynamic Arrays

Lists are a part of the core Python language. Despite their name, Python’s lists are implemented asdynamic arrays behind the scenes.

This means a list allows elements to be added or removed, and the list will automatically adjust the backing store that holds these elements by allocating or releasing memory.

Python lists can hold arbitrary elements—everything is an object in Python, including functions. Therefore, you can mix and match different kinds of data types and store them all in a single list.

This can be a powerful feature, but the downside is that supporting multiple data types at the same time means that data is generally less tightly packed. As a result, the whole structure takes up more space:

>>>arr=["one","two","three"]>>>arr[0]'one'>>># Lists have a nice repr:>>>arr['one', 'two', 'three']>>># Lists are mutable:>>>arr[1]="hello">>>arr['one', 'hello', 'three']>>>delarr[1]>>>arr['one', 'three']>>># Lists can hold arbitrary data types:>>>arr.append(23)>>>arr['one', 'three', 23]

tuple: Immutable Containers

Just like lists,tuples are part of the Python core language. Unlike lists, however, Python’stuple objects are immutable. This means elements can’t be added or removed dynamically—all elements in a tuple must be defined at creation time.

Tuples are another data structure that can hold elements of arbitrary data types. Having this flexibility is powerful, but again, it also means that data is less tightly packed than it would be in a typed array:

>>>arr=("one","two","three")>>>arr[0]'one'>>># Tuples have a nice repr:>>>arr('one', 'two', 'three')>>># Tuples are immutable:>>>arr[1]="hello"Traceback (most recent call last):  File"<stdin>", line1, in<module>TypeError:'tuple' object does not support item assignment>>>delarr[1]Traceback (most recent call last):  File"<stdin>", line1, in<module>TypeError:'tuple' object doesn't support item deletion>>># Tuples can hold arbitrary data types:>>># (Adding elements creates a copy of the tuple)>>>arr+(23,)('one', 'two', 'three', 23)

array.array: Basic Typed Arrays

Python’sarray module provides space-efficient storage of basic C-style data types like bytes, 32-bit integers, floating-point numbers, and so on.

Arrays created with thearray.array class aremutable and behave similarly to lists except for one important difference: they’retyped arrays constrained to a single data type.

Because of this constraint,array.array objects with many elements are more space efficient than lists and tuples. The elements stored in them are tightly packed, and this can be useful if you need to store many elements of the same type.

Also, arrays support many of the same methods as regular lists, and you might be able to use them as a drop-in replacement without requiring other changes to your application code:

>>>importarray>>>arr=array.array("f",(1.0,1.5,2.0,2.5))>>>arr[1]1.5>>># Arrays have a nice repr:>>>arrarray('f', [1.0, 1.5, 2.0, 2.5])>>># Arrays are mutable:>>>arr[1]=23.0>>>arrarray('f', [1.0, 23.0, 2.0, 2.5])>>>delarr[1]>>>arrarray('f', [1.0, 2.0, 2.5])>>>arr.append(42.0)>>>arrarray('f', [1.0, 2.0, 2.5, 42.0])>>># Arrays are "typed":>>>arr[1]="hello"Traceback (most recent call last):  File"<stdin>", line1, in<module>TypeError:must be real number, not str

str: Immutable Arrays of Unicode Characters

Python 3.x usesstr objects to store textual data as immutable sequences ofUnicode characters. Practically speaking, that means astr is an immutable array of characters. Oddly enough, it’s also arecursive data structure—each character in a string is itself astr object of length 1.

String objects are space efficient because they’re tightly packed and they specialize in a single data type. If you’re storing Unicode text, then you should use a string.

Because strings are immutable in Python, modifying a string requires creating a modified copy. The closest equivalent to a mutable string is storing individual characters inside a list:

>>>arr="abcd">>>arr[1]'b'>>>arr'abcd'>>># Strings are immutable:>>>arr[1]="e"Traceback (most recent call last):  File"<stdin>", line1, in<module>TypeError:'str' object does not support item assignment>>>delarr[1]Traceback (most recent call last):  File"<stdin>", line1, in<module>TypeError:'str' object doesn't support item deletion>>># Strings can be unpacked into a list to>>># get a mutable representation:>>>list("abcd")['a', 'b', 'c', 'd']>>>"".join(list("abcd"))'abcd'>>># Strings are recursive data structures:>>>type("abc")"<class 'str'>">>>type("abc"[0])"<class 'str'>"

bytes: Immutable Arrays of Single Bytes

bytes objects are immutable sequences of single bytes, or integers in the range 0 ≤x ≤ 255. Conceptually,bytes objects are similar tostr objects, and you can also think of them as immutable arrays of bytes.

Like strings,bytes have their own literal syntax for creating objects and are space efficient.bytes objects are immutable, but unlike strings, there’s a dedicated mutable byte array data type calledbytearray that they can be unpacked into:

>>>arr=bytes((0,1,2,3))>>>arr[1]1>>># Bytes literals have their own syntax:>>>arrb'\x00\x01\x02\x03'>>>arr=b"\x00\x01\x02\x03">>># Only valid `bytes` are allowed:>>>bytes((0,300))Traceback (most recent call last):  File"<stdin>", line1, in<module>ValueError:bytes must be in range(0, 256)>>># Bytes are immutable:>>>arr[1]=23Traceback (most recent call last):  File"<stdin>", line1, in<module>TypeError:'bytes' object does not support item assignment>>>delarr[1]Traceback (most recent call last):  File"<stdin>", line1, in<module>TypeError:'bytes' object doesn't support item deletion

bytearray: Mutable Arrays of Single Bytes

Thebytearray type is a mutable sequence of integers in the range 0 ≤x ≤ 255. Thebytearray object is closely related to thebytes object, with the main difference being that abytearray can be modified freely—you can overwrite elements, remove existing elements, or add new ones. Thebytearray object will grow and shrink accordingly.

Abytearray can be converted back into immutablebytes objects, but this involves copying the stored data in full—a slow operation takingO(n) time:

>>>arr=bytearray((0,1,2,3))>>>arr[1]1>>># The bytearray repr:>>>arrbytearray(b'\x00\x01\x02\x03')>>># Bytearrays are mutable:>>>arr[1]=23>>>arrbytearray(b'\x00\x17\x02\x03')>>>arr[1]23>>># Bytearrays can grow and shrink in size:>>>delarr[1]>>>arrbytearray(b'\x00\x02\x03')>>>arr.append(42)>>>arrbytearray(b'\x00\x02\x03*')>>># Bytearrays can only hold `bytes`>>># (integers in the range 0 <= x <= 255)>>>arr[1]="hello"Traceback (most recent call last):  File"<stdin>", line1, in<module>TypeError:'str' object cannot be interpreted as an integer>>>arr[1]=300Traceback (most recent call last):  File"<stdin>", line1, in<module>ValueError:byte must be in range(0, 256)>>># Bytearrays can be converted back into bytes objects:>>># (This will copy the data)>>>bytes(arr)b'\x00\x02\x03*'

Arrays in Python: Summary

There are a number of built-in data structures you can choose from when it comes to implementing arrays in Python. In this section, you’ve focused on core language features and data structures included in the standard library.

If you’re willing to go beyond the Python standard library, then third-party packages likeNumPy andpandas offer a wide range of fast array implementations for scientific computing and data science.

If you want to restrict yourself to the array data structures included with Python, then here are a few guidelines:

• If you need to store arbitrary objects, potentially with mixed data types, then use alist or atuple, depending on whether or not you want an immutable data structure.

• If you have numeric (integer or floating-point) data and tight packing and performance is important, then try outarray.array.

• If you have textual data represented as Unicode characters, then use Python’s built-instr. If you need a mutable string-like data structure, then use alist of characters.

• If you want to store a contiguous block of bytes, then use the immutablebytes type or abytearray if you need a mutable data structure.

In most cases, I like to start out with a simplelist. I’ll only specialize later on if performance or storage space becomes an issue. Most of the time, using a general-purpose array data structure likelist gives you the fastest development speed and the most programming convenience.

I’ve found that this is usually much more important in the beginning than trying to squeeze out every last drop of performance right from the start.

dict: Simple Data Objects

As mentionedpreviously, Python dictionaries store an arbitrary number of objects, each identified by a unique key. Dictionaries are also often calledmaps orassociative arrays and allow for efficient lookup, insertion, and deletion of any object associated with a given key.

Using dictionaries as a record data type or data object in Python is possible. Dictionaries are easy to create in Python as they have their own syntactic sugar built into the language in the form ofdictionary literals. The dictionary syntax is concise and quite convenient to type.

Data objects created using dictionaries are mutable, and there’s little protection against misspelled field names as fields can be added and removed freely at any time. Both of these properties can introduce surprising bugs, and there’s always a trade-off to be made between convenience and error resilience:

>>>car1={..."color":"red",..."mileage":3812.4,..."automatic":True,...}>>>car2={..."color":"blue",..."mileage":40231,..."automatic":False,...}>>># Dicts have a nice repr:>>>car2{'color': 'blue', 'automatic': False, 'mileage': 40231}>>># Get mileage:>>>car2["mileage"]40231>>># Dicts are mutable:>>>car2["mileage"]=12>>>car2["windshield"]="broken">>>car2{'windshield': 'broken', 'color': 'blue', 'automatic': False, 'mileage': 12}>>># No protection against wrong field names,>>># or missing/extra fields:>>>car3={..."colr":"green",..."automatic":False,..."windshield":"broken",...}

tuple: Immutable Groups of Objects

Python’s tuples are a straightforward data structure for grouping arbitrary objects. Tuples are immutable—they can’t be modified once they’ve been created.

Performance-wise, tuples take upslightly less memory thanlists in CPython, and they’re also faster to construct.

As you can see in the bytecode disassembly below, constructing a tuple constant takes a singleLOAD_CONST opcode, while constructing a list object with the same contents requires several more operations:

>>>importdis>>>dis.dis(compile("(23, 'a', 'b', 'c')","","eval"))      0 LOAD_CONST           4 ((23, "a", "b", "c"))      3 RETURN_VALUE>>>dis.dis(compile("[23, 'a', 'b', 'c']","","eval"))      0 LOAD_CONST           0 (23)      3 LOAD_CONST           1 ('a')      6 LOAD_CONST           2 ('b')      9 LOAD_CONST           3 ('c')     12 BUILD_LIST           4     15 RETURN_VALUE

However, you shouldn’t place too much emphasis on these differences. In practice, the performance difference will often be negligible, and trying to squeeze extra performance out of a program by switching from lists to tuples will likely be the wrong approach.

A potential downside of plain tuples is that the data you store in them can only be pulled out by accessing it through integer indexes. You can’t give names to individual properties stored in a tuple. This can impact code readability.

Also, a tuple is always an ad-hoc structure: it’s difficult to ensure that two tuples have the same number of fields and the same properties stored in them.

This makes it easy to introduce slip-of-the-mind bugs, such as mixing up the field order. Therefore, I would recommend that you keep the number of fields stored in a tuple as low as possible:

>>># Fields: color, mileage, automatic>>>car1=("red",3812.4,True)>>>car2=("blue",40231.0,False)>>># Tuple instances have a nice repr:>>>car1('red', 3812.4, True)>>>car2('blue', 40231.0, False)>>># Get mileage:>>>car2[1]40231.0>>># Tuples are immutable:>>>car2[1]=12Traceback (most recent call last):  File"<stdin>", line1, in<module>TypeError:'tuple' object does not support item assignment>>># No protection against missing or extra fields>>># or a wrong order:>>>car3=(3431.5,"green",True,"silver")

Write a Custom Class: More Work, More Control

Classes allow you to define reusable blueprints for data objects to ensure each object provides the same set of fields.

Using regularPython classes as record data types is feasible, but it also takes manual work to get the convenience features of other implementations. For example, adding new fields to the__init__ constructor is verbose and takes time.

Also, the default string representation for objects instantiated from custom classes isn’t very helpful. To fix that, you may have to add your own__repr__ method, which again is usually quite verbose and must be updated each time you add a new field.

Fields stored on classes are mutable, and new fields can be added freely, which you may or may not like. It’s possible to provide more access control and to create read-only fields using the@property decorator, but once again, this requires writing more glue code.

Writing a custom class is a great option whenever you’d like to add business logic and behavior to your record objects using methods. However, this means that these objects are technically no longer plain data objects:

>>>classCar:...def__init__(self,color,mileage,automatic):...self.color=color...self.mileage=mileage...self.automatic=automatic...>>>car1=Car("red",3812.4,True)>>>car2=Car("blue",40231.0,False)>>># Get the mileage:>>>car2.mileage40231.0>>># Classes are mutable:>>>car2.mileage=12>>>car2.windshield="broken">>># String representation is not very useful>>># (must add a manually written __repr__ method):>>>car1<Car object at 0x1081e69e8>

dataclasses.dataclass: Python 3.7+ Data Classes

Data classes are available in Python 3.7 and above. They provide an excellent alternative to defining your own data storage classes from scratch.

By writing a data class instead of a plain Python class, your object instances get a few useful features out of the box that will save you some typing and manual implementation work:

• The syntax for defining instance variables is shorter, since you don’t need to implement the.__init__() method.
• Instances of your data class automatically get nice-looking string representation via an auto-generated.__repr__() method.
• Instance variables accept type annotations, making your data class self-documenting to a degree. Keep in mind that type annotations are just hints that are not enforced without a separatetype-checking tool.

Data classes are typically created using the@dataclassdecorator, as you’ll see in the code example below:

>>>fromdataclassesimportdataclass>>>@dataclass...classCar:...color:str...mileage:float...automatic:bool...>>>car1=Car("red",3812.4,True)>>># Instances have a nice repr:>>>car1Car(color='red', mileage=3812.4, automatic=True)>>># Accessing fields:>>>car1.mileage3812.4>>># Fields are mutable:>>>car1.mileage=12>>>car1.windshield="broken">>># Type annotations are not enforced without>>># a separate type checking tool like mypy:>>>Car("red","NOT_A_FLOAT",99)Car(color='red', mileage='NOT_A_FLOAT', automatic=99)

To learn more about Python data classes, check out theThe Ultimate Guide to Data Classes in Python 3.7.

collections.namedtuple: Convenient Data Objects

Thenamedtuple class available in Python 2.6+ provides an extension of the built-intuple data type. Similar to defining a custom class, usingnamedtuple allows you to define reusable blueprints for your records that ensure the correct field names are used.

namedtuple objects are immutable, just like regular tuples. This means you can’t add new fields or modify existing fields after thenamedtuple instance is created.

Besides that,namedtuple objects are, well . . . named tuples. Each object stored in them can be accessed through a unique identifier. This frees you from having to remember integer indexes or resort to workarounds like defininginteger constants as mnemonics for your indexes.

namedtuple objects are implemented as regular Python classes internally. When it comes to memory usage, they’re also better than regular classes and just as memory efficient as regular tuples:

>>>fromcollectionsimportnamedtuple>>>fromsysimportgetsizeof>>>p1=namedtuple("Point","x y z")(1,2,3)>>>p2=(1,2,3)>>>getsizeof(p1)64>>>getsizeof(p2)64

namedtuple objects can be an easy way to clean up your code and make it more readable by enforcing a better structure for your data.

I find that going from ad-hoc data types like dictionaries with a fixed format tonamedtuple objects helps me to express the intent of my code more clearly. Often when I apply this refactoring, I magically come up with a better solution for the problem I’m facing.

Usingnamedtuple objects over regular (unstructured) tuples and dicts can also make your coworkers’ lives easier by making the data that’s being passed around self-documenting, at least to a degree:

>>>fromcollectionsimportnamedtuple>>>Car=namedtuple("Car","color mileage automatic")>>>car1=Car("red",3812.4,True)>>># Instances have a nice repr:>>>car1Car(color="red", mileage=3812.4, automatic=True)>>># Accessing fields:>>>car1.mileage3812.4>>># Fields are immtuable:>>>car1.mileage=12Traceback (most recent call last):  File"<stdin>", line1, in<module>AttributeError:can't set attribute>>>car1.windshield="broken"Traceback (most recent call last):  File"<stdin>", line1, in<module>AttributeError:'Car' object has no attribute 'windshield'

typing.NamedTuple: Improved Namedtuples

Added in Python 3.6,typing.NamedTuple is the younger sibling of thenamedtuple class in thecollections module. It’s very similar tonamedtuple, with the main difference being an updated syntax for defining new record types and added support fortype hints.

Please note that type annotations are not enforced without a separate type-checking tool likemypy. But even without tool support, they can provide useful hints for other programmers (or be terribly confusing if the type hints become out of date):

>>>fromtypingimportNamedTuple>>>classCar(NamedTuple):...color:str...mileage:float...automatic:bool>>>car1=Car("red",3812.4,True)>>># Instances have a nice repr:>>>car1Car(color='red', mileage=3812.4, automatic=True)>>># Accessing fields:>>>car1.mileage3812.4>>># Fields are immutable:>>>car1.mileage=12Traceback (most recent call last):  File"<stdin>", line1, in<module>AttributeError:can't set attribute>>>car1.windshield="broken"Traceback (most recent call last):  File"<stdin>", line1, in<module>AttributeError:'Car' object has no attribute 'windshield'>>># Type annotations are not enforced without>>># a separate type checking tool like mypy:>>>Car("red","NOT_A_FLOAT",99)Car(color='red', mileage='NOT_A_FLOAT', automatic=99)

struct.Struct: Serialized C Structs

Thestruct.Struct class converts between Python values and C structs serialized into Pythonbytes objects. For example, it can be used to handle binary data stored in files or coming in from network connections.

Structs are defined using a mini language based onformat strings that allows you to define the arrangement of various C data types likechar,int, andlong as well as theirunsigned variants.

Serialized structs are seldom used to represent data objects meant to be handled purely inside Python code. They’re intended primarily as a data exchange format rather than as a way of holding data in memory that’s only used by Python code.

In some cases, packing primitive data into structs may use less memory than keeping it in other data types. However, in most cases that would be quite an advanced (and probably unnecessary) optimization:

>>>fromstructimportStruct>>>MyStruct=Struct("i?f")>>>data=MyStruct.pack(23,False,42.0)>>># All you get is a blob of data:>>>datab'\x17\x00\x00\x00\x00\x00\x00\x00\x00\x00(B'>>># Data blobs can be unpacked again:>>>MyStruct.unpack(data)(23, False, 42.0)

types.SimpleNamespace: Fancy Attribute Access

Here’s one more slightly obscure choice for implementing data objects in Python:types.SimpleNamespace. This class was added in Python 3.3 and providesattribute access to its namespace.

This meansSimpleNamespace instances expose all of their keys as class attributes. You can useobj.key dotted attribute access instead of theobj['key'] square-bracket indexing syntax that’s used by regular dicts. All instances also include a meaningful__repr__ by default.

As its name proclaims,SimpleNamespace is simple! It’s basically a dictionary that allows attribute access and prints nicely. Attributes can be added, modified, and deleted freely:

>>>fromtypesimportSimpleNamespace>>>car1=SimpleNamespace(color="red",mileage=3812.4,automatic=True)>>># The default repr:>>>car1namespace(automatic=True, color='red', mileage=3812.4)>>># Instances support attribute access and are mutable:>>>car1.mileage=12>>>car1.windshield="broken">>>delcar1.automatic>>>car1namespace(color='red', mileage=12, windshield='broken')

Records, Structs, and Data Objects in Python: Summary

As you’ve seen, there’s quite a number of different options for implementing records or data objects. Which type should you use for data objects in Python? Generally your decision will depend on your use case:

• If you have only a few fields, then using a plain tuple object may be okay if the field order is easy to remember or field names are superfluous. For example, think of an(x, y, z) point in three-dimensional space.

• If you need immutable fields, then plain tuples,collections.namedtuple, andtyping.NamedTuple are all good options.

• If you need to lock down field names to avoid typos, thencollections.namedtuple andtyping.NamedTuple are your friends.

• If you want to keep things simple, then a plain dictionary object might be a good choice due to the convenient syntax that closely resemblesJSON.

• If you need full control over your data structure, then it’s time to write a custom class with@propertysetters and getters.

• If you need to add behavior (methods) to the object, then you should write a custom class, either from scratch, or using thedataclass decorator, or by extendingcollections.namedtuple ortyping.NamedTuple.

• If you need to pack data tightly to serialize it to disk or to send it over the network, then it’s time to read up onstruct.Struct because this is a great use case for it!

If you’re looking for a safe default choice, then my general recommendation for implementing a plain record, struct, or data object in Python would be to usecollections.namedtuple in Python 2.x and its younger sibling,typing.NamedTuple in Python 3.

set: Your Go-to Set

Theset type is the built-in set implementation in Python. It’s mutable and allows for the dynamic insertion and deletion of elements.

Python’s sets are backed by thedict data type and share the same performance characteristics. Anyhashable object can be stored in a set:

>>>vowels={"a","e","i","o","u"}>>>"e"invowelsTrue>>>letters=set("alice")>>>letters.intersection(vowels){'a', 'e', 'i'}>>>vowels.add("x")>>>vowels{'i', 'a', 'u', 'o', 'x', 'e'}>>>len(vowels)6

frozenset: Immutable Sets

Thefrozenset class implements an immutable version ofset that can’t be changed after it’s been constructed.

frozenset objects are static and allow only query operations on their elements, not inserts or deletions. Becausefrozenset objects are static and hashable, they can be used as dictionary keys or as elements of another set, something that isn’t possible with regular (mutable)set objects:

>>>vowels=frozenset({"a","e","i","o","u"})>>>vowels.add("p")Traceback (most recent call last):  File"<stdin>", line1, in<module>AttributeError:'frozenset' object has no attribute 'add'>>># Frozensets are hashable and can>>># be used as dictionary keys:>>>d={frozenset({1,2,3}):"hello"}>>>d[frozenset({1,2,3})]'hello'

collections.Counter: Multisets

Thecollections.Counter class in the Python standard library implements a multiset, or bag, type that allows elements in the set to have more than one occurrence.

This is useful if you need to keep track of not onlyif an element is part of a set, but alsohow many times it’s included in the set:

>>>fromcollectionsimportCounter>>>inventory=Counter()>>>loot={"sword":1,"bread":3}>>>inventory.update(loot)>>>inventoryCounter({'bread': 3, 'sword': 1})>>>more_loot={"sword":1,"apple":1}>>>inventory.update(more_loot)>>>inventoryCounter({'bread': 3, 'sword': 2, 'apple': 1})

One caveat for theCounter class is that you’ll want to be careful when counting the number of elements in aCounter object. Callinglen() returns the number ofunique elements in the multiset, whereas thetotal number of elements can be retrieved usingsum():

>>>len(inventory)3  # Unique elements>>>sum(inventory.values())6  # Total no. of elements

Sets and Multisets in Python: Summary

Sets are another useful and commonly used data structure included with Python and its standard library. Here are a few guidelines for deciding which one to use:

• If you need a mutable set, then use the built-inset type.
• If you need hashable objects that can be used as dictionary or set keys, then use afrozenset.
• If you need a multiset, or bag, data structure, then usecollections.Counter.

list: Simple, Built-in Stacks

Python’s built-inlist typemakes a decent stack data structure as it supports push and pop operations inamortizedO(1) time.

Python’s lists are implemented as dynamic arrays internally, which means they occasionally need to resize the storage space for elements stored in them when elements are added or removed. The list over-allocates its backing storage so that not every push or pop requires resizing. As a result, you get an amortizedO(1) time complexity for these operations.

The downside is that this makes their performance less consistent than the stableO(1) inserts and deletes provided by a linked list–based implementation (as you’ll see below withcollections.deque). On the other hand, lists do provide fastO(1) time random access to elements on the stack, and this can be an added benefit.

There’s an important performance caveat that you should be aware of when using lists as stacks: To get the amortizedO(1) performance for inserts and deletes, new items must be added to theend of the list with theappend() method and removed again from the end usingpop(). For optimum performance, stacks based on Python lists should grow towards higher indexes and shrink towards lower ones.

Adding and removing from the front is much slower and takesO(n) time, as the existing elements must be shifted around to make room for the new element. This is a performanceantipattern that you should avoid as much as possible:

>>>s=[]>>>s.append("eat")>>>s.append("sleep")>>>s.append("code")>>>s['eat', 'sleep', 'code']>>>s.pop()'code'>>>s.pop()'sleep'>>>s.pop()'eat'>>>s.pop()Traceback (most recent call last):  File"<stdin>", line1, in<module>IndexError:pop from empty list

collections.deque: Fast and Robust Stacks

Thedeque class implements adouble-ended queue that supports adding and removing elements from either end inO(1) time (non-amortized). Because deques support adding and removing elements from either end equally well, they can serve both as queues and as stacks.

Python’sdeque objects are implemented asdoubly-linked lists, which gives them excellent and consistent performance for inserting and deleting elements but poorO(n) performance for randomly accessing elements in the middle of a stack.

Overall,collections.deque is a great choice if you’re looking for a stack data structure in Python’s standard library that has the performance characteristics of a linked-list implementation:

>>>fromcollectionsimportdeque>>>s=deque()>>>s.append("eat")>>>s.append("sleep")>>>s.append("code")>>>sdeque(['eat', 'sleep', 'code'])>>>s.pop()'code'>>>s.pop()'sleep'>>>s.pop()'eat'>>>s.pop()Traceback (most recent call last):  File"<stdin>", line1, in<module>IndexError:pop from an empty deque

queue.LifoQueue: Locking Semantics for Parallel Computing

TheLifoQueue stack implementation in the Python standard library is synchronized and provideslocking semantics to support multiple concurrent producers and consumers.

BesidesLifoQueue, thequeue module contains several other classes that implement multi-producer, multi-consumer queues that are useful for parallel computing.

Depending on your use case, the locking semantics might be helpful, or they might just incur unneeded overhead. In this case, you’d be better off using alist or adeque as a general-purpose stack:

>>>fromqueueimportLifoQueue>>>s=LifoQueue()>>>s.put("eat")>>>s.put("sleep")>>>s.put("code")>>>s<queue.LifoQueue object at 0x108298dd8>>>>s.get()'code'>>>s.get()'sleep'>>>s.get()'eat'>>>s.get_nowait()queue.Empty>>>s.get()# Blocks/waits forever...

Stack Implementations in Python: Summary

As you’ve seen, Python ships with several implementations for a stack data structure. All of them have slightly different characteristics as well as performance and usage trade-offs.

If you’re not looking forparallel processing support (or if you don’t want to handle locking and unlocking manually), then your choice comes down to the built-inlist type orcollections.deque. The difference lies in the data structure used behind the scenes and overall ease of use.

list is backed by a dynamic array, which makes it great for fast random access but requires occasional resizing when elements are added or removed.

The list over-allocates its backing storage so that not every push or pop requires resizing, and you get an amortizedO(1) time complexity for these operations. But you do need to be careful to only insert and remove items usingappend() andpop(). Otherwise, performance slows down toO(n).

collections.deque is backed by a doubly-linked list, which optimizes appends and deletes at both ends and provides consistentO(1) performance for these operations. Not only is its performance more stable, thedeque class is also easier to use because you don’t have to worry about adding or removing items from the wrong end.

In summary,collections.deque is an excellent choice for implementing a stack (LIFO queue) in Python.

list: Terribly Sloooow Queues

It’s possible touse a regularlist as a queue, but this is not ideal from a performance perspective. Lists are quite slow for this purpose because inserting or deleting an element at the beginning requires shifting all the other elements by one, requiringO(n) time.

Therefore, I wouldnot recommend using alist as a makeshift queue in Python unless you’re dealing with only a small number of elements:

>>>q=[]>>>q.append("eat")>>>q.append("sleep")>>>q.append("code")>>>q['eat', 'sleep', 'code']>>># Careful: This is slow!>>>q.pop(0)'eat'

collections.deque: Fast and Robust Queues

Thedeque class implements a double-ended queue that supports adding and removing elements from either end inO(1) time (non-amortized). Because deques support adding and removing elements from either end equally well, they can serve both as queues and as stacks.

Python’sdeque objects are implemented as doubly-linked lists. This gives them excellent and consistent performance for inserting and deleting elements, but poorO(n) performance for randomly accessing elements in the middle of the stack.

As a result,collections.deque is a great default choice if you’re looking for a queue data structure in Python’s standard library:

>>>fromcollectionsimportdeque>>>q=deque()>>>q.append("eat")>>>q.append("sleep")>>>q.append("code")>>>qdeque(['eat', 'sleep', 'code'])>>>q.popleft()'eat'>>>q.popleft()'sleep'>>>q.popleft()'code'>>>q.popleft()Traceback (most recent call last):  File"<stdin>", line1, in<module>IndexError:pop from an empty deque

queue.Queue: Locking Semantics for Parallel Computing

Thequeue.Queue implementation in the Python standard library is synchronized and provides locking semantics to support multiple concurrent producers and consumers.

Thequeue module contains several other classes implementing multi-producer, multi-consumer queues that are useful for parallel computing.

Depending on your use case, the locking semantics might be helpful or just incur unneeded overhead. In this case, you’d be better off usingcollections.deque as a general-purpose queue:

>>>fromqueueimportQueue>>>q=Queue()>>>q.put("eat")>>>q.put("sleep")>>>q.put("code")>>>q<queue.Queue object at 0x1070f5b38>>>>q.get()'eat'>>>q.get()'sleep'>>>q.get()'code'>>>q.get_nowait()queue.Empty>>>q.get()# Blocks/waits forever...

multiprocessing.Queue: Shared Job Queues

multiprocessing.Queue is a shared job queue implementation that allows queued items to be processed in parallel by multiple concurrent workers. Process-based parallelization is popular in CPython due to theglobal interpreter lock (GIL) that prevents some forms of parallel execution on a single interpreter process.

As a specialized queue implementation meant for sharing data between processes,multiprocessing.Queue makes it easy to distribute work across multiple processes in order to work around the GIL limitations. This type of queue can store and transfer anypickleable object across process boundaries:

>>>frommultiprocessingimportQueue>>>q=Queue()>>>q.put("eat")>>>q.put("sleep")>>>q.put("code")>>>q<multiprocessing.queues.Queue object at 0x1081c12b0>>>>q.get()'eat'>>>q.get()'sleep'>>>q.get()'code'>>>q.get()# Blocks/waits forever...

Queues in Python: Summary

Python includes several queue implementations as part of the core language and its standard library.

list objects can be used as queues, but this is generally not recommended due to slow performance.

If you’re not looking for parallel processing support, then the implementation offered bycollections.deque is an excellent default choice for implementing a FIFO queue data structure in Python. It provides the performance characteristics you’d expect from a good queue implementation and can also be used as a stack (LIFO queue).

list: Manually Sorted Queues

You can use a sortedlist to quickly identify and delete the smallest or largest element. The downside is that inserting new elements into a list is a slowO(n) operation.

While the insertion point can be found inO(logn) time usingbisect.insort in the standard library, this is always dominated by the slow insertion step.

Maintaining the order by appending to the list and re-sorting also takes at leastO(n logn) time. Another downside is that you must manually take care of re-sorting the list when new elements are inserted. It’s easy to introduce bugs by missing this step, and the burden is always on you, the developer.

This means sorted lists are only suitable as priority queues when there will be few insertions:

>>>q=[]>>>q.append((2,"code"))>>>q.append((1,"eat"))>>>q.append((3,"sleep"))>>># Remember to re-sort every time a new element is inserted,>>># or use bisect.insort()>>>q.sort(reverse=True)>>>whileq:...next_item=q.pop()...print(next_item)...(1, 'eat')(2, 'code')(3, 'sleep')

heapq: List-Based Binary Heaps

heapq is a binary heap implementation usually backed by a plainlist, and it supports insertion and extraction of the smallest element inO(logn) time.

This module is a good choice forimplementing priority queues in Python. Sinceheapq technically provides only a min-heap implementation,extra steps must be taken to ensure sort stability and other features typically expected from a practical priority queue:

>>>importheapq>>>q=[]>>>heapq.heappush(q,(2,"code"))>>>heapq.heappush(q,(1,"eat"))>>>heapq.heappush(q,(3,"sleep"))>>>whileq:...next_item=heapq.heappop(q)...print(next_item)...(1, 'eat')(2, 'code')(3, 'sleep')

queue.PriorityQueue: Beautiful Priority Queues

queue.PriorityQueue usesheapq internally and shares the same time and space complexities. The difference is thatPriorityQueue is synchronized and provides locking semantics to support multiple concurrent producers and consumers.

Depending on your use case, this might be helpful, or it might just slow your program down slightly. In any case, you might prefer the class-based interface provided byPriorityQueue over the function-based interface provided byheapq:

>>>fromqueueimportPriorityQueue>>>q=PriorityQueue()>>>q.put((2,"code"))>>>q.put((1,"eat"))>>>q.put((3,"sleep"))>>>whilenotq.empty():...next_item=q.get()...print(next_item)...(1, 'eat')(2, 'code')(3, 'sleep')

Priority Queues in Python: Summary

Python includes several priority queue implementations ready for you to use.

queue.PriorityQueue stands out from the pack with a nice object-oriented interface and a name that clearly states its intent. It should be your preferred choice.

If you’d like to avoid the locking overhead ofqueue.PriorityQueue, then using theheapq module directly is also a good option.