Fluent Python—Dictionaries and Sets

Python

1. Dictionaries

1.1. Modern dict Syntax

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
# An iterable of key-value pairs can be passed directly to the dict constructor
dial_codes = [
    (86, 'China'),
    (81, 'Japan'),
    (7, 'Russia'),
    (1, 'United States'),
]
print(dict(dial_codes))  # {86: 'China', 81: 'Japan', 7: 'Russia', 1: 'United States'}

# A dictcomp (dict comprehension) builds a dict instance by taking key:value pairs from any iterable
country_dial = {country: code for code, country in dial_codes}
print(country_dial)  # {'China': 86, 'Japan': 81, 'Russia': 7, 'United States': 1}
print({code: country.upper() for country, code in sorted(country_dial.items()) if code < 70})  # {7: 'RUSSIA', 1: 'UNITED STATES'}

# We can apply ** to more than one argument in a function call. This works when keys are all strings and unique across all arguments
def dump(**kwargs):
    return kwargs
print(dump(**{'x': 1}, y=2, **{'z': 3}))  # {'x': 1, 'y': 2, 'z': 3}
# ** can be used inside a dict literal multiple times, but duplicate keys are allowed, later occurrences overwrite previous ones
print({'a': 0, **{'x': 1}, 'y': 2, **{'z': 3, 'x': 4}})  # {'a': 0, 'x': 4, 'y': 2, 'z': 3}

# Python 3.9 supports using | and |= to merge mappings, these are also the set union operators
d1 = {'a': 1, 'b': 3}
d2 = {'a': 2, 'b': 4, 'c': 6}
# Usually the new mapping type will be the same as the left operand type, but it can be other type according to the operator overloading rules
print(d1 | d2)  # {'a': 2, 'b': 4, 'c': 6}
print(d1)  # {'a': 1, 'b': 3}
# Update mapping in place
d1 |= d2
print(d1)  # {'a': 2, 'b': 4, 'c': 6}

1.2. Pattern Matching with Mappings

  • The match/case statement supports subjects that are mapping objects. Patterns for mappings look like dict literals, but they can match instances of any actual or virtual subclass of collections.abc.Mapping
  • In the context of pattern matching, a match succeeds only if the subject already has the required keys at the top of the match statement. The automatic handling of missing keys is not triggered because pattern matching always uses the d.get(key, sentinel) method—where the default sentinel is a special marker value that cannot occur in user data
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
def get_creators(record: dict) -> list:
    match record:
        # different types of patterns can be combined and nested
        case {'type': 'book', 'api': 2, 'authors': [*names]}:
            return names
        case {'type': 'book', 'api': 1, 'author': name}:
            return [name]
        case {'type': 'book'}:
            raise ValueError(f"Invalid 'book' record: {record!r}")
        # capture extra k-v pairs, must be the last in the pattern, and **_ is forbidden
        case {'type': 'movie', 'director': name, **details}:
            print(f"movie details: {details}")  # movie details: {'title': 'Avatar', 'year': '2009'}
            return [name]
        case _:
            raise ValueError(f'Invalid record: {record!r}')

# In contrast with sequence patterns, mapping patterns succeed on partial matches
b1 = dict(api=1, type='book', title='Gödel, Escher, Bach', author='Douglas Hofstadter')
print(get_creators(b1))  # ['Douglas Hofstadter']
# Order is irrelevant
from collections import OrderedDict
b2 = OrderedDict(api=2, type='book', title='Python in a Nutshell', authors='Martelli Ravenscroft Holden'.split())
print(get_creators(b2))  # ['Martelli', 'Ravenscroft', 'Holden']
b3 = dict(type='movie', title='Avatar', director='James Cameron', year='2009')
print(get_creators(b3))  # ['James Cameron']
#print(get_creators({'type': 'book', 'pages': 770}))  # ValueError: Invalid 'book' record: {'type': 'book', 'pages': 770}
#print(get_creators('Spam, spam, spam'))  # ValueError: Invalid record: 'Spam, spam, spam'

1.3. Dictionary Views

  • The dict instance methods .keys(), .values(), and .items() return instances of classes called dict_keys, dict_values, and dict_items, respectively. These dictionary views are read-only projections of the internal data structures used in the dict implementation. They avoid the memory overhead of the equivalent Python 2 methods that returned lists duplicating data already in the target dict, and they also replace the old methods that returned iterators
  • A view object is a dynamic proxy. If the source dict is updated, you can immediately see the changes through an existing view
  • The classes dict_keys, dict_values, and dict_items are internal: they are not available via __builtins__ or any standard library module, and even if you get a reference to one of them, you can’t use it to create a view from scratch in Python code
  • The dict_values class is the simplest dictionary view—it implements only the __len__, __iter__, and __reversed__ special methods. In addition to these methods, dict_keys and dict_items implement several set methods, almost as many as the frozenset class
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
d = dict(a=10, b=20, c=30)
values = d.values()
print(values)  # dict_values([10, 20, 30])
print(len(values))  # 3
print(list(values))  # [10, 20, 30]
# views implement __reversed__, returning a custom iterator
print(reversed(values))  # <dict_reversevalueiterator object at 0x10771f2e0>
# can't use [] to get individual items from a view
#print(values[0])  # TypeError: 'dict_values' object is not subscriptable

d['z'] = 99
print(values)  # dict_values([10, 20, 30, 99])

values_class = type({}.values())
#v = values_class()  # TypeError: cannot create 'dict_values' instances

1.4. Common Mapping Methods

dict defaultdict OrderedDict
d.clear() ● ● ● Remove all items
d.__contains__(k) ● ● ● k in d
d.copy() ● ● ● Shallow copy
d.__copy__() ● Support for copy.copy(d)
d.default_factory ● Callable invoked by __missing__ to set missing values
d.__delitem__(k) ● ● ● del d[k]—remove item with key k
d.fromkeys(it, [initial]) ● ● ● New mapping from keys in iterable, with optional initial value (defaults to None)
d.get(k, [default]) ● ● ● Get item with key k, return default or None if missing
d.__getitem__(k) ● ● ● d[k]—get item with key k
d.items() ● ● ● Get view over items—(key, value) pairs
d.__iter__() ● ● ● Get iterator over keys
d.keys() ● ● ● Get view over keys
d.__len__() ● ● ● len(d)—number of items
d.__missing__(k) ● Called when __getitem__ cannot find the key
d.move_to_end(k, [last]) ● Move k first or last position (last is True by default)
d.__or__(other) ● ● ● Support for d1 | d2 to create new dict merging d1 and d2 (Python ≥ 3.9)
d.__ior__(other) ● ● ● Support for d1 |= d2 to update d1 with d2 (Python ≥ 3.9)
d.pop(k, [default]) ● ● ● Remove and return value at k, or default or None if missing
d.popitem() ● ● ● Remove and return the last inserted item as (key, value)
d.__reversed__() ● ● ● Support for reverse(d)—returns iterator for keys from last to first inserted
d.__ror__(other) ● ● ● Support for other | d—reversed union operator (Python ≥ 3.9)
d.setdefault(k, [default]) ● ● ● If k in d, return d[k]; else set d[k] = default and return it
d.__setitem__(k, v) ● ● ● d[k] = v—put v at k
d.update(m, [**kwargs]) ● ● ● Update d with items from mapping or iterable of (key, value) pairs
d.values() ● ● ● Get view over values
  • The way d.update(m) handles its first argument m is a prime example of duck typing: it first checks whether m has a keys method and, if it does, assumes it is a mapping. Otherwise, update() falls back to iterating over m, assuming its items are (key, value) pairs
  • The constructor for most Python mappings uses the logic of update() internally, which means they can be initialized from other mappings or from any iterable object producing (key, value) pairs

1.5. Standard API of Mapping Types

MutableMapping

  • The collections.abc module provides the Mapping and MutableMapping ABCs describing the interfaces of dict and similar types. The main value of the ABCs is documenting and formalizing the standard interfaces for mappings, and serving as criteria for isinstance tests in code that needs to support mappings in a broad sense
  • Using isinstance with an ABC is often better than checking whether a function argument is of the concrete dict type, because then alternative mapping types can be used
  • To implement a custom mapping, it’s easier to extend collections.UserDict, or to wrap a dict by composition, instead of subclassing these ABCs. The collections.UserDict class and all concrete mapping classes in the standard library encapsulate the basic dict in their implementation, which in turn is built on a hash table. Therefore, they all share the limitation that the keys must be hashable
1
2
3
4
from collections import abc
my_dict = {}
print(isinstance(my_dict, abc.Mapping))  # True
print(isinstance(my_dict, abc.MutableMapping))  # True

1.6. What Is Hashable

  • An object is hashable if it has a hash code which never changes during its lifetime (it needs a __hash__() method), and can be compared to other objects (it needs an __eq__() method). Hashable objects which compare equal must have the same hash code
  • Numeric types and flat immutable types str and bytes are all hashable. Container types are hashable if they are immutable and all contained objects are also hashable. A frozenset is always hashable, because every element it contains must be hashable by definition. A tuple is hashable only if all its items are hashable
  • The hash code of an object may be different depending on the version of Python, the machine architecture, and because of a salt added to the hash computation for security reasons. The hash code of a correctly implemented object is guaranteed to be constant only within one Python process
  • User-defined types are hashable by default because their hash code is their id(), and the __eq__() method inherited from the object class simply compares the object IDs. If an object implements a custom __eq__() that takes into account its internal state, it will be hashable only if its __hash__() always returns the same hash code. In practice, this requires that __eq__() and __hash__() only take into account instance attributes that never change during the life of the object
1
2
3
4
5
6
tt = (1, 2, (30, 40))
print(hash(tt))  # -3907003130834322577
tl = (1, 2, [30, 40])
#print(hash(tl))  # TypeError: unhashable type: 'list'
tf = (1, 2, frozenset([30, 40]))
print(hash(tf))  # 5149391500123939311

1.7. How dict Works

  • The hash table implementation of Python’s dict is very efficient, but it’s important to understand the practical effects of this design:
    • Keys must be hashable objects. They must implement proper __hash__ and __eq__ methods
    • Item access by key is very fast. A dict may have millions of keys, but Python can locate a key directly by computing the hash code of the key and deriving an index offset into the hash table, with the possible overhead of a small number of tries to find a matching entry
    • Key ordering is preserved as a side effect of a more compact memory layout for dict in CPython 3.6, which became an official language feature in 3.7
    • Despite its new compact layout, dicts inevitably have a significant memory overhead. The most compact internal data structure for a container would be an array of pointers to the items (That’s how tuples are stored). Compared to that, a hash table needs to store more data per entry, and Python needs to keep at least one-third of the hash table rows empty to remain efficient
    • To save memory, avoid creating instance attributes outside of the __init__ method
  • Python’s default behavior is to store instance attributes in a special __dict__ attribute, which is a dict attached to each instance. Since PEP 412—Key-Sharing Dictionary was implemented in Python 3.3, instances of a class can share a common hash table, stored with the class. That common hash table is shared by the __dict__ of each new instance that has the same attributes names as the first instance of that class when __init__ returns. Each instance __dict__ can then hold only its own attribute values as a simple array of pointers. Adding an instance attribute after __init__ forces Python to create a new hash table just for the __dict__ of that one instance (which was the default behavior for all instances before Python 3.3)

2. Automatic Handling of Missing Keys

  • Sometimes it is convenient to have mappings that return some made-up value when a missing key is searched. There are two main approaches to this: one is to use a defaultdict instead of a plain dict. The other is to subclass dict or any other mapping type and add a __missing__ method

2.1. Inserting or Updating Mutable Values

  • In line with Python’s fail-fast philosophy, dict access with d[k] raises an error when k is not an existing key. Pythonistas know that d.get(k, default) is an alternative to d[k] whenever a default value is more convenient than handling KeyError. However, when you retrieve a mutable value and want to update it, there is a better way
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
import re

WORD_RE = re.compile(r'\w+')
index = {}

with open("a.txt", encoding='utf-8') as fp:
    for line_no, line in enumerate(fp, 1):
        for match in WORD_RE.finditer(line):
            word = match.group()
            column_no = match.start() + 1
            location = (line_no, column_no)
            # this is ugly; coded like this to make a point
            #occurrences = index.get(word, [])
            #occurrences.append(location)
            #index[word] = occurrences
            # setdefault avoids redundant key lookups
            index.setdefault(word, []).append(location)

for word in sorted(index, key=str.upper):
    print(word, index[word])

# a.txt:
# Welcome to the English-language Wiktionary, a collaborative project to produce a free-content multilingual dictionary. 
# It aims to describe all words of all languages using definitions and descriptions in English.

# output:
# a [(1, 45), (1, 80)]
# aims [(2, 4)]
# all [(2, 21), (2, 34)]
# and [(2, 66)]
# collaborative [(1, 47)]
# content [(1, 87)]
# definitions [(2, 54)]
# ...

2.2. collections.defaultdict

  • A collections.defaultdict instance creates items with a default value on demand whenever a missing key is searched using d[k] syntax (__getitem__ calls, not for the other methods). When instantiating a defaultdict, you provide a callable to produce a default value whenever __getitem__ is passed a nonexistent key argument
  • If no default_factory is provided, the usual KeyError is raised for missing keys. The mechanism that makes defaultdict work by calling default_factory is the __missing__ special method
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import collections
import re

WORD_RE = re.compile(r'\w+')
# create a defaultdict with the list (callable) constructor as default_factory
index = collections.defaultdict(list)

with open("a.txt", encoding='utf-8') as fp:
    for line_no, line in enumerate(fp, 1):
        for match in WORD_RE.finditer(line):
            word = match.group()
            column_no = match.start() + 1
            location = (line_no, column_no)
            # if word is not initially in the index, the default_factory is called to produce the missing value
            index[word].append(location)

for word in sorted(index, key=str.upper):
    print(word, index[word])

2.3. The __missing__ Method

  • __missing__ method is not defined in the base dict class, but dict is aware of it: if you subclass dict and provide a __missing__ method, the standard dict.__getitem__ will call it whenever a key is not found, instead of raising KeyError
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
# inherit from dict. A better way is to subclass collections.UserDict
class StrKeyDict0(dict):
    def __missing__(self, key):
        # avoid infinite recursion
        if isinstance(key, str):
            raise KeyError(key)
        return self[str(key)]

    def get(self, key, default=None):
        try:
            # delegate to __getitem__
            return self[key]
        except KeyError:
            return default

    # operation k in d calls it, but the method inherited from dict does not fall back to invoking __missing__
    def __contains__(self, key):
        # `key in self` can cause infinite recursion
        return key in self.keys() or str(key) in self.keys()

d = StrKeyDict0([('2', 'two'), ('4', 'four')])
print(d['2'])  # two
print(d[4])  # four
#print(d[1])  # KeyError: '1'
print(d.get('2'))  # two
print(d.get(4))  # four
print(d.get(1, 'N/A'))  # N/A
print('2' in d)  # True
print(4 in d)  # True
print(1 in d)  # False
  • A search like k in my_dict.keys() is efficient in Python 3 even for very large mappings because dict.keys() returns a view, which is similar to a set. However, k in my_dict does the same job, and is faster because it avoids the attribute lookup to find the .keys method

2.4. Inconsistent Usage of __missing__ in the Standard Library

  • User-defined classes derived from standard library mappings may or may not use __missing__ as a fallback in their implementations of __getitem__, get, or __contains__:
    • dict subclass: A subclass of dict implementing only __missing__ and no other method. In this case, __missing__ may be called only on d[k], which will use the __getitem__ inherited from dict
    • collections.UserDict subclass: A subclass of UserDict implementing only __missing__ and no other method. The get method inherited from UserDict calls __getitem__. This means __missing__ may be called to handle lookups with d[k] and d.get(k)
    • abc.Mapping subclass with the simplest possible __getitem__: A minimal subclass of abc.Mapping implementing __missing__ and the required abstract methods, including an implementation of __getitem__ that does not call __missing__. The __missing__ method is never triggered in this class
    • abc.Mapping subclass with __getitem__ calling __missing__: A minimal subclass of abc.Mapping implementing __missing__ and the required abstract methods, including an implementation of __getitem__ that calls __missing__. The __missing__ method is triggered in this class for missing key lookups made with d[k], d.get(k), and k in d
  • The four scenarios just described assume minimal implementations. If your subclass implements __getitem__, get, and __contains__, then you can make those methods use __missing__ or not, depending on your needs

3. Other variations of dict

3.1. collections.OrderedDict

  • Now that the built-in dict also keeps the keys ordered since Python 3.6, the most common reason to use OrderedDict is writing code that is backward compatible with earlier Python versions. Having said that, Python’s documentation lists some remaining differences between dict and OrderedDict:
    • The equality operation for OrderedDict checks for matching order
    • The popitem() method of OrderedDict has a different signature. It accepts an optional argument to specify which item is popped
    • OrderedDict has a move_to_end() method to efficiently reposition an element to an endpoint
    • The regular dict was designed to be very good at mapping operations. Tracking insertion order was secondary
    • OrderedDict was designed to be good at reordering operations. Space efficiency, iteration speed, and the performance of update operations were secondary
    • Algorithmically, OrderedDict can handle frequent reordering operations better than dict. This makes it suitable for tracking recent accesses (for example, in an LRU cache)

3.2. collections.ChainMap

  • A ChainMap instance holds a list of mappings that can be searched as one. The lookup is performed on each input mapping in the order it appears in the constructor call, and succeeds as soon as the key is found in one of those mappings
  • The ChainMap instance does not copy the input mappings, but holds references to them. Updates or insertions to a ChainMap only affect the first input mapping
  • ChainMap is useful to implement interpreters for languages with nested scopes, where each mapping represents a scope context, from the innermost enclosing scope to the outermost scope
1
2
3
4
5
6
7
8
9
10
11
12
13
14
d1 = dict(a=1, b=3)
d2 = dict(a=2, b=4, c=6)

from collections import ChainMap
chain = ChainMap(d1, d2)
print(chain['a'])  # 1
print(chain['c'])  # 6

chain['c'] = -1
print(d1)  # {'a': 1, 'b': 3, 'c': -1}
print(d2)  # {'a': 2, 'b': 4, 'c': 6}

import builtins
pylookup = ChainMap(locals(), globals(), vars(builtins))

3.3. collections.Counter

  • A mapping that holds an integer count for each key. Updating an existing key adds to its count. This can be used to count instances of hashable objects or as a multiset. Counter implements the + and - operators to combine tallies, and other useful methods such as most_common([n]), which returns an ordered list of tuples with the n most common items and their counts
1
2
3
4
5
6
import collections
ct = collections.Counter('abracadabra')
print(ct)  # Counter({'a': 5, 'b': 2, 'r': 2, 'c': 1, 'd': 1})
ct.update('aaaaazzz')
print(ct)  # Counter({'a': 10, 'z': 3, 'b': 2, 'r': 2, 'c': 1, 'd': 1})
print(ct.most_common(3))  # [('a', 10), ('z', 3), ('b', 2)]

3.4. shelve.Shelf

  • The shelve module in the standard library provides persistent storage for a mapping of string keys to Python objects serialized in the pickle binary format. The shelve.open module-level function returns a shelve.Shelf instance—a simple key-value DBM database backed by the dbm module, with these characteristics:
    • shelve.Shelf subclasses abc.MutableMapping, so it provides the essential methods we expect of a mapping type
    • In addition, shelve.Shelf provides a few other I/O management methods, like sync and close
    • A Shelf instance is a context manager, so you can use a with block to make sure it is closed after use
    • Keys and values are saved whenever a new value is assigned to a key
    • The keys must be strings
    • The values must be objects that the pickle module can serialize
  • Python’s pickle is easy to use in the simplest cases, but has several drawbacks

3.5. Subclassing UserDict Instead of dict

  • The main reason why it’s better to subclass UserDict rather than dict is that the built-in has some implementation shortcuts that end up forcing us to override methods that we can just inherit from UserDict with no problems
  • UserDict does not inherit from dict, but uses composition: it has an internal dict instance, called data, which holds the actual items. This avoids undesired recursion when coding special methods like __setitem__, and simplifies the coding of __contains__
1
2
3
4
5
6
7
8
9
10
11
12
import collections
class StrKeyDict(collections.UserDict):
    def __missing__(self, key):
        if isinstance(key, str):
            raise KeyError(key)
        return self[str(key)]

    def __contains__(self, key):
        return str(key) in self.data

    def __setitem__(self, key, item):
        self.data[str(key)] = item
  • Because UserDict extends abc.MutableMapping, the remaining methods that make StrKeyDict a full-fledged mapping are inherited from UserDict, MutableMapping, or Mapping. The latter have several useful concrete methods, in spite of being abstract base classes (ABCs). The following methods are worth noting:
    • MutableMapping.update: This powerful method can be called directly but is also used by __init__ to load the instance from other mappings, from iterables of (key, value) pairs, and keyword arguments. Because it uses self[key] = value to add items, it ends up calling our implementation of __setitem__
    • Mapping.get: In StrKeyDict0, we had to code our own get to return the same results as __getitem__, but in StrKeyDict we inherited Mapping.get, which is implemented exactly like StrKeyDict0.get

3.6. Immutable Mappings

  • The types module provides a wrapper class called MappingProxyType, which, given a mapping, returns a mappingproxy instance that is a read-only but dynamic proxy for the original mapping. This means that updates to the original mapping can be seen in the mappingproxy, but changes cannot be made through it
1
2
3
4
5
6
7
8
9
from types import MappingProxyType
d = {1: 'A'}
d_proxy = MappingProxyType(d)
print(d_proxy)  # {1: 'A'}
print(d_proxy[1])  # 'A'
#d_proxy[2] = 'x'  # TypeError: 'mappingproxy' object does not support item assignment
d[2] = 'B'
print(d_proxy)  # {1: 'A', 2: 'B'}
print(d_proxy[2])  # 'B'

4. Sets

  • A set is a collection of unique objects. Set elements must be hashable. The set type is not hashable. But frozenset is hashable. In addition to enforcing uniqueness, the set types implement many set operations as infix operators, so, given two sets a and b, a | b returns their union, a & b computes the intersection, a - b the difference, and a ^ b the symmetric difference
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
l = ['spam', 'spam', 'eggs', 'spam', 'bacon', 'eggs']
print(set(l))  # {'eggs', 'spam', 'bacon'}
print(list(set(l)))  # ['eggs', 'spam', 'bacon']

# remove duplicates but also preserve the order
print(dict.fromkeys(l).keys())  # dict_keys(['spam', 'eggs', 'bacon'])
print(list(dict.fromkeys(l).keys()))  # ['spam', 'eggs', 'bacon']

needles = [-1, 4, 4, 7, 900]
haystack = [i for i in range(100)]
print(set(needles) & set(haystack))  # {4, 7}
print(set(needles).intersection(haystack))  # {4, 7}

# no literal notation for the empty set
#s = {}  # dict
s = set()
print(s)  # set()

# set uses the {…} notation
s = {1}
print(s)  # {1}
print(type(s))  # <class 'set'>
print(s.pop())  # 1
print(s)  # set()

from dis import dis
print(dis('{1}'))
#   1           2 LOAD_CONST               0 (1)
#               4 BUILD_SET                1
#               6 RETURN_VALUE
print(dis('set([1])'))
#   1           2 PUSH_NULL
#               4 LOAD_NAME                0 (set)  # fetch the constructor
#               6 LOAD_CONST               0 (1)
#               8 BUILD_LIST               1  # build a list
#              10 PRECALL                  1
#              14 CALL                     1  # pass it to the constructor
#              24 RETURN_VALUE

# no special syntax to represent frozenset literals
print(frozenset(range(10)))  # frozenset({0, 1, 2, 3, 4, 5, 6, 7, 8, 9})

# Set Comprehensions
from unicodedata import name
print({chr(i) for i in range(32, 256) if 'SIGN' in name(chr(i), '')})
# the order of the output changes for each Python process, because of the salted hash
# {'¬', '=', '¥', '°', '$', '#', '©', '<', '¢', '¶', '>', '±', '£', '÷', '×', '+', '¤', '§', 'µ', '®', '%'}
# {'+', '§', '¶', '>', '#', '×', '=', '¢', '%', 'µ', '¬', '©', '£', '¥', '°', '±', '<', '÷', '®', '$', '¤'}

4.1. Set Operations

MutableSet

  • Mathematical set operations:
Math symbol Python operator Method Description
S ∩ Z s & z s.__and__(z) Intersection of s and z
z & s s.__rand__(z) Reversed & operator
s.intersection(it, …) Intersection of s and all sets built from iterables it, etc.
s &= z s.__iand__(z) s updated with intersection of s and z
s.intersection_update(it, …) s updated with intersection of s and all sets built from iterables it, etc.
S ∪ Z s | z s.__or__(z) Union of s and z
z | s s.__ror__(z) Reversed | operator
s.union(it, …) Union of s and all sets built from iterables it, etc.
s |= z s.__ior__(z) s updated with union of s and z
s.update(it, …) s updated with union of s and all sets built from iterables it, etc.
S \ Z s - z s.__sub__(z) Relative complement or difference between s and z
z - s s.__rsub__(z) Reversed - operator
s.difference(it, …) Difference between s and all sets built from iterables it, etc.
s -= z s.__isub__(z) s updated with difference between s and z
s.difference_update(it, …) s updated with difference between s and all sets built from iterables it, etc.
S ∆ Z s ^ z s.__xor__(z) Symmetric difference (the complement of the intersection s & z)
z ^ s s.__rxor__(z) Reversed ^ operator
s.symmetric_difference(it) Complement of s & set(it)
s ^= z s.__ixor__(z) s updated with symmetric difference of s and z
s.symmetric_differ ence_update(it, …) s updated with symmetric difference of s and all sets built from iterables it, etc.
S ∩ Z = ∅ s.isdisjoint(z) s and z are disjoint (no elements in common)
e ∈ S e in s s.__contains__(e) Element e is a member of s
S ⊆ Z s <= z s.__le__(z) s is a subset of the z set
s.issubset(it) s is a subset of the set built from the iterable it
S ⊂ Z s < z s.__lt__(z) s is a proper subset of the z set
S ⊇ Z s >= z s.__ge__(z) s is a superset of the z set
s.issuperset(it) s is a superset of the set built from the iterable it
S ⊃ Z s > z s.__gt__(z) s is a proper superset of the z set
  • Additional set methods:
set frozenset
s.add(e) ● Add element e to s
s.clear() ● Remove all elements of s
s.copy() ● ● Shallow copy of s
s.discard(e) ● Remove element e from s if it is present
s.__iter__() ● ● Get iterator over s
s.__len__() ● ● len(s)
s.pop() ● Remove and return an element from s, raising KeyError if s is empty
s.remove(e) ● Remove element e from s, raising KeyError if e not in s
  • The infix operators require that both operands be sets, but all other methods take one or more iterable arguments. For example, to produce the union of four collections, a, b, c, and d, you can call a.union(b, c, d), where a must be a set, but b, c, and d can be iterables of any type that produce hashable items. If you need to create a new set with the union of four iterables, instead of updating an existing set, you can write {*a, *b, *c, *d}

4.2. Set Operations on dict Views

  • The view objects returned by the dict methods .keys() and .items() are remarkably similar to frozenset. In particular, dict_keys and dict_items implement the special methods to support the powerful set operators & (intersection), | (union), - (difference), and ^ (symmetric difference)
frozenset dict_keys dict_items Description
s.__and__(z) ● ● ● s & z (intersection of s and z)
s.__rand__(z) ● ● ● Reversed & operator
s.__contains__() ● ● ● e in s
s.copy() ● Shallow copy of s
s.difference(it, …) ● Difference between s and iterables it, etc.
s.intersection(it, …) ● Intersection of s and iterables it, etc.
s.isdisjoint(z) ● ● ● s and z are disjoint (no elements in common)
s.issubset(it) ● s is a subset of iterable it
s.issuperset(it) ● s is a superset of iterable it
s.__iter__() ● ● ● Get iterator over s
s.__len__() ● ● ● len(s)
s.__or__(z) ● ● ● s | z (union of s and z)
s.__ror__() ● ● ● Reversed | operator
s.__reversed__() ● ● Get iterator over s in reverse order
s.__rsub__(z) ● ● ● Reversed - operator
s.__sub__(z) ● ● ● s - z (difference between s and z)
s.symmetric_difference(it) ● Complement of s & set(it)
s.union(it, …) ● Union of s and iterables it, etc.
s.__xor__() ● ● ● s ^ z (symmetric difference of s and z)
s.__rxor__() ● ● ● Reversed ^ operator 
1
2
3
4
5
6
7
8
9
d1 = dict(a=1, b=2, c=3, d=4)
d2 = dict(b=20, d=40, e=[50])
s = {'a', 'e', 'i'}
# dict_keys view can always be used as a set
print(d1.keys())  # dict_keys(['a', 'b', 'c', 'd'])
print(d1.keys() & d2.keys())  # {'b', 'd'}
print(d1.keys() & s)  # {'a'}
# dict_items view only works as a set if all values in the dict are hashable
#print(d2.items() & s)  # TypeError: unhashable type: 'list'

4.3. How Sets Work

  • The set and frozenset types are both implemented with a hash table. This has these effects:
    • Set elements must be hashable objects. They must implement proper __hash__ and __eq__ methods
    • Membership testing is very efficient. A set may have millions of elements, but an element can be located directly by computing its hash code and deriving an index offset, with the possible overhead of a small number of tries to find a matching element or exhaust the search
    • Sets have a significant memory overhead, compared to a low-level array pointers to its elements—which would be more compact but also much slower to search beyond a handful of elements
    • Element ordering depends on insertion order, but not in a useful or reliable way. If two elements are different but have the same hash code, their position depends on which element is added first
    • Adding elements to a set may change the order of existing elements. That’s because the algorithm becomes less efficient if the hash table is more than two-thirds full, so Python may need to move and resize the table as it grows. When this happens, elements are reinserted and their relative ordering may change

References

  • Fluent Python