Python中实用的库函数
|字数总计:1.9k|阅读时长:9分钟|阅读量:|
数据结构
双端队列
可从队列2端进行添加和移除数据，效率比list高。
1
2
3
4
5
6
7
8
9
| from collections import deque
d=deque([1,2,3])
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)
|
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)
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)
d = defaultdict(list)
d['a'].append(1)
print(d)
|
顺序存储字典
按顺序存储字典键值，内部由普通字典和双向链表实现。
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
| from collections import OrderedDict
user_dict = OrderedDict()
user_dict['b'] = '0xbug'
user_dict['a'] = '0bug'
user_dict['c'] = '1bug'
print(user_dict)
print(user_dict.popitem())
print(user_dict)
print(user_dict)
print(user_dict.popitem(last=False))
print(user_dict)
print(user_dict)
print(user_dict.pop('a'))
print(user_dict)
print(user_dict)
print(user_dict.move_to_end('a'))
print(user_dict)
print(user_dict)
print(next(iter(user_dict.values())))
|
有序集合
集合元素是有序的，添加元素后集合仍然保持有序。
1
2
3
4
5
6
7
| from sortedcontainers import SortedList
sl = SortedList()
sl.add(num)
sl.pop(0)
sl.pop()
s1.remove(num)
|
键有序字典
字典的键是有序的，可按顺序遍历键。
1
2
3
4
| from sortedcontainers import SortedDict
sd = SortedDict({'c': 3, 'a': 1, 'b': 2})
print(sd)
|
sortedcontainers非python默认库，需进行安装pip install sortedcontainers。
计数器
一种特殊的默认初始化字典，值是int类型，表示键的数量。
1
2
3
4
5
| from collections import Counter
obj = Counter('aabbccc')
obj['d'] += 1
print(obj)
|
自定义数据结构
并查集
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class UnionFind:
def __init__(self,n):
self.un=list(range(n))
def find(self,p):
if self.un[p]!=p:
self.un[p]=self.find(self.un[p])
return self.un[p]
def merge(self,p,q):
pr=self.find(p)
qr=self.find(q)
if pr!=qr:
self.un[pr]=qr
def connect(self,p,q):
return self.find(p)==self.find(q)
|
单词树
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Trie:
def __init__(self):
self.children={}
self.cnt=0
def add(self,s):
curr=self
for c in s:
if not c in curr.children:
curr.children[c]=Trie()
curr=curr.children[c]
curr.cnt+=1
def get(self,s):
curr=self
for c in s:
if not c in curr.children:
return 0
curr=curr.children[c]
return curr.cnt
|
二分模块
通过二分算法快速在有序集合中找到插入点。
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)
bisect.bisect_right([1,2],1)
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
random.random()
random.uniform(2, 6)
random.randint(6,8)
random.randrange(0, 31, 2)
random.choice([1,2,3])
arr=[1,2,3,4,5]
random.shuffle(arr)
print(arr)
random.sample([1,2,3,4,5], 3)
|
累积运算
1
2
3
4
5
6
7
8
9
10
11
12
| import itertools
import operator
if __name__ == '__main__':
data = [1, 2, 3, 4, 5]
print(list(itertools.accumulate(data)))
data = [3, 4, 6, 2, 1, 9, 0, 7, 5, 8]
print(list(itertools.accumulate(data, operator.mul, initial=2)))
print(list(itertools.accumulate(data, max)))
|
排列组合
笛卡尔积
有放回抽样排列
1
2
3
4
5
6
| import itertools
for i in itertools.product('ABCD', repeat = 2):
print(i)
|
数量：$ n^r=4^2=16 $
排列
不放回抽样排列
1
2
3
4
5
6
| import itertools
for i in itertools.permutations('ABCD', 2):
print(i)
|
数量：$ 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)
|
数量： $ 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)
|
相当于多增加(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')。
