Python 中的那些数据结构

作为一个写 Java 和 C++ 入门的新手，对于 Python 的数据结构并不是十分熟悉。Python 写的最多的大概是一些机器学习的代码，整天和一堆 Tensor 搞来搞去，也用不到什么数据结构，但是这两天刷题准备面试就觉得自己的 Python 知识有点捉襟见肘。其实用 Java 面也不是不可以，但是总觉得为了创建一个 ArrayList 就要写 List<Integer> l = new ArrayList<>(); 相比 Python 中的 l = [] 实在蛋疼不少，还是想享受一下写 Python 的轻快。

这里总结一下 Python 中一些有坑的以及不常用的数据结构。不过看到这么多乱七八糟到处都是的数据结构，可能会感到 Python 真的并不优雅。

list 列表

List 作为 Python 最基本的数据结构之一，应该还算是比较熟悉。需要注意的一个是它的内部实现是一个数组，即连续的一段内存，所以移除元素的时候需要移动 list 中的元素。因此用 list 来当作队列用是低效的，而用作栈则没有问题。

向 list 末尾添加元素使用 l.append(x)，从末尾移除元素则是 l.pop()。这是 list 作为栈使用的基本操作。如果要在 list 中间插入元素，则需要使用 l.insert(idx, x)，移除则是 l.pop(idx)。

此外还有一些方便的操作，比如 l.count(x)，l.index(x)，都是 $\O(n)$ 复杂度，一般不太常用到。

另外很重要的是 list 支持的比较运算符。注意 Python 的运算符是可以通过 dunder method 重载的，所以 == （即 __eq__） 的比较一般相当于 Java 中的 equals，而 is 才是 Java 中的 ==，即 reference equality。因为重载的特性，所以 == 对于 list 来说就是最自然的比较，两个 list 相等当且仅当它们长度相同且对应元素相等；而不等号的比较也十分自然，即是字典序的比较。

还有很重要的一点是因为 list 可变，它是 unhashable 的，所以不能作为字典中的 key！

tuple 元组

Tuple 也是 Python 的基本数据结构，相对来说我还是比较熟悉。需要注意的几点是它与 list 的一些不同，比如它是 immutable 和 hashable 的。

Tuple 的比较运算符和 list 相同。需要注意的是 Python 对 tuple 加法运算的定义和 list 是一致的，即 concat 运算，而不是逐元素的加法。

set 集合和 dict 字典

集合与字典也是 Python 的基本数据结构，非常常用，但是也没有什么特别的坑。

collections.Counter 计数器

Counter 是在 collections 中的一个数据结构，是 dict 的子类；它的 key 可以是任意 hashable 的值，value 是自然数。通过它的构造器可以很方便的获得一个 iterable 的数据结构中各个元素的数量。一个方便的方法是 counter.most_common()，可以获得 value 最大的 key。但是总的来说 Counter 并不是非常常用。

collections.deque 双端队列

deque （发音为 deck）则是 collections 中非常常用的一种数据结构，即双端队列，可以用作 LIFO 的栈也可以用作 FIFO 队列（不过栈一般使用 list 就够了），两端操作都为 $\O(1)$，在 BFS 之类的算法中非常有用。可以通过构造器传入一个 iterable 来提供 deque 的初始值。

它支持的方法有 q.append，q.appendleft，q.pop，q.popleft；也有 q.extend 和 q.extendleft，不过在算法题中应该不会常用。还有一个方便的 q.rotate(n) 可以右移元素，不过应该也不常用。

collections.defaultdict 缺省字典

defaultdict 也是 dict 的子类，只是在使用方括号的时候，如果 key 不存在，会返回一个默认值。这个默认值在初始化时通过构造器传入。

collections.OrderedDict 有序字典

OrderedDict 可以记住插入元素的顺序，内部使用链表实现，所以 od.popitem(True) （从末尾移除）和 od.popitem(False) （从开头移除）都是 $\O(1)$ 的操作。

heapq 堆队列算法

heapq 是堆在 Python 中的一种实现，不过有趣的是它是一个算法（一系列函数）而不是一个数据结构。它直接使用（而不是在内部维护）一个 list 来作为堆的数据，支持：heappush(heap, item)，heappop(heap)，heappushpop(heap,item)（先 push 再 pop，比分开操作快），heapreplace(heap,item)（先 pop 再 push，也比分开操作快），其中 heap 是一个满足堆性质的 list。另外还有线性时间的 heapify(x) 的 heapify 算法，将 list x 变成一个堆。

一个恼人的问题是 heapq 并不支持自定义的 priority，所以如果需要用它处理非数字的值，需要使用一个 tuple (priority, item) 来手工指定 priority。

此外，heapq 包还有两个有qi用guai的方法，nlargest(n, iterable, key=None) 和对应的 nsmallest(n, iterable, key=None)，利用堆来取出 iterable 中最大（小）的 n 个元素（大小由 key 函数定义）。

queue.PriorityQueue 优先队列

queue 是一个包，包括了各种各样队列的实现。其中 queue.SimpleQueue 是最普通的队列，在一些情景（？）下有特定用途，但是在算法题中 collections.deque 已经足够好。比较有用的是 queue.PriorityQueue。它是一个优先队列（堆），使用 pq.put(item) 插入数据，使用 pq.get() 取出数据。

官方推荐了以下方式来制定某项的 priority，但是使用 tuple 仍然是一种可行的方法。

from dataclasses import dataclass, field
from typing import Any

@dataclass(order=True)
class PrioritizedItem:
    priority: int
    item: Any=field(compare=False)