Python Cookbook

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

数据结构和算法

双向队列

使用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)