4-python算法常用模块

1 集合

熟练掌握常用的集合运算符-|^&，可以提高编码效率：

a = {"a", "b", "c"}
b = {"a", "b", "d"}
print("差集，a有b没有的元素:a-b=", a - b, "，等价于a.difference(b)", a.difference(b))
print("并集，a、b合在一起并去重:a|b=", a | b, "，等价于a.union(b)", a.union(b))
print("交集，a、b同时都有的元素:a&b=", a & b, "，等价于a.intersection(b)", a.intersection(b))
print("补集，a有b没有的元素+b有a没有的元素:a^b=", a ^ b, "，等价于a.symmetric_difference(b)或(a-b)+(b-a)", a.symmetric_difference(b))
1
2
3
4
5
6

---

2 collections模块

collections模块常用的对象有defaultdict、OrderedDict、namedtuple。但是也别忘了Counter、deque

• collections.Counter，用于快速统计序列中的元素特别好用；同时还具有默认字典的功能:

import collections
obj = collections.Counter('aabbccc')
print(obj)
print("~~~~~~~~~~~~~~~~~~~~~~~")
obj1 = collections.Counter()
obj1["a"] += 1
print(obj1)
1
2
3
4
5
6
7

• collections.deque: 如果list是单端队列的话，collections.deque则是两端都能实现快速append和pop的双端队列

import collections
q = collections.deque()
q.append(1)
q.append(3)
q.appendleft(2)
print(q)
print(q.popleft())
print(q.pop())
1
2
3
4
5
6
7
8

---

3 bisect模块

如果不是学习如何实现二分法搜索的话，生产运用中，应到立马要想到使用bisect模块，避免重复造轮子，提高效率。

import bisect
test_list = [1, 2, 2, 4, 8, 15]

print(bisect.bisect(test_list, 2))
print(bisect.bisect_right(test_list, 2))
print(bisect.bisect_left(test_list, 2))

bisect.insort_right(test_list, 2)
print(test_list)
bisect.insort_left(test_list, 8)
print(test_list)

1
2
3
4
5
6
7
8
9
10
11
12

---

4 itertools模块

可以使用itertools.accumulate类，计算前缀合，同时还可以指定前缀和数组的初始值，返回一个itertools.accumulate对象。

import itertools
test_list = [1, 2, 2, 4, 8, 15]
ret = itertools.accumulate(test_list, initial=0)
print(ret)
ret_list = list(ret)
print(ret_list)
1
2
3
4
5
6

除此之外，itertools还有很多其他有用的方法，比如生产无限迭代器itertools.count()等。

---

5 heapq模块

该模块提供了堆排序算法的实现。

1 创建堆

heapq创建堆的方法有两种。一种是使用一个空列表，然后使用heapq.heappush()函数把值加入堆中，另外一种就是使用heap.heapify(list)转换列表成为堆结构。

import heapq

# 第一种
nums = [2, 3, 5, 1, 54, 23, 132]
heap = []
for num in nums:
    heapq.heappush(heap, num)  # 加入堆

print(heap[0])  # 如果只是想获取最小值而不是弹出，使用heap[0]
print([heapq.heappop(heap) for _ in range(len(nums))])  # 堆排序结果
# out: [1, 2, 3, 5, 23, 54, 132]

# 第二种
nums = [2, 3, 5, 1, 54, 23, 132]
heapq.heapify(nums)
print([heapq.heappop(nums) for _ in range(len(nums))])  # 堆排序结果
# out: [1, 2, 3, 5, 23, 54, 132]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

2 访问堆内容

• 堆创建好后，可以通过heapq.heappop() 函数弹出堆中最小值；
• 如果需要删除堆中最小元素并加入一个元素，可以使用heapq.heaprepalce()函数

3 heapq应用

实现heap堆排序算法。类似于sorted(iterable)，但与sorted()不同的是这个实现是不稳定的。

import heapq
def heapsort(iterable):
    h = []
    for value in iterable:
        heapq.heappush(h, value)
    return [heapq.heappop(h) for _ in range(len(h))]

src = [1, 3, 5, 7, 9, 2, 4, 6, 8, 0]
dst = heapsort(src)
print(dst)
1
2
3
4
5
6
7
8
9
10

重点： 堆元素可以为元组。 这适用于可以实现对带权值的元素进行排序（例如任务优先级）。 比如：

import heapq

src = [(23, 4), (0, 1, 65), (19, 0), (0, 1, 33), (5, 1), (6, 1), (19, 6), (88, 4)]
heapq.heapify(src)
ret = [heapq.heappop(src) for _ in range(len(src))]
print(ret)
# output: [(0, 1, 33), (0, 1, 65), (5, 1), (6, 1), (19, 0), (19, 6), (23, 4), (88, 4)]
# 可以看出，heapq排序，类似于sorted(iterable, key=lambda x: (x[0], x[1]， x[2]))
1
2
3
4
5
6
7
8

可以看出，heapq排序，类似于sorted(iterable, key=lambda x: (x[0], x[1]， x[2]))。

此外，还有heapq.merge、heapq.nlargest、heapq.nsmallest等方法，可以参考官方文档。