在线excel表格助力企业高效管理与数据分析的未来趋势
916
2022-05-29
常用 Python 数据结构（指南）
目录
字典、地图和哈希表
dict：您的首选词典
collections.OrderedDict：记住键的插入顺序
collections.defaultdict：为丢失的键返回默认值
collections.ChainMap：搜索多个字典作为单个映射
types.MappingProxyType：用于制作只读字典的包装器
Python 中的字典：总结
数组数据结构
列表：可变动态数组
元组：不可变容器
array.array：基本类型数组
str：Unicode 字符的不可变数组
bytes：不可变的单字节数组
bytearray：单字节的可变数组
Python 中的数组：总结
记录、结构和数据传输对象
dict：简单数据对象
元组：不可变对象组
编写自定义类：更多工作，更多控制
dataclasses.dataclass：Python 3.7+ 数据类
collections.namedtuple：方便的数据对象
Typing.NamedTuple：改进的命名元组
struct.Struct：序列化的 C 结构体
types.SimpleNamespace：花式属性访问
Python 中的记录、结构和数据对象：总结
集和多集
套装：您的首选套装
冻结集：不可变集
collections.Counter：Multisets
Python 中的集合和多重集：总结
堆栈 (LIFO)
列表：简单的内置堆栈
collections.deque：快速而健壮的堆栈
queue.LifoQueue：并行计算的锁定语义
Python 中的堆栈实现：总结
队列 (FIFO)
列表：非常慢的队列
collections.deque：快速而健壮的队列
queue.Queue：并行计算的锁定语义
multiprocessing.Queue：共享作业队列
Python 中的队列：总结
优先队列
列表：手动排序的队列
heapq：基于列表的二叉堆
queue.PriorityQueue：漂亮的优先队列
Python 中的优先队列：总结
结论：Python 数据结构
数据结构是您构建程序的基本结构。每种数据结构都提供了一种特定的数据组织方式，因此可以根据您的用例进行有效访问。Python 在其标准库中附带了一组广泛的数据结构。
但是，Python 的命名约定并没有提供您在其他语言中会发现的相同级别的清晰度。在Java 中，列表不仅仅是一个list——它是一个LinkedList或一个ArrayList。在 Python 中不是这样。即使是经验丰富的 Python 开发人员有时也会怀疑内置list类型是作为链表还是动态数组实现的。
在本教程中，您将学习：
Python标准库中内置了哪些常见的抽象数据类型
最常见的抽象数据类型如何映射到 Python 的命名方案
如何在各种算法中实际使用抽象数据类型
注意：本教程改编自Python Tricks: The Book 中的“Common Data Structures in Python”一章。如果您喜欢下面阅读的内容，请务必查看本书的其余部分。
字典、地图和哈希表
在 Python 中，字典（或简称为dicts）是一个中心数据结构。字典存储任意数量的对象，每个对象由唯一的字典键标识。
字典也常被称为映射、哈希映射、查找表或关联数组。它们允许对与给定键关联的任何对象进行有效的查找、插入和删除。
电话簿为字典对象提供了一个体面的现实世界模拟。它们允许您快速检索与给定键（人名）相关联的信息（电话号码）。不必前后翻阅电话簿才能找到某人的号码，您可以或多或少直接跳到一个姓名并查找相关信息。
当涉及到如何组织信息以允许快速查找时，这种类比会有所不同。但是基本的性能特征是成立的。字典允许您快速找到与给定键关联的信息。
字典是计算机科学中最重要和最常用的数据结构之一。那么，Python 是如何处理字典的呢？让我们来看看核心 Python 和 Python 标准库中可用的字典实现。
dict：您的首选词典
因为字典非常重要，Python 具有一个健壮的字典实现，它直接内置到核心语言中：dict数据类型。
Python 还提供了一些有用的语法糖，用于在程序中使用字典。例如，花括号 ({ }) 字典表达式语法和字典推导式允许您方便地定义新的字典对象：
>>>
>>> phonebook = { ... "bob": 7387, ... "alice": 3719, ... "jack": 7052, ... } >>> squares = {x: x * x for x in range(6)} >>> phonebook["alice"] 3719 >>> squares {0: 0, 1: 1, 2: 4, 3: 9, 4: 16, 5: 25}
哪些对象可以用作有效键有一些限制。
Python 的字典由可以是任何可散列类型的键索引。可散列对象的散列值在其生命周期内永远不会改变（请参阅__hash__），并且可以与其他对象进行比较（请参阅__eq__）。比较相等的可散列对象必须具有相同的散列值。
像字符串和数字这样的不可变类型是可散列的，并且可以很好地用作字典键。您也可以将tuple对象用作字典键，只要它们本身只包含可散列类型。
对于大多数用例，Python 的内置字典实现将完成您需要的一切。字典经过高度优化，是语言许多部分的基础。例如，堆栈帧中的类属性和变量都内部存储在字典中。
Python 字典基于经过充分测试和微调的哈希表实现，它提供了您期望的性能特征：O (1) 在一般情况下查找、插入、更新和删除操作的时间复杂度。
没有理由不使用dictPython 附带的标准实现。但是，存在专门的第三方词典实现，例如跳过列表或基于 B 树的词典。
除了普通dict对象，Python 的标准库还包括许多专门的字典实现。这些专用词典均基于内置词典类（并共享其性能特征），但还包括一些额外的便利功能。
让我们来看看它们。
collections.OrderedDict: 记住键的插入顺序
Python 包含一个专门的dict子类，它记住添加到其中的键的插入顺序：collections.OrderedDict.
注意： 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实例提供了该功能。即使在Python 3.8，dict而OrderedDict对象是不完全一样的。OrderedDict实例具有一种在普通实例上不可用的.move_to_end()方法，dict以及.popitem()一种比普通dict实例更可定制的方法。
collections.defaultdict: 为丢失的键返回默认值
本defaultdict类是接受它的构造函数，其返回值将被使用，如果被请求的密钥无法找到一个可调用另一个字典子类。
与在常规词典中使用get()或捕获KeyError异常相比，这可以为您节省一些输入并使您的意图更清晰：
>>>
>>> from collections import defaultdict >>> 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: 搜索多个字典作为单个映射
该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 "
types.MappingProxyType: 用于制作只读字典的包装器
MappingProxyType是标准字典的包装器，它提供了对包装字典数据的只读视图。这个类是在 Python 3.3 中添加的，可用于创建字典的不可变代理版本。
MappingProxyType例如，如果您想从类或模块返回带有内部状态的字典，同时不鼓励对该对象的写访问，这可能会有所帮助。UsingMappingProxyType允许您在不必首先创建字典的完整副本的情况下设置这些限制：
>>>
>>> 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 "
Python 中的字典：总结
本教程中列出的所有 Python 字典实现都是内置于 Python 标准库中的有效实现。
如果您正在寻找有关在程序中使用哪种映射类型的一般建议，我会向您指出内置dict数据类型。它是一种多功能且经过优化的哈希表实现，直接内置于核心语言中。
我建议您仅在有超出dict.
所有的实现都是有效的选项，但如果你的代码大部分时间依赖于标准的 Python 字典，它会更清晰、更容易维护。
数组数据结构
一个阵列是在大多数编程语言的基本数据结构可用的，并且它具有较宽的范围跨越不同的算法的用途。
在本节中，您将了解 Python 中的数组实现，这些实现仅使用 Python 标准库中包含的核心语言特性或功能。您将看到每种方法的优点和缺点，因此您可以决定哪种实现适合您的用例。
但在我们开始之前，让我们先介绍一些基础知识。数组是如何工作的，它们的用途是什么？数组由固定大小的数据记录组成，允许根据其索引有效地定位每个元素：
因为阵列中邻接的存储块存储的信息，他们认为连续的数据结构（相对于链接数据结构如链表，例如）。
数组数据结构在现实世界中的类比是停车场。您可以将停车场视为一个整体并将其视为单个对象，但在停车场内有由唯一编号索引的停车位。停车位是车辆的容器——每个停车位可以是空的，也可以是停放汽车、摩托车或其他车辆。
但并非所有停车场都一样。一些停车场可能仅限于一种类型的车辆。例如，房车停车场不允许停放自行车。受限停车场对应于类型化数组数据结构，该结构只允许存储具有相同数据类型的元素。
在性能方面，根据元素的索引查找包含在数组中的元素非常快。在这种情况下，正确的数组实现可保证恒定的O (1) 访问时间。
Python 在其标准库中包含了几个类似数组的数据结构，每个数据结构的特征都略有不同。让我们来看看。
list: 可变动态数组
列表是核心 Python 语言的一部分。尽管名称不同，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]
tuple: 不可变容器
就像列表一样，元组是 Python 核心语言的一部分。然而，与列表不同，Python 的tuple对象是不可变的。这意味着不能动态添加或删除元素——元组中的所有元素都必须在创建时定义。
元组是另一种可以保存任意数据类型元素的数据结构。拥有这种灵活性是强大的，但同样，这也意味着数据没有类型化数组那么紧密：
>>>
>>> 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 "
array.array: 基本类型数组
Python 的array模块为基本的 C 风格数据类型（如字节、32 位整数、浮点数等）提供节省空间的存储。
使用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 "
str: Unicode 字符的不可变数组
Python 3.x 使用str对象将文本数据存储为Unicode 字符的不可变序列。实际上，这意味着 astr是一个不可变的字符数组。奇怪的是，它也是一种递归数据结构——字符串中的每个字符本身都是一个str长度为 1的对象。
字符串对象是空间高效的，因为它们被紧密打包并且专门用于单一数据类型。如果要存储 Unicode 文本，则应使用字符串。
因为字符串在 Python 中是不可变的，所以修改字符串需要创建一个修改后的副本。与可变字符串最接近的等价物是将单个字符存储在列表中：
>>>
>>> arr = "abcd" >>> arr[1] 'b' >>> arr 'abcd' >>> # Strings are immutable: >>> arr[1] = "e" Traceback (most recent call last): File "
bytes: 不可变的单字节数组
bytes对象是单个字节的不可变序列，或者是 0 ≤ x ≤ 255范围内的整数。从概念上讲，bytes对象类似于str对象，您也可以将它们视为不可变的字节数组。
像字符串一样，bytes有自己的文字语法来创建对象并且节省空间。bytes对象是不可变的，但与字符串不同的是，有一个专用的可变字节数组数据类型，称为bytearray它们可以解压缩为：
>>>
>>> arr = bytes((0, 1, 2, 3)) >>> arr[1] 1 >>> # Bytes literals have their own syntax: >>> arr b'\x00\x01\x02\x03' >>> arr = b"\x00\x01\x02\x03" >>> # Only valid `bytes` are allowed: >>> bytes((0, 300)) Traceback (most recent call last): File "
bytearray: 单字节可变数组
的bytearray类型是一个整数的范围内的可变序列0≤ X ≤255。bytearray对象是密切相关的bytes对象，与主要区别在于一个bytearray可以被修改可自由可以覆盖元件，删除现有的元素，或添加新的那些。该bytearray对象将增长，并相应地缩小。
Abytearray可以转换回不可变bytes对象，但这涉及完整复制存储的数据 - 一个缓慢的操作需要O ( n ) 时间：
>>>
>>> arr = bytearray((0, 1, 2, 3)) >>> arr[1] 1 >>> # The bytearray repr: >>> arr bytearray(b'\x00\x01\x02\x03') >>> # Bytearrays are mutable: >>> arr[1] = 23 >>> arr bytearray(b'\x00\x17\x02\x03') >>> arr[1] 23 >>> # Bytearrays can grow and shrink in size: >>> del arr[1] >>> arr bytearray(b'\x00\x02\x03') >>> arr.append(42) >>> arr bytearray(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 "
Python 中的数组：总结
在 Python 中实现数组时，您可以选择许多内置数据结构。在本节中，您重点介绍了标准库中包含的核心语言功能和数据结构。
如果您愿意超越 Python 标准库，那么像NumPy和pandas这样的第三方包为科学计算和数据科学提供了广泛的快速数组实现。
如果你想限制自己使用 Python 包含的数组数据结构，那么这里有一些指导原则：
如果您需要存储任意对象，可能具有混合数据类型，则使用 alist或 a tuple，具体取决于您是否需要不可变数据结构。
如果您有数字（整数或浮点）数据并且紧密包装和性能很重要，那么试试array.array.
如果您将文本数据表示为 Unicode 字符，则使用 Python 的内置str. 如果你需要一个可变的类似字符串的数据结构，那么使用 a listof characters 。
如果要存储连续的字节块，请使用不可变bytes类型，bytearray如果需要可变数据结构，则使用a。
在大多数情况下，我喜欢从一个简单的list. 如果性能或存储空间成为问题，我将稍后专门研究。大多数时候，使用像这样的通用数组数据结构list会给你最快的开发速度和最大的编程方便。
我发现这通常在开始时比从一开始就试图挤出每一滴性能更重要。
记录、结构和数据传输对象
与数组相比，记录数据结构提供固定数量的字段。每个字段都可以有一个名称，也可以有不同的类型。
在本节中，您将看到如何仅使用标准库中的内置数据类型和类在 Python 中实现记录、结构和普通旧数据对象。
注意：我在这里松散地使用了记录的定义。例如，我还将讨论像 Python 内置的类型，这些类型tuple在严格意义上可能会也可能不会被视为记录，因为它们不提供命名字段。
Python 提供了多种数据类型，可用于实现记录、结构和数据传输对象。在本节中，您将快速了解每个实现及其独特的特性。最后，您会找到一份总结和一份决策指南，可帮助您做出自己的选择。
注意：本教程改编自Python Tricks: The Book 中的“Common Data Structures in Python”一章。如果您喜欢正在阅读的内容，请务必查看本书的其余部分。
好的，让我们开始吧！
dict: 简单数据对象
如所提及的先前，Python字典存储对象的任意数量，每一个都由唯一的密钥标识。字典也常被称为映射或关联数组，允许高效查找、插入和删除与给定键关联的任何对象。
在 Python 中使用字典作为记录数据类型或数据对象是可能的。字典在 Python 中很容易创建，因为它们以字典文字的形式在语言中内置了自己的语法糖。字典语法简洁，打字非常方便。
使用字典创建的数据对象是可变的，并且几乎没有针对拼写错误的字段名称的保护，因为字段可以随时自由添加和删除。这两个属性都会引入令人惊讶的错误，并且在便利性和错误恢复之间总是需要权衡：
>>>
>>> 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: 不可变的对象组
Python 的元组是一种用于对任意对象进行分组的简单数据结构。元组是不可变的——一旦创建就不能修改。
在性能方面，元组占用的内存比CPython 中的列表略少，而且它们的构造速度也更快。
正如你在下面的字节码反汇编中看到的，构造一个元组常量需要一个LOAD_CONST操作码，而构造一个具有相同内容的列表对象需要更多的操作：
>>>
>>> import dis >>> 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
但是，您不应过分强调这些差异。在实践中，性能差异通常可以忽略不计，并且试图通过从列表切换到元组来从程序中榨取额外的性能可能是错误的方法。
普通元组的一个潜在缺点是，您存储在其中的数据只能通过整数索引访问来提取。您不能为存储在元组中的单个属性命名。这会影响代码的可读性。
此外，元组始终是一种临时结构：很难确保两个元组具有相同数量的字段和存储在其中的相同属性。
这使得很容易引入不经意的错误，例如混淆字段顺序。因此，我建议您尽可能减少元组中存储的字段数：
>>>
>>> # 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] = 12 Traceback (most recent call last): File "
编写自定义类：更多工作，更多控制
类允许您为数据对象定义可重用的蓝图，以确保每个对象提供相同的字段集。
使用常规 Python 类作为记录数据类型是可行的，但也需要手动工作才能获得其他实现的便利功能。例如，向__init__构造函数添加新字段是冗长的并且需要时间。
此外，从自定义类实例化的对象的默认字符串表示形式也不是很有帮助。要解决这个问题，您可能必须添加自己的__repr__方法，这通常同样非常冗长，每次添加新字段时都必须更新。
存储在类中的字段是可变的，可以自由添加新字段，您可能喜欢也可能不喜欢。可以提供更多的访问控制并使用@property装饰器创建只读字段，但同样，这需要编写更多的胶水代码。
每当您想使用方法向记录对象添加业务逻辑和行为时，编写自定义类是一个很好的选择。但是，这意味着这些对象在技术上不再是纯数据对象：
>>>
>>> class Car: ... 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.mileage 40231.0 >>> # Classes are mutable: >>> car2.mileage = 12 >>> car2.windshield = "broken" >>> # String representation is not very useful >>> # (must add a manually written __repr__ method): >>> car1
dataclasses.dataclass：Python 3.7+ 数据类
数据类在 Python 3.7 及更高版本中可用。它们为从头开始定义您自己的数据存储类提供了一种极好的替代方法。
通过编写数据类而不是普通的 Python 类，您的对象实例可以获得一些开箱即用的有用功能，这将为您节省一些键入和手动实现的工作：
定义实例变量的语法更短，因为您不需要实现该.__init__()方法。
数据类的实例通过自动生成的.__repr__()方法自动获得漂亮的字符串表示。
实例变量接受类型注释，使您的数据类在一定程度上具有自文档性。请记住，类型注释只是提示，没有单独的类型检查工具就不会强制执行。
数据类通常使用@dataclass 装饰器创建，如下面的代码示例所示：
>>>
>>> from dataclasses import dataclass >>> @dataclass ... class Car: ... color: str ... mileage: float ... automatic: bool ... >>> car1 = Car("red", 3812.4, True) >>> # Instances have a nice repr: >>> car1 Car(color='red', mileage=3812.4, automatic=True) >>> # Accessing fields: >>> car1.mileage 3812.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)
要了解有关 Python 数据类的更多信息，请查看Python 3.7 中的数据类终极指南。
collections.namedtuple: 方便的数据对象
namedtuplePython 2.6+ 中可用的类提供了内置tuple数据类型的扩展。与定义自定义类类似， usingnamedtuple允许您为记录定义可重用的蓝图，以确保使用正确的字段名称。
namedtuple对象是不可变的，就像普通元组一样。这意味着您不能在namedtuple创建实例后添加新字段或修改现有字段。
除此之外，namedtuple对象是，嗯。. . 命名元组。存储在其中的每个对象都可以通过唯一标识符进行访问。这使您不必记住整数索引或求助于解决方法，例如将整数常量定义为索引的助记符。
namedtuple对象在内部实现为常规 Python 类。在内存使用方面，它们也比常规类更好，并且与常规元组一样具有内存效率：
>>>
>>> from collections import namedtuple >>> from sys import getsizeof >>> p1 = namedtuple("Point", "x y z")(1, 2, 3) >>> p2 = (1, 2, 3) >>> getsizeof(p1) 64 >>> getsizeof(p2) 64
namedtuple 对象可以是一种清理代码的简单方法，并通过为数据实施更好的结构使其更具可读性。
我发现从具有固定格式的字典等特殊数据类型到namedtuple对象有助于我更清楚地表达我的代码的意图。通常，当我应用这种重构时，我会神奇地为我面临的问题想出一个更好的解决方案。
namedtuple在常规（非结构化）元组和字典上使用对象还可以使传递的数据自我记录，至少在一定程度上使您的同事的生活更轻松：
>>>
>>> from collections import namedtuple >>> Car = namedtuple("Car" , "color mileage automatic") >>> car1 = Car("red", 3812.4, True) >>> # Instances have a nice repr: >>> car1 Car(color="red", mileage=3812.4, automatic=True) >>> # Accessing fields: >>> car1.mileage 3812.4 >>> # Fields are immtuable: >>> car1.mileage = 12 Traceback (most recent call last): File "
typing.NamedTuple: 改进的命名元组
在 Python 3.6 中添加，typing.NamedTuple是模块中namedtuple类的弟弟collections。它与 非常相似namedtuple，主要区别在于用于定义新记录类型的更新语法和增加了对类型提示的支持。
请注意，如果没有像mypy这样的单独类型检查工具，则不会强制执行类型注释。但即使没有工具支持，它们也可以为其他程序员提供有用的提示（如果类型提示过时，则会非常混乱）：
>>>
>>> from typing import NamedTuple >>> class Car(NamedTuple): ... color: str ... mileage: float ... automatic: bool >>> car1 = Car("red", 3812.4, True) >>> # Instances have a nice repr: >>> car1 Car(color='red', mileage=3812.4, automatic=True) >>> # Accessing fields: >>> car1.mileage 3812.4 >>> # Fields are immutable: >>> car1.mileage = 12 Traceback (most recent call last): File "
struct.Struct: 序列化的 C 结构
所述struct.Struct的Python值和C的结构之间转换类序列化到的Pythonbytes对象。例如，它可用于处理存储在文件中或来自网络连接的二进制数据。
结构是使用基于迷你语言定义的格式字符串，允许你定义各种C数据类型，如的安排char，int以及long以及其unsigned变种。
序列化结构很少用于表示纯粹在 Python 代码中处理的数据对象。它们主要用作数据交换格式，而不是作为一种仅由 Python 代码使用的将数据保存在内存中的方式。
在某些情况下，将原始数据打包到结构中可能比将其保留在其他数据类型中使用更少的内存。但是，在大多数情况下，这将是一种非常高级（并且可能是不必要的）优化：
>>>
>>> from struct import Struct >>> MyStruct = Struct("i?f") >>> data = MyStruct.pack(23, False, 42.0) >>> # All you get is a blob of data: >>> data b'\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: 花式属性访问
这是在 Python 中实现数据对象的另一种略显晦涩的选择：types.SimpleNamespace. 这个类是在 Python 3.3 中添加的，并提供对其命名空间的属性访问。
这意味着SimpleNamespace实例将其所有键公开为类属性。您可以使用obj.key点属性访问代替obj['key']常规字典使用的方括号索引语法。__repr__默认情况下，所有实例还包括一个有意义的。
顾名思义，SimpleNamespace简单！它基本上是一个允许属性访问和打印良好的字典。可以自由添加、修改和删除属性：
>>>
>>> from types import SimpleNamespace >>> car1 = SimpleNamespace(color="red", mileage=3812.4, automatic=True) >>> # The default repr: >>> car1 namespace(automatic=True, color='red', mileage=3812.4) >>> # Instances support attribute access and are mutable: >>> car1.mileage = 12 >>> car1.windshield = "broken" >>> del car1.automatic >>> car1 namespace(color='red', mileage=12, windshield='broken')
Python 中的记录、结构和数据对象：总结
如您所见，实现记录或数据对象有很多不同的选项。你应该为 Python 中的数据对象使用哪种类型？通常，您的决定将取决于您的用例：
如果您只有几个字段，那么如果字段顺序易于记忆或字段名称是多余的，则使用纯元组对象可能没问题。例如，考虑(x, y, z)三维空间中的一个点。
如果您需要不可变字段，那么纯元组collections.namedtuple、 和typing.NamedTuple都是不错的选择。
如果您需要锁定字段名称以避免拼写错误，那么collections.namedtuple和typing.NamedTuple就是您的朋友。
如果您想让事情保持简单，那么简单的字典对象可能是一个不错的选择，因为它的语法非常类似于JSON。
如果您需要完全控制您的数据结构，那么是时候使用@propertysetter 和 getter编写自定义类了。
如果您需要向对象添加行为（方法），那么您应该从头开始编写自定义类，或者使用dataclass装饰器，或者通过扩展collections.namedtuple或typing.NamedTuple。
如果您需要将数据紧密打包以将其序列化到磁盘或通过网络发送，那么是时候继续阅读了，struct.Struct因为这是一个很好的用例！
如果您正在寻找安全的默认选择，那么我在 Python 中实现普通记录、结构或数据对象的一般建议是collections.namedtuple在 Python 2.x 及其更小的兄弟typing.NamedTuplePython 3 中使用。
集和多集
在本节中，您将看到如何使用标准库中的内置数据类型和类在 Python 中实现可变和不可变的集合和多集（袋）数据结构。
一组是不允许重复元素的对象的无序集合。通常，集合用于快速测试集合中成员的值，从集合中插入或删除新值，以及计算两个集合的并集或交集。
在适当的集合实现中，成员资格测试预计在快速O (1) 时间内运行。并、交、差和子集操作平均需要O ( n ) 时间。Python 标准库中包含的集合实现遵循这些性能特征。
就像字典一样，集合在 Python 中得到了特殊处理，并且有一些语法糖，使它们易于创建。例如，花括号集合表达式语法和集合推导式允许您方便地定义新的集合实例：
vowels = {"a", "e", "i", "o", "u"} squares = {x * x for x in range(10)}
但要小心：要创建一个空集，您需要调用set()构造函数。使用空花括号 ( {}) 是不明确的，而是会创建一个空字典。
Python 及其标准库提供了几个集合实现。让我们来看看它们。
set：您的首选套装
该set类型是在Python内置集的实现。它是可变的，并允许动态插入和删除元素。
Python 的集合由dict数据类型支持并共享相同的性能特征。任何可散列对象都可以存储在一个集合中：
>>>
>>> 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类实现的不可变版本set不能后更改的被构建。
frozenset对象是静态的，只允许对其元素进行查询操作，而不是插入或删除。因为frozenset对象是静态且可散列的，所以它们可以用作字典键或另一个集合的元素，这是常规（可变）set对象无法实现的：
>>>
>>> vowels = frozenset({"a", "e", "i", "o", "u"}) >>> vowels.add("p") Traceback (most recent call last): File "
collections.Counter: 多组
collections.CounterPython 标准库中的类实现了多集或包类型，允许集合中的元素出现多次。
如果你需要保持跟踪这不仅是有用，如果一个元素是一组的一部分，但也多少次它包含在集：
>>>
>>> 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})
Counter该类的一个警告是，在计算Counter对象中元素的数量时要小心。调用len()返回多集中唯一元素的数量，而可以使用以下方法检索元素总数sum()：
>>>
>>> len(inventory) 3 # Unique elements >>> sum(inventory.values()) 6 # Total no. of elements
Python 中的集合和多重集：总结
集合是 Python 及其标准库中包含的另一种有用且常用的数据结构。以下是决定使用哪一个的一些准则：
如果您需要可变集，请使用内置set类型。
如果您需要可用作字典或设置键的可散列对象，请使用frozenset.
如果您需要多集或包数据结构，请使用collections.Counter.
堆栈 (LIFO)
甲堆是对象的集合，支持快速后进/先出（LIFO）语义插入和删除。与列表或数组不同，堆栈通常不允许随机访问它们包含的对象。插入和删除操作通常也称为push和pop。
堆栈数据结构的一个有用的现实世界类比是一堆盘子。新的盘子被添加到堆栈的顶部，由于盘子又贵又重，只能移动最上面的盘子。换句话说，堆栈中的最后一个板必须是第一个移除的 (LIFO)。要到达堆栈中较低的板，必须将最顶部的板一一移除。
在性能方面，正确的堆栈实现预计需要O (1) 时间进行插入和删除操作。
堆栈在算法中有广泛的用途。例如，它们用于语言解析以及依赖于调用堆栈的运行时内存管理。使用堆栈的一种简短而美观的算法是对树或图形数据结构的深度优先搜索(DFS)。
Python 附带了几个堆栈实现，每个实现的特性略有不同。让我们来看看它们并比较它们的特性。
list：简单的内置堆栈
Python 的内置list类型构成了一个不错的堆栈数据结构，因为它支持分摊 O (1) 时间的push 和 pop 操作。
Python 的列表在内部实现为动态数组，这意味着当添加或删除元素时，它们偶尔需要调整存储在其中的元素的存储空间大小。该列表过度分配了其后备存储，因此并非每次推送或弹出都需要调整大小。因此，这些操作的分摊时间复杂度为O (1)。
不利的一面是，这使得它们的性能不如基于链表的实现提供的稳定的O (1) 插入和删除（如下面的collections.deque）。另一方面，列表确实提供了对堆栈上元素的快速O (1) 时间随机访问，这可能是一个额外的好处。
使用列表作为堆栈时，您应该注意一个重要的性能警告：为了获得插入和删除的分摊O (1) 性能，必须使用该方法将新项目添加到列表的末尾，append()并再次从列表中删除结束使用pop(). 为了获得最佳性能，基于 Python 列表的堆栈应该向更高的索引增长并向更低的索引收缩。
从前面添加和删除要慢得多并且需要O ( n ) 时间，因为必须移动现有元素为新元素腾出空间。这是您应该尽可能避免的性能反模式：
>>>
>>> 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 "
collections.deque：快速而健壮的堆栈
所述deque类实现一个双端队列支持添加和去除从任一端元件Ô（1）时间（非摊销）。由于双端队列同样支持从任一端添加和删除元素，因此它们既可以用作队列，也可以用作堆栈。
Python 的deque对象被实现为双向链表，这使它们在插入和删除元素方面具有出色且一致的性能，但在随机访问堆栈中间的元素方面的O ( n ) 性能较差。
总的来说，如果您正在 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 "
queue.LifoQueue: 并行计算的锁定语义
LifoQueuePython 标准库中的堆栈实现是同步的，并提供锁定语义以支持多个并发生产者和消费者。
此外LifoQueue，该queue模块还包含其他几个实现多生产者、多消费者队列的类，这些队列对并行计算很有用。
根据您的用例，锁定语义可能会有所帮助，或者它们可能只会产生不必要的开销。在这种情况下，最好使用 alist或 adeque作为通用堆栈：
>>>
>>> from queue import LifoQueue >>> s = LifoQueue() >>> s.put("eat") >>> s.put("sleep") >>> s.put("code") >>> s
Python 中的堆栈实现：总结
如您所见，Python 附带了多种堆栈数据结构的实现。它们都具有略有不同的特性以及性能和使用权衡。
如果您不是在寻找并行处理支持（或者如果您不想手动处理锁定和解锁），那么您的选择归结为内置list类型或collections.deque. 不同之处在于幕后使用的数据结构和整体易用性。
list 由动态数组支持，这使得它非常适合快速随机访问，但在添加或删除元素时需要偶尔调整大小。
该列表过度分配了其后备存储，因此并非每个推送或弹出都需要调整大小，并且这些操作的分摊时间复杂度为O (1)。但是您确实需要小心，只能使用append()and插入和删除项目pop()。否则，性能会降低到O ( n )。
collections.deque由双向链表支持，它优化了两端的追加和删除，并为这些操作提供一致的O (1) 性能。不仅其性能更稳定，deque该类也更易于使用，因为您不必担心从错误的一端添加或删除项目。
总之，collections.deque是在 Python 中实现堆栈（LIFO 队列）的绝佳选择。
队列 (FIFO)
在本节中，您将了解如何仅使用 Python 标准库中的内置数据类型和类来实现先进/先出(FIFO) 队列数据结构。
甲队列是对象的集合支持用于插入和删除快速FIFO语义。插入和删除操作有时称为入队和出队。与列表或数组不同，队列通常不允许随机访问它们包含的对象。
这是一个真实世界的 FIFO 队列类比：
想象一下，在 PyCon 注册的第一天，一群 Pythonistas 正在等待领取他们的会议徽章。当新人进入会场并排队领取胸卡时，他们会在队列的后面加入队伍（排队）。开发人员收到他们的徽章和会议赃物袋，然后在队列的前面退出队列（出队）。
记住队列数据结构特征的另一种方法是将其视为管道。您在一端添加乒乓球，然后它们移动到另一端，在那里您将它们移除。当球在队列中（一根坚固的金属管）时，你无法拿到它们。与队列中的球交互的唯一方法是在管道的后面添加新的（入队）或在前面删除它们（出队）。
队列类似于栈。它们之间的区别在于如何删除项目。随着队列，你删除该项目至少最近添加（FIFO），但有一个堆栈，你删除的项最最近添加（LIFO）。
在性能方面，正确的队列实现预计需要O (1) 时间来进行插入和删除操作。这是对队列执行的两个主要操作，在正确的实现中，它们应该很快。
队列在算法中有广泛的应用，通常有助于解决调度和并行编程问题。使用队列的一种简短而美观的算法是对树或图数据结构的广度优先搜索(BFS)。
调度算法通常在内部使用优先级队列。这些是专门的队列。代替通过插入时间检索的下一个元素的，一个优先级队列中检索最高优先级的元素。单个元素的优先级由队列根据应用于它们的键的顺序决定。
但是，常规队列不会对其携带的项目重新排序。就像在管道示例中一样，您取出放入的内容，并且完全按照该顺序。
Python 附带了几个队列实现，每个实现的特性略有不同。让我们回顾一下它们。
list：非常慢的队列
可以将常规list用作 queue，但从性能角度来看这并不理想。为此，列表非常慢，因为在开头插入或删除一个元素需要将所有其他元素移动一个，需要O ( n ) 时间。
因此，除非您只处理少量元素，否则我不建议将 alist用作 Python 中的临时队列：
>>>
>>> q = [] >>> q.append("eat") >>> q.append("sleep") >>> q.append("code") >>> q ['eat', 'sleep', 'code'] >>> # Careful: This is slow! >>> q.pop(0) 'eat'
collections.deque：快速而健壮的队列
所述deque类实现一个双端队列支持添加和去除从任一端元件Ô（1）时间（非摊销）。由于双端队列同样支持从任一端添加和删除元素，因此它们既可以用作队列，也可以用作堆栈。
Python 的deque对象被实现为双向链表。这使他们用于插入和删除元素优良和稳定的性能，但差ø（Ñ用于随机访问在堆栈的中间元件）的性能。
因此，collections.deque如果您正在 Python 的标准库中寻找队列数据结构，这是一个很好的默认选择：
>>>
>>> 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 "
queue.Queue: 并行计算的锁定语义
queue.QueuePython 标准库中的实现是同步的，并提供锁定语义以支持多个并发生产者和消费者。
该queue模块包含其他几个实现多生产者、多消费者队列的类，这些队列对并行计算很有用。
根据您的用例，锁定语义可能会有所帮助，或者只会产生不必要的开销。在这种情况下，您最好将其collections.deque用作通用队列：
>>>
>>> from queue import Queue >>> q = Queue() >>> q.put("eat") >>> q.put("sleep") >>> q.put("code") >>> q
multiprocessing.Queue: 共享作业队列
multiprocessing.Queue是一个共享的作业队列实现，允许多个并发工作人员并行处理排队的项目。基于进程的并行化在 CPython 中很流行，因为全局解释器锁(GIL) 可以防止在单个解释器进程上进行某些形式的并行执行。
作为用于在进程之间共享数据的专用队列实现，multiprocessing.Queue可以轻松地跨多个进程分发工作以解决 GIL 限制。这种类型的队列可以跨进程边界存储和传输任何可腌制的对象：
>>>
>>> from multiprocessing import Queue >>> q = Queue() >>> q.put("eat") >>> q.put("sleep") >>> q.put("code") >>> q
Python 中的队列：总结
Python 包括几个队列实现作为核心语言及其标准库的一部分。
list 对象可以用作队列，但由于性能缓慢，通常不建议这样做。
如果您不是在寻找并行处理支持，那么提供的collections.deque实现是在 Python 中实现 FIFO 队列数据结构的绝佳默认选择。它提供了您期望从一个好的队列实现中获得的性能特征，也可以用作堆栈（LIFO 队列）。
优先队列
一个优先级队列是管理一组与记录的容器数据结构完全有序键提供快速访问记录中，设定的最小或最大关键。
您可以将优先级队列视为修改后的队列。它不是按插入时间检索下一个元素，而是检索最高优先级的元素。各个元素的优先级由应用于它们的键的顺序决定。
优先级队列通常用于处理调度问题。例如，您可以使用它们来优先处理具有更高紧迫性的任务。
想想操作系统任务调度程序的工作：
理想情况下，系统上优先级较高的任务（例如玩实时游戏）应优先于优先级较低的任务（例如在后台下载更新）。通过将待处理的任务组织在以任务紧迫性为关键的优先级队列中，任务调度器可以快速选择优先级最高的任务并让它们先运行。
在本节中，您将看到一些关于如何使用 Python 标准库中包含的内置数据结构或数据结构在 Python 中实现优先级队列的选项。每个实现都有自己的优点和缺点，但在我看来，大多数常见场景都有明显的赢家。让我们找出它是哪一个。
list: 手动排序队列
您可以使用 sortedlist来快速识别和删除最小或最大元素。缺点是将新元素插入列表是一个缓慢的O ( n ) 操作。
虽然在标准库中可以在O (log n ) 时间内找到插入点bisect.insort，但这总是由缓慢的插入步骤决定。
通过附加到列表和重新排序来维护顺序也至少需要O ( n log n ) 时间。另一个缺点是您必须在插入新元素时手动处理列表的重新排序。错过这一步很容易引入错误，而负担始终落在开发人员身上。
这意味着排序列表仅适用于插入很少的优先级队列：
>>>
>>> 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是一个二进制堆实现，通常由一个普通的list支持，它支持在O (log n ) 时间内插入和提取最小元素。
该模块是在 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内部使用并共享相同的时间和空间复杂性。不同之处在于PriorityQueue同步并提供锁定语义以支持多个并发生产者和消费者。
根据您的用例，这可能会有所帮助，或者它可能只是稍微减慢您的程序速度。在任何情况下，您可能更喜欢 提供的基于类的接口而PriorityQueue不是提供的基于函数的接口heapq：
>>>
>>> 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')
Python 中的优先队列：总结
Python 包括几个可供您使用的优先级队列实现。
queue.PriorityQueue以一个漂亮的面向对象的界面和一个明确说明其意图的名称脱颖而出。它应该是您的首选。
如果您想避免 的锁定开销queue.PriorityQueue，那么heapq直接使用该模块也是一个不错的选择。
结论：Python 数据结构
您对 Python 中常见数据结构的浏览到此结束。凭借您在此处获得的知识，您已准备好实施适合您的特定算法或用例的高效数据结构。
在本教程中，您学习了：
Python标准库中内置了哪些常见的抽象数据类型
最常见的抽象数据类型如何映射到 Python 的命名方案
如何在各种算法中实际使用抽象数据类型
如果您喜欢从Python Tricks 的这个示例中学到的东西，那么一定要查看本书的其余部分。
Python 数据结构
版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。
相关文章
推荐文章
最近发表
