原文链接：Common Python Data Structures (Guide)

在我们开始学习Python的时，,内置的数据结构List,Tuple,Dictionary,Set已足够我们使用。

但是随着实践的深入，我们需要构建的数据结构就会越来越复杂，在此文中，我将向您介绍更多实用的，包含在标准库的Python数据结构，熟悉它们将帮助您更好的构建代码。

Dictionaries, Maps与 Hash Tables

在Python中，字典（或简称为dict）是中央数据结构（central data structure）。字典存储任意数量的对象，每个对象都由唯一的字典键标识。

字典通常也称为映射，哈希图，查找表或关联数组。它们允许有效查找，插入和删除与给定键关联的任何对象。

dict

Python还提供了一些有用的语法糖，用于在程序中使用字典。例如，字典表达式：

>>> squares = {x: x * x for x in range(6)}
>>> squares
{0: 0, 1: 1, 2: 4, 3: 9, 4: 16, 5: 25}

对于大多数使用情况，Python的内置字典实现将满足您的所有需求。字典经过了高度优化，并构成语言的许多部分。例如，堆栈框架中的类属性和变量都存储在内部字典中。

ython字典基于经过良好测试和精心调整的哈希表实现，可提供您期望的性能特征：平均情况下查找，插入，更新和删除操作O(1)的时间复杂度。

除了普通dict对象之外，Python的标准库还包括许多专用的字典实现。这些专业词典均基于内置词典类（并具有其性能特征），但还包含一些其他便利功能。

collections.OrderedDict：记住键的插入顺序

Python包含一个专门的dict子类，该子类记住添加到它的键的插入顺序：collections.OrderedDict(必须从collections标准库中的模块中导入)。

尽管标准dict在CPython 3.6及更高版本中保留了键的插入顺序，但这只是CPython实现的副作用，并且直到Python 3.7才在语言规范中定义。因此，如果键顺序对于算法的工作很重要，那么最好通过显式使用OrderedDict类来明确传达这一点：

>>> import collections
>>> d = collections.OrderedDict(one=1, two=2, three=3)

>>> d
OrderedDict([('one', 1), ('two', 2), ('three', 3)])

>>> d["four"] = 4
>>> d
OrderedDict([('one', 1), ('two', 2),
             ('three', 3), ('four', 4)])

>>> d.keys()
odict_keys(['one', 'two', 'three', 'four'])

在Python 3.8之前，您无法使用reversed()反向遍历字典项。仅OrderedDict实例提供该功能。

collections.defaultdict：返回缺少键的默认值

dict查找的key不存在的时候就会报KeyError，一般我们会使用dict.setdefault()函数来解决这个问题。但是，defaultdict提供了更优雅的解决方式，一开始就指定了默认值：

>>> from collections import defaultdict
>>> dd = defaultdict(list) #指定默认值为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']
>>> dd["cats"]
[]

collections.ChainMap：将多个词典作为一个映射进行搜索

collections.ChainMap数据结构组多个词典成一个单一的的映射。查找则会搜索多个映射，直到找到一个键。插入，更新和删除仅影响添加到链中的第一个映射：

>>> from collections import ChainMap
>>> dict1 = {"one": 1, "two": 2}
>>> dict2 = {"three": 3, "four": 4}
>>> chain = ChainMap(dict1, dict2)

>>> chain
ChainMap({'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>", line 1, in <module>
KeyError: 'missing'

types.MappingProxyType：不可变映射类型

python3.3开始,types模块中引入了一个封装类名叫MappingProxyType，如果给这个类一个映射,它会返回一个只读映射视图。
虽然是个只读的视图,但是它是动态的,这意味着如果对原映射做出了改动,我们可以通过这个视图观察到,但是无法通过这个视图对原映射做出修改。
使用场景，如果您想从类或模块中返回携带内部状态的字典，同时又不鼓励对该对象进行写访问：

>>> from types import MappingProxyType
>>> writable = {"one": 1, "two": 2}
>>> read_only = MappingProxyType(writable)

>>> # The proxy is read-only:
>>> read_only["one"]
1
>>> read_only["one"] = 23
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: 'mappingproxy' object does not support item assignment

>>> # Updates to the original are reflected in the proxy:
>>> writable["one"] = 42
>>> read_only
mappingproxy({'one': 42, 'two': 2})

Array

在性能方面，给定元素的索引，查找数组中包含的元素非常快。适当的数组实现可确保在这种情况下具有恒定的O(1)访问时间。

Python在其标准库中包含几种类似数组的数据结构，每种结构都具有稍微不同的特征，让我们来看看。

list：可变动态数组

list列表是Python核心语言的一部分。尽管名称如此，但Python的列表使用动态数组作为后台实现的。

这意味着列表允许添加或删除元素，并且列表将通过分配或释放内存来自动调整保存这些元素的后备存储。

Python列表可以包含任意元素，包括函数。因此，您可以混合和匹配不同种类的数据类型，并将它们全部存储在一个列表中。这可能是一个强大的功能，但缺点是同时支持多种数据类型意味着数据的打包通常不太紧密。结果，整个结构占用更多空间：

>>> 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']

>>> del arr[1]
>>> arr
['one', 'three']

>>> # Lists can hold arbitrary data types:
>>> arr.append(23)
>>> arr
['one', 'three', 23]

array.array：基本类型数组

用array.array该类创建的数组是可变的，但是，它们是类型化的数组，被约束为单个数据类型。

由于此约束，array.array比列表和元组具有更高的空间利用率。存储在其中的元素紧密包装，如果您需要存储许多相同类型的元素，array.array将很有用。

此外，数组支持许多与常规列表相同的方法，并且您可以将它们用作直接替换，而无需对应用程序代码进行其他更改。

>>> import array
>>> arr = array.array("f", (1.0, 1.5, 2.0, 2.5))
>>> arr[1]
1.5

>>> # Arrays have a nice repr:
>>> arr
array('f', [1.0, 1.5, 2.0, 2.5])

>>> # Arrays are mutable:
>>> arr[1] = 23.0
>>> arr
array('f', [1.0, 23.0, 2.0, 2.5])

>>> del arr[1]
>>> arr
array('f', [1.0, 2.0, 2.5])

>>> arr.append(42.0)
>>> arr
array('f', [1.0, 2.0, 2.5, 42.0])

>>> # Arrays are "typed":
>>> arr[1] = "hello"
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: must be real number, not str

Sets 与 Multisets

set类型是Python中的内置set实现。它是可变的，并允许动态插入和删除元素。任何可哈希对象都可以存储在一个集中：

>>> vowels = {"a", "e", "i", "o", "u"}
>>> "e" in vowels
True

>>> letters = set("alice")
>>> letters.intersection(vowels)
{'a', 'e', 'i'}

>>> vowels.add("x")
>>> vowels
{'i', 'a', 'u', 'o', 'x', 'e'}

>>> len(vowels)
6

frozenset：不可变集

frozenset对象是静态的，并且仅允许对其元素进行查询操作，而不能进行插入或删除操作。因为frozenset对象是静态且可哈希的，所以它们可以用作字典键或用作另一个集合的元素，而常规（可变）set对象则无法实现：

>>> vowels = frozenset({"a", "e", "i", "o", "u"})
>>> vowels.add("p")
Traceback (most recent call last):
  File "<stdin>", line 1, 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：多集

Python标准库中的collections.Counter类实现了一种多集或袋类型，该类型允许集合中的元素出现多次。

>>> from collections import Counter
>>> inventory = Counter()

>>> loot = {"sword": 1, "bread": 3}
>>> inventory.update(loot)
>>> inventory
Counter({'bread': 3, 'sword': 1})

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

调用len()返回多集中唯一元素的数量，而元素的总数可以使用sum()来检索：

>>> len(inventory)
3  # Unique elements

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

Stacks (LIFO) 堆栈

堆是对象的集合，支持快速后进/先出（LIFO）语义插入和删除。与列表或数组不同，堆栈通常不允许随机访问其中包含的对象。插入和删除操作通常也称为push和pop。

在性能方面，正确的堆栈实现预期将花费O(1)时间进行插入和删除操作。

堆栈在算法中有广泛的用途。例如，它们用于语言解析以及运行时内存管理中，后者依赖于调用堆栈。使用堆栈的简短而美观的算法是在树或图数据结构上进行深度优先搜索（DFS）。

Python附带了几个堆栈实现，每个实现都有一些稍有不同的特性。让我们看看它们并比较它们的特征。

list：简单的内置堆栈

Python的内置list类型构成了不错的堆栈数据结构，因为它支持摊销 O(1)时间内的推入和弹出操作。

>>> 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>", line 1, in <module>
IndexError: pop from empty list

collections.deque：快速且稳定的堆栈

如果您要在Python标准库中寻找具有链接列表实现的性能特征的堆栈数据结构，collections.deque则是一个不错的选择：

>>> from collections import deque
>>> s = deque()
>>> s.append("eat")
>>> s.append("sleep")
>>> s.append("code")

>>> s
deque(['eat', 'sleep', 'code'])

>>> s.pop()
'code'
>>> s.pop()
'sleep'
>>> s.pop()
'eat'

>>> s.pop()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
IndexError: pop from an empty deque

collections.deque由双向链表支持，该链表优化了两端的追加和删除，并为这些操作提供了一致的O（1）性能。deque该类不仅性能更稳定，而且更易于使用，因为您不必担心在错误的一端添加或删除项。

总之，这collections.deque是在Python中实现堆栈（LIFO队列）的绝佳选择。

Queues（FIFO）队列

队列是对象的集合支持用于插入和删除快速FIFO语义。插入和删除操作有时称为enqueue和dequeue。与列表或数组不同，队列通常不允许随机访问它们包含的对象。

list：非常Sloooow的队列

可以将常规list用作队列，但是从性能角度来看，这不是理想的选择。用做队列的列表非常慢，因为在开头插入或删除一个元素需要将所有其他元素移位，需要O（n）的时间。

因此，除非您只处理少量元素，否则我建议不要在Python中使用list作为临时队列。

>>> q = []
>>> q.append("eat")
>>> q.append("sleep")
>>> q.append("code")

>>> q
['eat', 'sleep', 'code']

>>> # Careful: This is slow!
>>> q.pop(0)
'eat'

collections.deque：快速且健壮的队列

由于双端队列很好地支持从任一端添加和删除元素，因此它们既可以用作队列也可以用作堆栈。

Python的deque对象被实现为双链表。这使它们在插入和删除元素方面具有出色且一致的性能，但对于在堆栈中间随机访问元素的性能较差需要O（n）时间。

如果要在Python的标准库中查找队列数据结构，则collections.deque是一个不错的默认选择：

>>> from collections import deque
>>> q = deque()
>>> q.append("eat")
>>> q.append("sleep")
>>> q.append("code")

>>> q
deque(['eat', 'sleep', 'code'])

>>> q.popleft()
'eat'
>>> q.popleft()
'sleep'
>>> q.popleft()
'code'

>>> q.popleft()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
IndexError: pop from an empty deque

queue.Queue：支持锁和并行计算

Python标准库中queue.Queue的实现是同步的，并提供锁定语义以支持多个并发的生产者和使用者。

该queue模块包含其他几个实现多生产者，多消费者队列的类，这些类对于并行计算很有用。

根据您的用例，锁定语义可能会有所帮助，或者只是产生不必要的开销。在这种情况下，最好将其collections.deque用作通用队列：

>>> from queue import Queue
>>> 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：共享作业队列

multiprocessing.Queue是一种共享作业队列实现，它允许多个并发工作进程并行处理排队的项目。基于进程的并行化在CPython中很流行，这是因为全局解释器锁（GIL）防止在单个解释器进程上，进行某种形式的并行执行。

作为专门的队列实现，它意味着multiprocessing.Queue在进程之间共享数据，可以轻松地在多个进程之间分配工作，以解决GIL限制。这种队列可以跨进程边界存储和传输任何pickleable对象：

>>> from multiprocessing import Queue
>>> 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...

Priority Queues优先队列

优先队列通常用于处理调度问题。

考虑一下操作系统任务调度程序的工作：

理想情况下，系统上较高优先级的任务（例如玩实时游戏）应优先于较低优先级的任务（例如在后台下载更新）。通过将使用任务紧急性作为关键字的优先级队列组织待处理的任务，任务计划程序可以快速选择优先级最高的任务，并允许它们首先运行。

list：手动排序的队列

您可以使用排序list来快速识别和删除最小或最大元素。

排序列表仅在插入次数很少时才适合作为优先级队列：

>>> 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)

>>> while q:
...     next_item = q.pop()
...     print(next_item)
...
(1, 'eat')
(2, 'code')
(3, 'sleep')

heapq：基于列表的二进制堆

heapq模块是在Python中实现优先级队列的不错选择。从技术上讲,heapq仅提供最小堆实现，因此必须采取额外的步骤来确保排序稳定性和实际优先级队列通常期望的其他功能：

>>> import heapq
>>> q = []
>>> heapq.heappush(q, (2, "code"))
>>> heapq.heappush(q, (1, "eat"))
>>> heapq.heappush(q, (3, "sleep"))

>>> while q:
...     next_item = heapq.heappop(q)
...     print(next_item)
...
(1, 'eat')
(2, 'code')
(3, 'sleep')

queue.PriorityQueue：最佳优先级队列

queue.PriorityQueue在内部使用了heapq，并和heapq具有相同的时间和空间复杂性。区别在于，PriorityQueue是同步的，并提供锁定语义，它支持多个并发的生产者和使用者：

>>> from queue import PriorityQueue
>>> q = PriorityQueue()
>>> q.put((2, "code"))
>>> q.put((1, "eat"))
>>> q.put((3, "sleep"))

>>> while not q.empty():
...     next_item = q.get()
...     print(next_item)
...
(1, 'eat')
(2, 'code')
(3, 'sleep')