Python学习之路42-数据结构和算法

《Python Cookbook》笔记。

本篇主要讨论Python中一些常用的数据结构和算法。

1. 保留最后N个元素

collections.deque可以设置队列的长度,用于保存最后加入的N个元素:

1
2
3
4
5
6
7
8
>>> from collections import deque
>>> q = deque(maxlen=3)
>>> q.extend([1,2,3])
>>> q
deque([1, 2, 3], maxlen=3)
>>> q.append(4)
>>> q
deque([2, 3, 4], maxlen=3)

有时我们希望在处理数据时(比如文本匹配)能记录最后访问到的几项数据,此时使用collections.deque就会非常方便。

2. 找到最大或最小的N个元素

使用heapq模块中的nlargest()nsmallest()函数可以轻松实现:

1
2
3
4
5
6
>>> import heapq
>>> nums = [1, 8, 2, 23, 7, -4, 18, 23, 42, 37, 2]
>>> heapq.nlargest(3, nums)
[42, 37, 23]
>>> heapq.nsmallest(3, nums)
[-4, 1, 2]

sorted()函数一样,这两个函数也接收一个key参数,用于在排序时比较元素。

从这个模块名可以看出,这个模块中的函数必定和堆(Heap)有关,但nlargest()nsmallest()在排序元素时并不一定建堆,它会根据实际情况选择排序方法:比如,要是N和集合本身大小差不多,它就会选择例如快排之类的排序方法,然后切片,而不是建堆。

这两个函数一般用于N比较小的情况:

  • 当N=1时,建议大家使用max()min()函数;
  • 当N接近集合大小时,建议大家直接使用sorted()函数,然后切片;
  • 当N在上述两个情况之间时,则是用到nlargest()nsmallest()的时候。

还有一种情况,如果想依次获取集合中最小的元素,可以先建堆,再弹出:

1
2
3
4
5
6
7
8
9
>>> import heapq
>>> heap = [1, 8, 2, 23, 7, -4, 18, 23, 42, 37, 2]
>>> heapq.heapify(heap)
>>> heap
[-4, 2, 1, 23, 7, 2, 18, 23, 42, 37, 8]
>>> heapq.heappop(heap)
-4
>>> heapq.heappop(heap)
1

不过,在使用heapq.heappop()之前,请先建堆heapq.heapify(),否则得到的不一定是你想要的结果。

heapq.heapify()建立的是小顶堆,heapq.heappop()的时间复杂度是O(logN)级。

3. 优先级队列

其实queue.py模块中自带了一个PriorityQueue类,它的内部实现其实也是使用的collections.queueheapq。这里我们手动使用heapq模块来实现一个简单的优先级队列,用于展示其中的某些技巧。这个优先级队列每次pop操作时,都弹出优先级最高的那个元素:

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
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]

>>> from my_prique import PriorityQueue
>>> class Item:
... def __init__(self, name):
... self.name = name
... def __repr__(self):
... return "Item({!r})".format(self.name)
...
>>> q = PriorityQueue()
>>> q.push(Item("foo"), 1)
>>> q.push(Item("bar"), 3)
>>> q.push(Item("grok"), 1)
>>> q.pop()
Item('bar')
>>> q.pop()
Item('foo')
>>> q.pop()
Item('grok')

这里其实利用到了3个点:

  • 在比较元素顺序时,利用了元组比较的规则:两个元组进行比较时,先比较第一个元素,第一个元素相等再比较下一个元素,以此类推;
  • 由于heapq.heapify()建立的是小顶堆,每次pop操作返回的都是最小值,而我们要求返回最大值,所以将优先级进行了取负,这是一个常用的技巧;
  • 为了实现”同优先时级先录入的先输出”,这里维护了一个self._index计数器,用于指示录取的顺序。它相当于一个第二优先级。

heapq.heappush()的时间复杂度也是O(logN)级。

4. 一键多值字典

这里指的并不是什么惊奇的字典,也不是什么真正的一键多值字典,其实就是一个键对应一个列表或集合,实际还是一键一值。

有时候我们希望创建这样的字典:

1
2