越而胜己 / Beyond awesome

作为一个写 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.appendq.appendleftq.popq.popleft;也有 q.extendq.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)