数据结构

双端队列

可从队列2端进行添加和移除数据,效率比list高。

1
2
3
4
5
6
7
8
9
from collections import deque

d=deque([1,2,3]) # 使用list初始化
d.append(1) # 队尾添加元素
d.appendleft(1) # 队头添加元素
d.pop() # 队尾移除元素
d.popleft() # 队头移除元素
d.extend([4,5,6]) # 队尾添加多个元素
d.extendleft([4,5,6]) # 队头添加多个元素

优先队列

基于堆实现的优先队列,默认小顶堆,最小的元素在堆顶。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from queue import PriorityQueue

q = PriorityQueue()

q.put((2, 'code'))
q.put((1, 'eat'))
q.put((3, 'sleep'))

while not q.empty():
next_item = q.get()
print(next_item)

# 结果:
# (1, 'eat')
# (2, 'code')
# (3, 'sleep')

PriorityQueue内部使用heapq函数实现,将基于函数的接口封装为了基于类的接口,同时PriorityQueue是同步的,提供了锁语义来支持多个并发的生产者和消费者。

函数式heapq

默认小顶堆

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import heapq

q = []

heapq.heappush(q, (2, 'code'))
heapq.heappush(q, (1, 'eat'))
heapq.heappush(q, (3, 'sleep'))

while q:
next_item = heapq.heappop(q)
print(next_item)

# 结果:
# (1, 'eat')
# (2, 'code')
# (3, 'sleep')

# 将一个数组初始化为堆结构
heapq.heapify([3,2,1])

默认初始化字典

如果获取的键不存在,则采用指定的构造函数为这个键设置一个默认值。

1
2
3
4
5
6
7
8
9
10
11
from collections import defaultdict

s = 'mississippi'
d = defaultdict(int)
for k in s:
d[k] += 1
print(d) # defaultdict(<class 'int'>, {'m': 1, 'i': 4, 's': 4, 'p': 2})

d = defaultdict(list)
d['a'].append(1)
print(d) # defaultdict(<class 'list'>, {'a': [1]})

键有序字典

字典的键是有序的,可按顺序遍历键。

1
2
3
4
from sortedcontainers import SortedDict

sd = SortedDict({'c': 3, 'a': 1, 'b': 2})
print(sd) #SortedDict({'a': 1, 'b': 2, 'c': 3})

计数器

一种特殊的默认初始化字典,值是int类型,表示键的数量。

1
2
3
4
5
from collections import Counter

obj = Counter('aabbccc')
obj['d'] += 1
print(obj) # Counter({'c': 3, 'a': 2, 'b': 2, 'd': 1})

二分模块

通过二分算法快速在有序集合中找到插入点。

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

# 插入操作
bisect.insort_left([1,2],1) # 插入在左侧,无返回值
bisect.insort_right([1,2],1) # 插入在右侧,无返回值

# 查找操作
bisect.bisect_left([1,2],1) # 不插入值,返回左侧的索引,输出:0
bisect.bisect_right([1,2],1) # 不插入值,返回右侧的索引,输出:1

# 下面两行就是insort_right和bisect_right的别名
bisect.insort([1,2],1) # 插入在右侧
bisect.bisect([1,2],1) # 不插入值,返回右侧的索引

随机数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import random

# 浮点数[0,1)
random.random()

# 浮点数[2,6]
random.uniform(2, 6)

# 整数[6,8]
random.randint(6,8)

# 随机返回range中的一个元素
random.randrange(0, 31, 2) # 输出[0,30]内的偶数

# 随机返回集合中的一个元素
random.choice([1,2,3])

# 随机打乱集合,无返回
arr=[1,2,3,4,5]
random.shuffle(arr)
print(arr)

# 从列表中随机返回3个元素,作为新列表返回
random.sample([1,2,3,4,5], 3)

排列组合

笛卡尔积

有放回抽样排列

1
2
3
4
5
6
import itertools
for i in itertools.product('ABCD', repeat = 2):
print(i)
# 输出
# ('A', 'A') ('A', 'B') ('A', 'C') ('A', 'D') ('B', 'A') ('B', 'B') ('B', 'C') ('B', 'D')
# ('C', 'A') ('C', 'B') ('C', 'C') ('C', 'D') ('D', 'A') ('D', 'B') ('D', 'C') ('D', 'D')

数量:$ n^r=4^2=16 $

排列

不放回抽样排列

1
2
3
4
5
6
import itertools
for i in itertools.permutations('ABCD', 2):
print(i)
# 输出
# ('A', 'B') ('A', 'C') ('A', 'D') ('B', 'A') ('B', 'C') ('B', 'D') ('C', 'A') ('C', 'B')
# ('C', 'D') ('D', 'A') ('D', 'B') ('D', 'C')

数量:$ A_n^r=A_4^2=\frac{4!}{(4-2)!}=12 $

组合,没有重复

不放回抽样组合

1
2
3
4
5
import itertools
for i in itertools.combinations('ABCD', 2):
print(i)
# 输出
# ('A', 'B') ('A', 'C') ('A', 'D') ('B', 'C') ('B', 'D') ('C', 'D')

数量: $ C_n^r=C_4^2=\frac{4!}{(4-2)!*2!}=6 $

组合,有重复

有放回抽样组合

1
2
3
4
5
6
import itertools
for i in itertools.combinations_with_replacement('ABCD', 2):
print(i)
# 输出
# ('A', 'A') ('A', 'B') ('A', 'C') ('A', 'D') ('B', 'B') ('B', 'C') ('B', 'D') ('C', 'C')
# ('C', 'D') ('D', 'D')

相当于多增加(r-1)个元素参与选择,这(r-1)个元素是替换符,可以替换成组合中已存在的元素,形成重复。

数量: $ C_{n+r-1}^r=C_5^2=\frac{5!}{(5-2)!*2!}=10 $

相比itertools.combinations('ABCD', 2),多出的4个组合是('A', 'X') ('B', 'X') ('C', 'X') ('D', 'X'),对应的则是('A', 'A') ('B', 'B') ('C', 'C') ('D', 'D')