那时难决
0%

【使用Python实现算法】04 标准库（数据类型模块）

Posted on Edited on In

【使用 Python 实现算法】目录

算法实现中经常需要构造和处理一些特殊的数据结构，Python 标准库中有一些模块可以帮到我们。

collections 实用容器

collections模块实现了一些特定目标的容器，以提供 Python 标准内建容器 dict , list , set , 和 tuple 的替代选择。

deque

在 Python 中从list对象的头部删除元素，时间复杂度是 O(n)。deque类型是一个双向队列，类似列表(list)的容器，实现了在两端快速添加(append)和弹出(pop)。

1
2
3
4
5
6
7
8
9
q = deque([1, 2, 3, 4])

q.append(5)
q.appendleft(0)
assert q == deque([0, 1, 2, 3, 4, 5])

assert q.pop() == 5
assert q.popleft() == 0
assert len(q) == 4

在广度优先搜索的算法实现中，deque类型是一个不错的选择。

defaultdict

defaultdict是字典的子类，提供了一个工厂函数，为字典查询提供一个默认值

1
2
3
4
5
6
counter = defaultdict(int)

for ch in "aaabbbccc":
    counter[ch] += 1

assert counter == {"a": 3, "b": 3, "c": 3}

Counter

Counter也是字典的子类，提供了可哈希对象的计数功能。使用Counter类型可以使用一条语句替代上述的字母计数的实现。

1
assert Counter("aaabbbccc") == {"a": 3, "b": 3, "c": 3}

heapq 二叉堆算法

heapq模块提供了堆队列算法的实现，也称为优先队列算法。

堆是一个二叉树，它的每个父节点的值都只会小于或等于所有孩子节点（的值）。 它使用了数组来实现：从零开始计数，对于所有的 k ，都有 heap[k] <= heap[2k+1] 和 heap[k] <= heap[2k+2]。 为了便于比较，不存在的元素被认为是无限大。 堆最有趣的特性在于最小的元素总是在根结点：heap[0]。
这个 API 与教材的堆算法实现有所不同，具体区别有两方面：（a）我们使用了从零开始的索引。这使得节点和其孩子节点索引之间的关系不太直观但更加适合，因为 Python 使用从零开始的索引。 （b）我们的 pop 方法返回最小的项而不是最大的项（这在教材中称为“最小堆”；而“最大堆”在教材中更为常见，因为它更适用于原地排序）。
基于这两方面，把堆看作原生的 Python list 也没什么奇怪的： heap[0] 表示最小的元素，同时 heap.sort() 维护了堆的不变性！
要创建一个堆，可以使用 list 来初始化为 [] ，或者你可以通过一个函数 heapify() ，来把一个 list 转换成堆。

一个简单的堆排序的示例如下：

1
2
3
4
5
6
def heap_sort(nums):
    heapq.heapify(nums)
    return [heapq.heappop(nums) for _ in range(len(nums))]


assert heap_sort([3, 1, 2]) == [1, 2, 3]

当然在现实的算法实现中，一般不会去完整的实现一个堆排序。heapq模块主要应用在一些需要部分排序的算法实现中，例如 TopK 问题。

1
2
3
4
5
def top_k(arr: list[int], k: int) -> list[int]:
    heapq.heapify(arr)
    return heapq.nlargest(k, arr)

assert top_k([3, 1, 2], 2) == [3, 2]

bisect 二分查找

bisect模块提供了数组二分查找算法。

值得一提的是bisect模块的函数一般是返回新的插入位置，要检查一个元素是否在排序列表中，需要一点额外的判断。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
def index(a, x):
    'Locate the leftmost value exactly equal to x'
    i = bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    raise ValueError

def find_lt(a, x):
    'Find rightmost value less than x'
    i = bisect_left(a, x)
    if i:
        return a[i-1]
    raise ValueError

def find_le(a, x):
    'Find rightmost value less than or equal to x'
    i = bisect_right(a, x)
    if i:
        return a[i-1]
    raise ValueError

def find_gt(a, x):
    'Find leftmost value greater than x'
    i = bisect_right(a, x)
    if i != len(a):
        return a[i]
    raise ValueError

def find_ge(a, x):
    'Find leftmost item greater than or equal to x'
    i = bisect_left(a, x)
    if i != len(a):
        return a[i]
    raise ValueError

Python 官方文档给了一个体现bisect模块实用性的非常合适的例子（代码稍有调整）。

函数 bisect() 还可以用于数字表查询。这个例子是使用 bisect() 从一个给定的考试成绩集合里，通过一个有序数字表，查出其对应的字母等级：90 分及以上是 ‘A’，80 到 89 是 ‘B’，以此类推

1
2
3
4
5
6
7
def grade(score, breakpoints=[60, 70, 80, 90], grades="FDCBA"):
    i = bisect.bisect(breakpoints, score)
    return grades[i]

grades = [grade(score) for score in [33, 99, 77, 70, 89, 90, 100]]
assert grades == ["F", "A", "C", "C", "B", "A", "A"]

bisect模块还提供了一个insort函数用于向一个有序列表中插入元素。不过即使确定插入位置的时间复杂度是 O(logN)，但向列表中插入元素的时间复杂度为 O(n)，实用性相当有限。

好在 LeetCode 的 Python 环境安装并导入了sortedcontainers模块，提供了SortedList，SortedDict等实用类型。

graphlib 拓扑排序

graphlib是 Python3.9 引入的新模块，提供了拓扑排序的功能。

1
2
3
4
>>> graph = {"D": {"B", "C"}, "C": {"A"}, "B": {"A"}}
>>> ts = TopologicalSorter(graph)
>>> tuple(ts.static_order())
('A', 'C', 'B', 'D')

总结

这些模块可以帮助构造想要的数据结构，实现具体的算法。

扫码加入技术交流群🖱️
QR code