2018-02-28数据结构和算法(1)
1.1解压序列赋值给多个变量:
任何的序列（或者是可迭代对象）可以通过一个简单的赋值语句解压并赋值给多个变量。 唯一的前提就是变量的数量必须跟序列元素的数量是一样的。
>>> data = [ 'ACME', 50, 91.1, (2012, 12, 21) ] >>> name, shares, price, date = data >>> name 'ACME'
此方法需要注意变量个数和序列元素个数的匹配,否则会产生异常
代码示例:
>>> p = (4, 5) >>> x, y, z = p Traceback (most recent call last): File "<stdin>", line 1, in <module> ValueError: need more than 2 values to unpack
可以使用任意占位符去丢弃元素:
>>> data = [ 'ACME', 50, 91.1, (2012, 12, 21) ] >>> _, shares, price, _ = data >>> shares 50
1.2解压可迭代对象赋值给多个变量
>>> record = ('Dave', 'dave@example.com', '773-555-1212', '847-555-1212')
>>> name, email, *phone_numbers = record
>>> name
'Dave'
>>> email
'dave@example.com'
>>> phone_numbers
['773-555-1212', '847-555-1212']
>>>
值得注意的是上面解压出的 phone_numbers 变量永远都是列表类型，不管解压的电话号码数量是多少（包括 0 个）。 所以，任何使用到 phone_numbers 变量的代码就不需要做多余的类型检查去确认它是否是列表类型了。
值得注意的是，星号表达式在迭代元素为可变长元组的序列时是很有用的。 比如，下面是一个带有标签的元组序列：
records = [
('foo', 1, 2),
('bar', 'hello'),
('foo', 3, 4),
]
def do_foo(x, y):
print('foo', x, y)
def do_bar(s):
print('bar', s)
for tag, *args in records:
if tag == 'foo':
do_foo(*args)
elif tag == 'bar':
do_bar(*args)
星号解压语法在字符串操作的时候也会很有用，比如字符串的分割。
代码示例：
>>> line = 'nobody:*:-2:-2:Unprivileged User:/var/empty:/usr/bin/false'
>>> uname, *fields, homedir, sh = line.split(':')
>>> uname
'nobody'
>>> homedir
'/var/empty'
>>> sh
'/usr/bin/false'
>>>
有时候，你想解压一些元素后丢弃它们，你不能简单就使用 * ， 但是你可以使用一个普通的废弃名称，比如 _ 或者 ign （ignore）。
代码示例：
>>> record = ('ACME', 50, 123.45, (12, 18, 2012))
>>> name, *_, (*_, year) = record
>>> name
'ACME'
>>> year
2012
>>>
如果你够聪明的话，还能用这种分割语法去巧妙的实现递归算法。比如：
1 >>> def sum(items): 2 ... head, *tail = items 3 ... return head + sum(tail) if tail else head 4 ... 5 >>> sum(items) 6 36 7 >>>
然后，由于语言层面的限制，递归并不是 Python 擅长的
1.3保留最后N个元素
保留有限历史记录正是 collections.deque 大显身手的时候。比如，下面的代码在多行上面做简单的文本匹配， 并返回匹配所在行的最后N行：
from collections import deque
def search(lines, pattern, history=5):
previous_lines = deque(maxlen=history)
for line in lines:
if pattern in line:
yield line, previous_lines
previous_lines.append(line)
# Example use on a file
if __name__ == '__main__':
with open(r'../../cookbook/somefile.txt') as f:
for line, prevlines in search(f, 'python', 5):
for pline in prevlines:
print(pline, end='')
print(line, end='')
print('-' * 20)
使用 deque(maxlen=N) 构造函数会新建一个固定大小的队列。当新的元素加入并且这个队列已满的时候， 最老的元素会自动被移除掉。
尽管你也可以手动在一个列表上实现这一的操作（比如增加、删除等等）。但是这里的队列方案会更加优雅并且运行得更快些。
更一般的， deque 类可以被用在任何你只需要一个简单队列数据结构的场合。 如果你不设置最大队列大小，那么就会得到一个无限大小队列，你可以在队列的两端执行添加和弹出元素的操作。
代码示例：
>>> q = deque() >>> q.append(1) >>> q.append(2) >>> q.append(3) >>> q deque([1, 2, 3]) >>> q.appendleft(4) >>> q deque([4, 1, 2, 3]) >>> q.pop() 3 >>> q deque([4, 1, 2]) >>> q.popleft() 4
在队列两端插入或删除元素时间复杂度都是 O(1) ，区别于列表，在列表的开头插入或删除元素的时间复杂度为 O(N) 。
1.4查找最大或最小的N个元素
heapq 模块有两个函数：nlargest() 和 nsmallest() 可以完美解决这个问题。
import heapq nums = [1, 8, 2, 23, 7, -4, 18, 23, 42, 37, 2] print(heapq.nlargest(3, nums)) # Prints [42, 37, 23] print(heapq.nsmallest(3, nums)) # Prints [-4, 1, 2]
两个函数都能接受一个关键字参数，用于更复杂的数据结构中：
1 portfolio = [
2 {'name': 'IBM', 'shares': 100, 'price': 91.1},
3 {'name': 'AAPL', 'shares': 50, 'price': 543.22},
4 {'name': 'FB', 'shares': 200, 'price': 21.09},
5 {'name': 'HPQ', 'shares': 35, 'price': 31.75},
6 {'name': 'YHOO', 'shares': 45, 'price': 16.35},
7 {'name': 'ACME', 'shares': 75, 'price': 115.65}
8 ]
9 cheap = heapq.nsmallest(3, portfolio, key=lambda s: s['price'])
10 expensive = heapq.nlargest(3, portfolio, key=lambda s: s['price'])
如果你想在一个集合中查找最小或最大的 N 个元素，并且 N 小于集合元素数量，那么这些函数提供了很好的性能。 因为在底层实现里面，首先会先将集合数据进行堆排序后放入一个列表中：
>>> nums = [1, 8, 2, 23, 7, -4, 18, 23, 42, 37, 2] >>> import heapq >>> heap = list(nums) >>> heapq.heapify(heap) >>> heap [-4, 2, 1, 23, 7, 2, 18, 23, 42, 37, 8] >>>
堆数据结构最重要的特征是 heap[0] 永远是最小的元素。并且剩余的元素可以很容易的通过调用 heapq.heappop() 方法得到， 该方法会先将第一个元素弹出来，然后用下一个最小的元素来取代被弹出元素（这种操作时间复杂度仅仅是 O(log N)，N 是堆大小）。 比如，如果想要查找最小的 3 个元素，你可以这样做：
>>> heapq.heappop(heap) -4 >>> heapq.heappop(heap) 1 >>> heapq.heappop(heap) 2
当要查找的元素个数相对比较小的时候，函数 nlargest() 和 nsmallest() 是很合适的。 如果你仅仅想查找唯一的最小或最大（N=1）的元素的话，那么使用 min() 和 max() 函数会更快些。 类似的，如果 N 的大小和集合大小接近的时候，通常先排序这个集合然后再使用切片操作会更快点 （ sorted(items)[:N] 或者是 sorted(items)[-N:] ）。 需要在正确场合使用函数 nlargest() 和 nsmallest() 才能发挥它们的优势 （如果 N 快接近集合大小了，那么使用排序操作会更好些）。
1.5实现一个优先级队列
下面的类利用 heapq 模块实现了一个简单的优先级队列：
1 import heapq 2 3 class PriorityQueue: 4 def __init__(self): 5 self._queue = [] 6 self._index = 0 7 8 def push(self, item, priority): 9 heapq.heappush(self._queue, (-priority, self._index, item)) 10 self._index += 1 11 12 def pop(self): 13 return heapq.heappop(self._queue)[-1]
>>> 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'), 5)
>>> q.push(Item('spam'), 4)
>>> q.push(Item('grok'), 1)
>>> q.pop()
Item('bar')
>>> q.pop()
Item('spam')
>>> q.pop()
Item('foo')
>>> q.pop()
Item('grok')
>>>
heappop() 函数总是返回”最小的”的元素，这就是保证队列pop操作返回正确元素的关键。 另外，由于 push 和 pop 操作时间复杂度为 O(log N)，其中 N 是堆的大小，因此就算是 N 很大的时候它们运行速度也依旧很快。
在上面代码中，队列包含了一个 (-priority, index, item) 的元组。 优先级为负数的目的是使得元素按照优先级从高到低排序。 这个跟普通的按优先级从低到高排序的堆排序恰巧相反。
index 变量的作用是保证同等优先级元素的正确排序。 通过保存一个不断增加的 index 下标变量，可以确保元素按照它们插入的顺序排序。 而且， index 变量也在相同优先级元素比较的时候起到重要作用。
为了阐明这些，先假定 Item 实例是不支持排序的：
1 >>> a = Item('foo')
2 >>> b = Item('bar')
3 >>> a < b
4 Traceback (most recent call last):
5 File "<stdin>", line 1, in <module>
6 TypeError: unorderable types: Item() < Item()
7 >>>
如果你使用元组 (priority, item) ，只要两个元素的优先级不同就能比较。 但是如果两个元素优先级一样的话，那么比较操作就会跟之前一样出错：
1 >>> a = (1, Item('foo'))
2 >>> b = (5, Item('bar'))
3 >>> a < b
4 True
5 >>> c = (1, Item('grok'))
6 >>> a < c
7 Traceback (most recent call last):
8 File "<stdin>", line 1, in <module>
9 TypeError: unorderable types: Item() < Item()
10 >>>
通过引入另外的 index 变量组成三元组 (priority, index, item) ，就能很好的避免上面的错误， 因为不可能有两个元素有相同的 index 值。Python 在做元组比较时候，如果前面的比较已经可以确定结果了， 后面的比较操作就不会发生了：
>>> a = (1, 0, Item('foo'))
>>> b = (5, 1, Item('bar'))
>>> c = (1, 2, Item('grok'))
>>> a < b
True
>>> a < c
True
>>>