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)