Python中的数据结构

前言

其实忙碌的期末周已经过去一个星期多了，但是我又咸🐟了整整一个星期没在学习所以导致博客断更了好长一段时间www
正好学到了Python中的数据结构，而我也有复习数据结构的打算，所以很快啊，我就来水（bushi）博文了。
Python中的数据结构其实挺多的，而且不像其它语言一样，比如Java中就把列表分为LinkedList和ArrayList，但是在Python中就更“抽象”。所以还是非常有必要下相当一部分功夫的。

正文

数组数据结构

从我们熟悉而且常用的老朋友——数组开始介绍。在Python中，数组可以是固定大小的，也可以是动态的，可以只装一种数据类型，也可以装很多种，这些都会在后边一一介绍。现在，先来了解一下数组的原理和用途。

数组由大小固定的数据记录组成，根据索引能快速找到其中的每个元素。
因为数组将信息存储在依次连接的内存块中，所以它是连续的数据结构。

列表——可变动态数组

Python里边常用的列表，即list，就是以动态数组实现的。它实现了增删查改功能，而且可以包含任何对象（也就是说可以装不同的数据类型）。

这个功能很强大，但缺点是同时支持多种数据类型会导致数据存储得不是很紧凑。因此整个结构占据了更多的空间。
本质上是因为列表中存储的是PyObject指针，指向不同的对象。然而（其它）数组是直接存放数据本身。

>>> arr = [1, 2, 3]
>>> arr[0]
1

# 列表的__repr__方法
>>> arr
[1, 2, 3]

# 列表是可变的，且可以含有任意类型的数据
>>> arr[1] = 'two'
>>> arr
[1, 'two', 3]

想了解更多有关list的知识，可以翻阅官方文档：List

元组——不可变容器

元组也是非常熟悉的一个Python中的序列类型了。与列表不同的是，Python的元组对象是不可变的，创建了元组之后，我们就不能对这个元组进行修改了。有些看上去是修改了元组的语法，本质上是创建了一个新的元组，而不是修改原来的元组。
和列表一样，元组也可以包含任意数据类型的元素。

>>> arr = 1, 2, 3
>>> arr[0]
1

# 元组的__repr__方法
>>> arr
(1, 2, 3)

# 元组是不可变的
>>> arr[1] = 'two'
TypeError: 'tuple' object does not support item assignment

# 元组可以包含任意类型的数据(注意，这里并没有修改原本的元组，而是创建了一个新的元组)
>>> arr + (23,)
(1, 2, 3, 23)

想了解更多有关tuple的知识，可以翻阅官方文档：Tuple

array.array——基本类型数组

利用array.array创建的数组也是可变的，但是它是只能包含单一数据类型的“类型数组”,因此它也比列表和元组更为节省空间。
此外，数组中也有许多普通列表中含有的方法，使用方式也相同。

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

# array.array的__repr__方法
>>> arr
array('f', [1.0, 1.5, 2.0, 2.5])

# array.array中数据类型是单一的
>>> arr[1] = 'one'
TypeError: must be real number, not str

str——含有Unicode字符的不可变数组

Python中的str实际上是不可变的字符数组，而且，str还是一种递归的数据结构，字符串中的每个字符都是长度为1的str对象（很奇怪吧，我也觉得）。
如果需要一个可变字符串，Python并不能像Java那样直接拿出一个StringBuffer，而是只能利用列表来作为可变字符串。

python3.x使用str对象将文本数据存储为不可变的Unicode字符序列。

>>> arr = 'hello'
>>> arr[1]
'e'

>>> arr
'hello'

# 字符串是不可变的
>>> arr[1] = 'e'
TypeError: 'str' object does not support item assignment

# 字符串是递归型数据类型
>>> type('hello')
<class 'str'>
>>> type('hello'[1])
<class 'str'>

想了解更多有关str的知识，可以翻阅官方文档：Str

bytes——含有单字节的不可变数组

bytes对象是单字节的不可变序列，单字节为[0, 255]范围内的整数。

>>> arr = bytes((0, 1, 2, 3))
>>> arr[1]
1

# bytes有自己的语法
>>> arr
b'\x00\x01\x02\x03'
>>> arr = b'\x00\x11\x22\x33'
>>> arr
b'\x00\x01\x02\x03'

bytes可以解包到bytearray中。

想了解更多有关bytes的知识，可以翻阅官方文档：Bytes

bytearray——含有单字节的可变数组

bytearray类型是可变整数序列，包含的整数范围和bytes一样，也是[0, 255]。
bytearray数可以转换回不可变的bytes对象，但是这需要复制所存储的数据，是耗时为**O(n)**的慢操作。

>>> arr = bytearray((0, 1, 2, 3))
>>> arr[1]
1

# bytearray的__repr__方法
>>> arr
bytearray(b'\x00\x01\x02\x03')

# bytearray可以转换回byte对象，此过程会复制数据
>>> bytes(arr)
b'\x00\x01\x02\x03'

想了解更多有关bytearray的知识，可以翻阅官方文档：Bytes Array

字典数据结构

Python里边第二熟悉的数据结构应该就是字典了。字典可以存储任意数量的对象，每个对象都是一个值，每个值都被唯一的字典键标识。
字典通常也被称为映射、散列表、查找表或关联数组。
在Python中，通常字典都是由dict实现，不过当dict不能满足某些需求的时候，Python还提供了一些特殊字典（尽管特殊，但他们都基于内置的字典类dict）以供使用。

dict——首选字典实现

Python中最稳健的字典实现就是dict。为方便使用，Python还提供了一些有用的“语法糖”来处理程序中的字典。例如，用花括号字典表达式语法和字典解析式能够方便地创建新的字典对象。

number = {
    'one': 1,
    'two': 2,
    'three': 3,
}
squares = {x: x * x for x in range(6)}

>>> number['two']
2

>>> squares
{0: 0, 1: 1, 2: 4, 3: 9, 4: 16, 5: 25}

Python的字典由可散列类型的键来索引。 可散列对象具有在其生命周期中永远不会改变的散列值（参见__hash__），并且可以与其他对象进行比较（参见__eq__）。另外，相等的可散列对象，其散列值必然相同。
像字符串和数这样的不可变类型是可散列的，它们可以很好地用作字典键。元组对象也可以用作字典键，但这些元组本身必须只包含可散列类型。
想了解更多有关dict的知识，可以翻阅官方文档：Mapping Types — dict

collections.OrderDict——能记住键的插入顺序

collections.OrderDict是特别的dict子类，该类型会记录添加到其中的键的插入顺序。

在Python3.7以后，标准的字典实现会保留键的插入顺序这一特性被固定下来了，当然，这只是CPython实现的一个副作用，如果在自己的工作中很需要用到键顺序，最好明确使用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'])

想了解更多有关collections.OrderedDict的知识，可以翻阅官方文档：collections.OrderedDict

collections.defaultdict——为缺失的键返回默认值

defaultdict是另一个dict子类，其构造函数接受一个可调用对象，查找时如果找不到给定的键，就返回这个可调用对象。

与使用get()方法或在普通字典中捕获KeyError异常相比，这种方式的代码较少，并能清晰地表达出程序员的意图。

>>> from collections import defaultdict
>>> d = defaultdict(list)

# 访问缺失的键就会用默认工厂方法创建它并初始化
# 在本例中工厂方法为list()
>>> d['none'].append(1)
>>> d['none'].append(2)
>>> d['none'].append(3)

>>> d['none']
[1, 2, 3]

可以看到我们在访问缺失的键时，对象 d 自动调用了list()方法为新键的值创建列表并返回这个列表。
想了解更多有关collections.defaultdict的知识，可以翻阅官方文档：collections.defaultdict

collections.ChainMap——搜索多个字典

collections.ChainMap将多个字典分组到一个映射中，在查找时逐个搜索底层映射，直到找到一个符合条件的键。对ChainMap进行插入、更新和删除操作，只会作用于其中的第一个字典。

>>> from collections import ChainMap
>>> d1 = {'one': 1, 'two': 2,}
>>> d2 = {'three': 3, 'four': 4,}
>>> chainDict = ChainMap(d1, d2)

>>> chainDict
ChainMap({'one': 1, 'two': 2}, {'three': 3, 'four': 4})

# ChinaMap在内部从左到右逐个搜索，直到找到对应的键或全部搜索完毕。
>>> chainDict['three']
3
>>> chainDict['one']
1
>>> chainDict['none']
KeyError: 'none'

直观地看，我就觉得这东西像是一个包含字典的列表（像啊，很像啊！），操作（如查找）更方便的字典列表（误）。
想了解更多有关collections.ChainMap的知识，可以翻阅官方文档：collections.ChainMap

types.MappingProxyType——用于创建只读字典

MappingProxyType封装了标准的字典，为封装的字典数据提供只读视图。
举例来说，如果希望返回一个字典来表示类或模块的内部状态，同时禁止向该对象写入内容，此时MappingProxyType就能派上用场。使用MappingProxyType无需创建完整的字典副本。

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

# 代理是只读的
>>> readOnly['one']
1
>>> readOnly['one'] = 'one'
TypeError: 'mappingproxy' object does not support item assignment

# 更新原字典也会影响代理
>>> writable['one'] = 'one'
>>> readOnly
mappingproxy({'one': 'one', 'two': 2})

想了解更多有关types.MappingProxyType的知识，可以翻阅官方文档：types.MappingProxyType

记录、结构体和纯数据对象

与数组相比，记录数据结构中的字段数目固定，每个都有一个名称，类型也可以不同。
从这个概念出发，我们很容易地可以想到用python中的字典来实现记录，也可以用元组来实现没有字段名称的特殊记录。但是前者的缺点是没有对字段名称进行保护，后者则是没有字段名称。好在python中还提供了一些数据类型或类来帮助实现这些数据结构。

collections.namedtuple——方便的数据对象

namedtuple可以看作是普通元组的拓展，也是不可变容器，但是它的每个字段都有名称。也就是说，namedtuple是具有名称的元组。
namedtuple非常适合在python中以节省内存的方式快速手动定义一个不可变的类，所以也很适合用于实现记录数据类型。

>>> from collections import namedtuple
>>> Car = namedtuple('Car', 'color mileage automatic')
>>> car1 = Car('red', 3812.4, True)

# 实例的__repr__方法
>>> car1
Car(color='red', mileage=3812.4, automatic=True)

# 访问字段
>>> car1.mileage
3812.4

# 字段是不可变的
>>> car1.mileage = 12
AttributeError: can't set attribute
>>> car1.windshield = 'broken'
AttributeError: 'Car' object has no attribute 'windshield'

想了解更多有关namedtuple的知识，可以翻阅官方文档：collections.namedtuple

typing.NamedTuple——改进版namedtuple

NamedTuple与namedtuple的主要区别就在于用新语法来定义记录类型并支持类型注解（type hint）。

注意，只有像mypy这样独立的类型检查工具才会在意类型注解。不过即使没有工具支持，类型注解也可帮助其他程序员更好地理解代码（如果类型注解没有随代码及时更新则会带来混乱）。

>>> from typing import NamedTuple
>>> class Car(NamedTuple):
		color: str
		mileage: float
		automatic: bool
>>> car1 = Car('red', 3812.4, True)

# 实例的__repr__方法
>>> car1
Car(color='red', mileage=3812.4, automatic=True)

# 访问字段
>>> car1.mileage
3812.4

# 字段是不可变的
>>> car1.mileage = 12
AttributeError: can't set attribute
>>> car1.windshield = 'broken'
AttributeError: 'Car' object has no attribute 'windshield'

# 只有像mypy这样的类型检查工具才会落实类型注解
>>> Car('red', 'NOT_A_FLOAT', 99)
Car(color='red', mileage='NOT_A_FLOAT', automatic=99)

想了解更多有关NamedTuple的知识，可以翻阅官方文档：typing.NamedTuple

types.SimpleNamespace——花哨的属性访问

SimpleNamespace同样可以用于创建数据对象，它主要提供通过属性访问的方式访问其名称空间。
也就是说，SimpleNamespace实例将其中的所有键都公开为类属性。因此访问属性时可以使用obj.key这样的点式语法，不需要像普通字典一样通过索引来访问值。

正如其名，SimpleNamespace很简单，基本上就是扩展版的字典，能够很好地访问属性并以字符串打印出来，还能自由地添加、修改和访问属性。

>>> from types import SimpleNamespace
>>> car1 = SimpleNamespace(color = 'red', mileage = 3812.4, automatic = True)

# 实例的__repr__方法
>>> car1
namespace(color='red', mileage=3812.4, automatic=True)

# 实例支持属性访问并且是可变的
>>> car1.mileage = 12
>>> car1.windshield = 'broken'
>>> del car1.automatic
>>> car1
namespace(color='red', mileage=12, windshield='broken')

想了解更多有关SimpleNamespace的知识，可以翻阅官方文档：types.SimpleNamespace

为什么没有struct.Struct？

因为我认为这个东西太过高级（懒），如同书中所说：“大多数情况下这都属于高级（且可能不必要的）优化。”如果想了解可以自行翻阅相关文档。

集合和多重集合

集合含有一组不含重复元素的无序对象。集合可用来快速检查元素的包含性，插入或删除值，计算两个集合的并集或交集。
在python中，集合和字典一样，也拥有语法糖：利用花括号表达式就可以快速创建集合，但是要注意，如果需要创建空集（不含任何元素的集合），就要用set()构造函数，如果用空花括号{}的话，创建的是一个空字典。

set——首选集合实现

set就是Python中的内置集合实现，可以看成是最基本的集合。set类型是可变的，能够动态插入和删除元素，所有可散列的对象都可以存储在集合中。

>>> animal = {'cat', 'bird', 'dog', 'panda'}
>>> 'cat' in animal
True

# intersection方法返回包含存在于集合 x 和集合 y 中的项目的集合（返回集合 x 和集合 y 的交集）
>>> my_pet = {'cat', 'dog'}
>>> my_pet.intersection(animal)
{'dog', 'cat'}

>>> animal.add('bat')
>>> animal
{'dog', 'cat', 'bat', 'panda', 'bird'}
>>> len(animal)
5

想了解更多有关set的知识，可以翻阅官方文档：set

frozenset——不可变集合

其实看名字就知道这是什么东西啦，就是一个静态集合，里边的元素只读不改。因此frozenset是可用作字典的键的（静态且可散列），也可以放置在另一个集合中，这些都是set没办法做到的。

>>> vowels = frozenset({'a', 'e', 'i', 'o', 'u'})
>>> vowels.add('p')
AttributeError: 'frozenset' object has no attribute 'add'

# frozenset用作字典键
>>> d = {frozenset({1, 2, 3}): 'hello'}
>>> d[frozenset({1, 2, 3})]
'hello'
>>> key = frozenset({1, 2, 3})
>>> d[key]
'hello'

想了解更多有关frozenset的知识，可以翻阅官方文档：frozenset

collections.Counter——多重集合

其实这个东西也非常简单，就是允许出现重复元素（允许在集合中多次出现同一个元素）的集合，它也叫做背包（bag）类型。

如果既要检查元素是否为集合的一部分，又要记录元素在集合中出现的次数，那么就需要用到这个类型

>>> 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的知识，可以翻阅官方文档：collections.Counter

栈与队列

栈是含有一组对象的容器，支持快速后进先出（LIFO）的插入（入栈push）和删除（出栈pop）操作。
队列则是先进先出（FIFO），插入和删除分别称作入队enqueue和出队dequeue。
可以很容易地想到用python内置的列表来实现，但是列表只对随机访问的性能好，对于插入和删除元素则差，所以python在这方面还提供了另外的类来实现。

collections.deque——快速且稳健的栈

deque类实现了一个双端队列，所以它既可以作为栈也可以作为队列。

Python的deque对象以双向链表实现，这为插入和删除元素提供了出色且一致的性能，但是随机访问位于栈中间元素的性能很差，耗时为O(n)。

>>> 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()
IndexError: pop from an empty deque

想了解更多有关deque的知识，可以翻阅官方文档：collections.deque

queue.LifoQueue——为并行计算提供的锁语义

queue.LifoQueue这个位于Python标准库中的栈实现是同步的，提供了锁语义来支持多个并发的生产者和消费者。（可以参考一下PV操作）

>>> from queue import LifoQueue
>>> s = LifoQueue()
>>> s.put('eat')
>>> s.put('sleep')
>>> s.put('code')

>>> s
<queue.LifoQueue object at 0x000001E3F4D22430>

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

>>> s.get()
# 阻塞，永远停在这里...

想了解更多有关LifoQueue的知识，可以翻阅官方文档：queue.LifoQueue

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()
IndexError: pop from an empty deque

想了解更多有关deque的知识，可以翻阅官方文档：collections.deque

queue.Queue——为并行计算提供的锁语义

参考LifoQueue。

>>> from queue import Queue
>>> q = Queue()
>>> q.put('eat')
>>> q.put('sleep')
>>> q.put('code')

>>> q
<queue.Queue object at 0x0000026060A55FA0>

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

>>> q.get()
# 阻塞，永远停在这里...

想了解更多有关Queue的知识，可以翻阅官方文档：queue.Queue

优先队列

优先队列是一个容器数据结构，使用具有全序关系的键（例如用数值表示的权重）来管理元素，以便快速访问容器中键值最小或最大的元素。
所以说python的列表挺全能了，甚至也能当优先队列，只不过每次添加新元素时，都要重新排序。
当然了，也有其他办法实现优先队列。

heapq——基于列表的二叉堆

heapq是二叉堆，通常用普通列表实现，能在O(logn)时间内插入和获取最小的元素。

由于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')

想了解更多有关heapq的知识，可以翻阅官方文档：heapq

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

想了解更多有关PriorityQueue的知识，可以翻阅官方文档：queue.PriorityQueue

尾声

在我不断地拖延症发作下漫长的更新终于结束啦蛤蛤蛤马上就有又会接着更新的现在就先这样啦

---

参考书目： 《Python Tricks 深入理解python特性》 [德]达恩·巴德尔 人民邮电出版社

希望本文章能够帮到您~