Python Cookbook

对《Python Cookbook》做一些整理。按照章节进行。

数据结构和算法

字典

字典中将键映射到多个值上

在字典中将键映射到多个值上,需要将这多个值保存到另一个容器里面,使用list或者set,大致流程如下。

1
2
3
4
5
6
7
8
>>> dict = {}
>>> a = [1,2,3]
>>> dict['a'] = a
>>> b = [4,5]
>>> dict['b'] = b
>>> dict
{'a': [1, 2, 3], 'b': [4, 5]}
>>>

麻烦的地方在于创建每个键值对应的容器。

collections模块中的defaultdict类,和正常的dict模块相比,它会自动初始化容器,这样就只需要关注添加的元素。例如

1
2
3
4
5
6
7
8
9
>>> from collections import defaultdict
>>> d = defaultdict(list)
>>> d['a'].append(1)
>>> d['a'].append(2)
>>> d
defaultdict(<class 'list'>, {'a': [1, 2]})
>>> d.get('a')
[1, 2]
>>>

如果想要使用set(),那么久d = defaultdict(set)

如果不想用这个特制类,也有对应的简化操作,不过稍微有点奇怪。

1
2
3
4
5
>>> d = {}
>>> d.setdefault('a', []).append(1)
>>> d
{'a': [1]}
>>>

其实也就逻辑上稍微简化了一点。

1
2
3
4
5
6
7
8
9
10
11
d = {}
for key, value in pairs:
if key not in d:
d[key] = []
d[key].append(value)

#如果使用defaultdict
from collections import defaultdict
d = defaultdict(list)
for key, value in pairs:
d[key].append(value)

让字典保持有序

可以使用collections模块里的OrderedDict类。当对字典进行迭代时候,会严格按照元素初始添加的顺序进行。当保持有序,进行其他序列化操作或者编码成另一种格式的时候,例如下面的转json格式。

OrderedDict内部维护了一个双向链表,会根据元素加入的顺序安排键的位置,第一个加入的元素在链表的末尾。对键对应的元素重新赋值不会改变键的顺序。缺点是OrderedDict的大小是普通字典的两倍多。

1
2
3
4
5
6
7
8
9
10
11
>>> from collections import OrderedDict
>>> d = OrderedDict()
>>> d['foo'] = 1
>>> d['bar'] = 2
>>> d['spam'] = 4
>>> d['grok'] = 3
>>> d
OrderedDict([('foo', 1), ('bar', 2), ('spam', 4), ('grok', 3)])
>>> import json
>>> json.dumps(d)
'{"foo": 1, "bar": 2, "spam": 4, "grok": 3}'

双向队列

使用collections中的deque,或者list人工定义也能实现deque双向队列的功能。

Python没有独立的堆类型,而只有一个包含一些堆操作函数的模块。这个模块名为heapq(其中的q表示队列),它包含6个函数,其中前4个与堆操作直接相关。必须使用列表来表示堆对象本身。

函数 作用
heappush(heap, x) 将x压入堆中
heappop(heap) 从堆中弹出最小的元素
heapify(heap) 让list变为堆
heapreplace(heap,x) 弹出最小的元素,并将x压入堆中
nlargest(n, iter) 返回iter中n个最大的元素
nsmallest(n, iter) 返回iter中n个最小的元素

最后两个函数相当于是使用了堆排序。

1
2
3

nums = [1,8,2,23,-7]
print(heapq.nlargest(3,nums))

值得注意的是使用这个模块默认构建的是小顶堆。

如果要heapq构建大顶堆,在构建和压入弹出元素对正负加上小trick

1
2
3
4
5
6
7
8
9
import heapq
class MaxHeap(object):
def __init__(self, x):
self.heap = [-e for e in x]
heapq.heapify(self.heap)
def push(self, value):
heapq.heappush(self.heap, -value)
def pop(self):
return -heapq.heappop(self.heap)

当然也可以手动写代码实现

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
class max_heap:
def __init__(self,arr):
self.arr = arr
for i in range(len(self.arr)//2-1, -1, -1):
self.heapify(i, len(self.arr)-1)


def heapify(self, start, end):
dad = start
son = start*2+1
while son < end:
if son + 1 <= end and self.arr[son] < self.arr[son+1]:
#使用两个子节点中更大的那个
son += 1
if self.arr[son] > self.arr[dad]:
#父节点小的话,和子节点互换,并且为继续递归调整做好准备,设置好下一次的dad和son的值
self.arr[son], self.arr[dad] = self.arr[dad], self.arr[son]
dad = son
son = dad * 2 + 1
else:
#如果父节点大,不需要调整
return
def heap_sort(self):
for i in range(len(self.arr)-1,-1,-1):
#把堆顶的元素,也就是最大值,存放在最后
self.arr[0], self.arr[i] = self.arr[i], self.arr[0]
#之后再对 下标i之前的数值进行heapify之后取出新的最大值
self.heapify(0, i-1)

arr = [3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, 0, 2, 6]
heapq = max_heap(arr)
heapq.heap_sort()
print(arr)

优先队列

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

class priorityQueue:

def __init__(self):
self.queue = []
self.index = 0
def push(self, item, priority):
heapq.heappush(self.queue, (-priority, self.index, item))
self.index += 1
def pop(self):
return heapq.heappop(self.queue)[-1]

使用举例,以及解释下每次push为什么需要按照(-priority, self.index, item)的元组格式。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
>>> class Item:
... def __init__(self, name):
... self.name = name
... def __repr__(self):
... return 'Item({0})'.format(self.name)
...
>>> q = PriorityQueue()
>>> q.push(Item('foo'), 1)
>>> q.push(Item('bar'), 5)
>>> q.push(Item('spam'), 4)
>>> q.push(Item('qrok'), 1)
>>> q.pop()
Item('bar')
>>> q.pop()
Item('spam')
>>> q.pop()
Item('foo')
>>> q.pop()
Item('grok')
>>>

由于 heapq默认的是小顶堆,所以元组的第一个值的priority需要取负,因为我们希望的是队列能够按照元素的优先级从高到低进行排列。这样每次pop出来的是priority高的元素,符合优先队列的要求。

元组的第二个值维护了一个index,标记了元素入队列的时间。这样使得相同优先级的元素能够以适当的指标进行排序,也方便元素之间的对比。
(元组之间比大小是按照从前往后一个个元素对应着比对的)。

bisect的使用

和二分搜索有关,对于一个有序序列,查找特定数值就可以使用这个模块

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

L = [1,3,3,6,8,12,15]
x = 3

x_insert_point = bisect.bisect_left(L,x)  
#在L中查找x,x存在时返回x左侧的位置,x不存在返回应该插入的位置..这是3存在于列表中,返回左侧位置1
print(x_insert_point)

x_insert_point = bisect.bisect_right(L,x)
#在L中查找x,x存在时返回x右侧的位置,x不存在返回应该插入的位置..这是3存在于列表中,返回右侧位置3
print(x_insert_point)

bisect.insort_left(L,x)
#将x插入到列表L中,x存在时插入在左侧
print(L)

bisect.insort_right(L,x)
#将x插入到列表L中,x存在时插入在右侧    
print(L)

一些技巧性操作

在两个字典中寻找相同点

字典的键也支持集合操作,并集、交集和差集。keys()和items()是可以配合集合操作符使用的。

但是values()不行,因为字典保证键值都是不同的,但是values是可以有重复的。

1
2
3
4
5
6
7
8
9
10
11
12
>>> a = {'x':1, 'y':2, 'z':3}
>>> b = {'w':10, 'x':11, 'y':2}
>>> a.keys() & b.keys()
{'x', 'y'}
>>> a.keys() - b.keys()
{'z'}
>>> a.items() & b.items()
{('y', 2)}
>>> c = {key:a[key] for key in a.keys() - {'z','w'}}
>>> c
{'x': 1, 'y': 2}
>>>