本文为PythonCookbook的读书笔记，主要是对知识点的总结
本章主要内容是一些简单的数据结构的操作
Table of Contents
Python 提供了大量的内置数据结构，包括列表，集合以及字典。大多数情况下使用这些数据结构是很简单的。但是，我们也会经常碰到到诸如查询，排序和过滤等等这些普遍存在的问题。因此，这一章的目的就是讨论这些比较常见的问题和算法。另外，也会给出在模块 collections 中操作这些数据结构的方法。
from IPython.core.interactiveshell import InteractiveShell
InteractiveShell.ast_node_interactivity = "all"
1.1 解压序列赋值给多个变量¶
实际上就是序列解包问题，用于接收的变量数量要保持和序列内的变量数量一样。如果数量不匹配会产生异常，如果想丢弃某些值，可以用不常用的名字占位，然后丢弃即可。这种解包可以用在任何可迭代对象上，不仅仅是 list tuple，包括字符串，文件对象，迭代器生成器等。
p = (4, 5)
x, y = p
x
y
data = [ 'ACME', 50, 91.1, (2012, 12, 21) ]
name, shares, price, date = data
name,shares,price,date
1.2 解压可迭代对象赋值给多个变量¶
在解包的时候利用 * 操作符来接受多个值
record = ('Dave', 'dave@example.com', '773-555-1212', '847-555-1212')
name, email, *phone_numbers = record
name, email,phone_numbers
无论如何 phone_numbers 解压出来都是 list 类型，就算只有 0 个元素
还可以利用 * 解包实现递归
def sum(items):
head, *tail = items
return head + sum(tail) if tail else head
items = list(range(20))
sum(items)
Python 并不擅长递归
1.3 保留最后 N 个元素¶
利用 collections 库中的 deque，通过 maxlen 参数设置其最大长度
或者可以利用 % 手动实现一个环形 buf 区
from collections import deque
def search(lines, pattern, history=5):
previous_lines = deque(maxlen=history)
for li in lines:
if pattern in li:
yield li, previous_lines
previous_lines.append(li)
# Example use on a file
if __name__ == '__main__':
with open('data/somefile.txt', 'r') as f:
for line, prevlines in search(f, 'is', 5):
for pline in prevlines:
print(pline, end='')
print(line, end='')
print('-' * 20)
deque 还实现了 appendleft appendright popleft popright 等方法。
在队列两端插入或删除元素时间复杂度都是 O(1)，而在列表的开头插入或删除元素的时间复杂度为 O(N)
1.4 查找最大或最小的N 个元素¶
问题
集合里面，求最大或者最小的 N 个元素
解决
heapq模块有两个函数：nlargest() 和 nsmallest() 可以完美解决这个问题。（其实是利用了堆排序的性质）
import heapq
nums = [1, 8, 2, 23, 7, -4, 18, 23, 42, 37, 2]
heapq.nlargest(3, nums)
heapq.nsmallest(3, nums)
可以使用 key 参数，以支持更复杂的数据结构：
cheap = heapq.nsmallest(3, portfolio, key=lambda s: s['price'])
讨论
在底层实现里面，首先会先将集合数据进行堆排序后放入一个列表中：
>>> nums = [1, 8, 2, 23, 7, -4, 18, 23, 42, 37, 2]
>>> import heapq
>>> heapq.heapify(nums)
>>> nums
[-4, 2, 1, 23, 7, 2, 18, 23, 42, 37, 8]
堆数据结构最重要的特征是 heap[0] 永远是最小的元素，该方法会先将第一个元素弹出来，然后用下一个最小的元素来取代被弹出元素(这种操作时间复杂度仅仅是O(log N)，N是堆大小)。
>>> heapq.heappop(nums)
-4
>>> heapq.heappop(nums)
1
>>> heapq.heappop(nums)
2
注意
如果你仅仅想查找唯一的最小或最大(N=1)的元素的话，使用 min() 和 max() 函数
如果N的大小和集合大小接近的时候，先排序这个集合然后再使用切片
使用 heap 的场景是需要的 n 不是太大也不是太小
1.5 实现一个优先级队列¶
实现一个按优先级排序的队列 并且在这个队列上面每次pop操作总是返回优先级最高的那个元素
一种方式是使用堆，不过每个元素不仅仅包括了值，还包括了优先级，于是堆按照优先级进行处理操作
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]
class Item:
def __init__(self, name):
self.name = name
def __repr__(self):
return f'Item({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._queue
q.pop()
q.pop()
q.pop()
q.pop()
如果两个有着相同优先级的元素( foo 和 grok )，pop操作按照它们被插入到队列的顺序返回的。
讨论
函数 heapq.heappush() 和 heapq.heappop()分别在队列 _queue 上插入和删除第一个元素， 并且队列_queue保证第一个元素拥有最高优先级。 heappop() 函数总是返回”最小的”的元素，这就是保证队列pop操作返回正确元素的关键。 另外，push和pop操作时间复杂度为O(log N)
在上面代码中，队列包含了一个 (-priority, index, item) 的元组。 优先级为负数的目的是使得元素按照优先级从高到低排序。
index 变量的作用是保证同等优先级元素的正确排序
Python 中的元祖排序，默认是按照元祖内元素从前到后进行排序的
如果想在多个线程中使用同一个队列，那么你需要增加适当的锁和信号量机制。
1.6 字典中的键映射多个值¶
实现一个键对应多个值的字典(也叫 multidict )？
依旧是依靠字典一个键对应一个值，但是这个值可以是列表之类的，这样就实现了一个键对应多个值了。
使用 collections 模块中的 defaultdict defaultdict 会自动初始化每个 key 刚开始对应的值，只需要添加元素即可
from collections import defaultdict
d = defaultdict(list)
d['a'].append(1)
d['a'].append(2)
d['b'].append(4)
d = defaultdict(set)
d['a'].add(1)
d['a'].add(2)
d['b'].add(4)
d
创建一个多值映射字典是很简单的。但是，如果自己实现的话，值的初始化可能会有点麻烦
这样
d = {}
for key, value in pairs:
if key not in d:
d[key] = []
d[key].append(value)
或者这样
d = {} # A regular dictionary
d.setdefault('a', []).append(1)
如果使用 defaultdict 的话代码就更加简洁了：
d = defaultdict(list)
for key, value in pairs:
d[key].append(value)
from collections import OrderedDict
d = OrderedDict()
d['foo'] = 1
d['bar'] = 2
d['spam'] = 3
d['grok'] = 4
for key in d:
print(key, d[key])
d
当你想要构建一个将来需要序列化或编码成其他格式的映射的时候， OrderedDict 是非常有用的。 比如，你想精确控制以JSON编码后字段的顺序
import json
print(json.dumps(d,indent=2))
OrderedDict 内部维护着一个根据键插入顺序排序的双向链表。每次当一个新的元素插入进来的时候， 它会被放到链表的尾部。对于一个已经存在的键的重复赋值不会改变键的顺序。
需要注意的是，OrderedDict 的大小是普通字典的两倍，因为它内部维护着另外一个链表。
权衡一下是否需要使用 OrderedDict 带来的好处要大过额外内存消耗的影响。
prices = {
'ACME': 45.23,
'AAPL': 612.78,
'IBM': 205.55,
'HPQ': 37.20,
'FB': 10.75
}
min_price = min(zip(prices.values(), prices.keys()))
min_price
max_price = max(zip(prices.values(), prices.keys()))
max_price
prices_sorted = sorted(zip(prices.values(), prices.keys()))
prices_sorted
zip() 函数创建的是一个只能访问一次的迭代器
方式二，利用 min 或 max 的 key 参数
min(prices.values())
max(prices, key=lambda k: prices[k])
当多个实体拥有相同的值的时候，键会决定返回结果。 比如，在执行 min() 和 max() 操作的时候，如果恰巧最小或最大值有重复的，那么拥有最小或最大键的实体会返回。
a = {
'x' : 1,
'y' : 2,
'z' : 3
}
b = {
'w' : 10,
'x' : 11,
'y' : 2
}
# Find keys in common
a.keys() & b.keys()
# Find keys in a that are not in b
a.keys() - b.keys()
# Find (key,value) pairs in common
a.items() & b.items()
字典的 keys() 方法返回一个展现键集合的键视图对象 键视图也支持集合操作不用转换成set
字典的 values() 方法也是类似，但是它并不支持集合操作。 某种程度上是因为值视图不能保证所有的值互不相同。
如果非要堆 对 values() 进行集合操作，可以先 set() 一下
def dedupe_1(items):
seen = set()
for item in items:
if item not in seen:
yield item
seen.add(item)
如果你想消除元素不可哈希(比如 dict 类型)
def dedupe_2(items, key=None):
seen = set()
for item in items:
val = item if key is None else key(item)
if val not in seen:
yield item
seen.add(val)
这里的key参数指定了一个函数，将序列元素转换成 hashable 类型
a = [ {'x':1, 'y':2}, {'x':1, 'y':3}, {'x':1, 'y':2}, {'x':2, 'y':4}]
list(dedupe_2(a, key=lambda d: (d['x'],d['y'])))
list(dedupe_2(a, key=lambda d: d['x']))
如果只需要消除重复元素，通常可以简单的构造一个集合，但是这样会打乱原序列的顺序。
内置的 slice() 函数创建了一个切片对象，slice() 接受三个参数，start stop step 可以被用在任何切片允许使用的地方。
items = [0, 1, 2, 3, 4, 5, 6]
a = slice(2, 4)
items[2:4]
items[a]
items[a] = [10,11]
items
del items[a]
items
注意¶
ls = list(range(10))
sl = ls[0:2]
del sl
ls
del ls[0:2]
ls
虽然切片返回浅拷贝对象，但切片本身仍然指向原始目标
如果你有一个切片对象a，你可以分别调用它的 a.start , a.stop , a.step 属性来获取更多的信息
a = slice(5, 50, 2)
a.start
a.stop
a.step
另外，你还能通过调用切片的 indices(size) 方法将它映射到一个确定大小的序列上， 这个方法返回一个三元组 (start, stop, step) ，所有值都会被合适的缩小以满足边界限制，避免出现 IndexError 异常。
s = 'HelloWorld'
a.indices(len(s))
words = [
'look', 'into', 'my', 'eyes', 'look', 'into', 'my', 'eyes',
'the', 'eyes', 'the', 'eyes', 'the', 'eyes', 'not', 'around', 'the',
'eyes', "don't", 'look', 'around', 'the', 'eyes', 'look', 'into',
'my', 'eyes', "you're", 'under'
]
from collections import Counter
word_counts = Counter(words)
top_three = word_counts.most_common(3)
top_three
作为输入， Counter 对象可以接受任意的由可哈希(hashable)元素构成的序列对象。 在底层实现上，一个 Counter 对象就是一个字典，将元素映射到它出现的次数上。
增加计数：
1.手动增加计数，可以简单的用加法：
word_counts['the'] += 1
2.使用 update() 方法
morewords = ['why','are','you','not','looking','in','my','eyes']
word_counts.update(morewords)
Counter 实例可以跟数学运算操作或者说是集合操作相结合
a = Counter(words)
b = Counter(morewords)
a
b
c = a + b
c
d = a - b
d
rows = [
{'fname': 'Brian', 'lname': 'Jones', 'uid': 1003},
{'fname': 'David', 'lname': 'Beazley', 'uid': 1002},
{'fname': 'John', 'lname': 'Cleese', 'uid': 1001},
{'fname': 'Big', 'lname': 'Jones', 'uid': 1004}
]
from operator import itemgetter
rows_by_fname = sorted(rows, key=itemgetter('fname'))
rows_by_fname
itemgetter() 函数也支持多个keys，在比较的时候按顺序进行比较
rows_by_lfname = sorted(rows, key=itemgetter('lname','fname'))
rows_by_lfname
operator.itemgetter() 函数的参数可以是一个字典键名称， 一个整形值或者任何能够传入一个对象的 __getitem__() 方法的值。
itemgetter() 有时候也可以用 lambda 表达式代替，感觉itemgetter()就是一个闭包或者类
rows_by_fname = sorted(rows, key=lambda r: r['fname'])
使用 itemgetter() 会稍微快点。因此如果你对性能要求比较高的话就使用 itemgetter() 方式
这样的技术也同样适用于 min() 和 max() 等函数
排序不支持原生比较的对象¶
内置的 sorted() 函数有一个关键字参数 key ，可以传入 callable 对象
对于类对象一种方法是使用 operator.attrgetter() 另一种则是使用 lambda 函数
from operator import attrgetter
class User:
def __init__(self, user_id):
self.user_id = user_id
def __repr__(self):
return 'User({})'.format(self.user_id)
def sort_notcompare():
users = [User(23), User(3), User(99)]
print(users)
print(sorted(users, key=lambda u: u.user_id)) # 方法一
print(sorted(users, key=attrgetter('user_id'))) # 方法二
sort_notcompare()
attrgetter()函数通常会快点，并且还能同时允许多个字段进行比较
rows = [
{'address': '5412 N CLARK', 'date': '07/01/2012'},
{'address': '5148 N CLARK', 'date': '07/04/2012'},
{'address': '5800 E 58TH', 'date': '07/02/2012'},
{'address': '2122 N CLARK', 'date': '07/03/2012'},
{'address': '5645 N RAVENSWOOD', 'date': '07/02/2012'},
{'address': '1060 W ADDISON', 'date': '07/02/2012'},
{'address': '4801 N BROADWAY', 'date': '07/01/2012'},
{'address': '1039 W GRANVILLE', 'date': '07/04/2012'},
]
from operator import itemgetter
from itertools import groupby
rows.sort(key=itemgetter('date'))
rows
for date, items in groupby(rows, key=itemgetter('date')):
print(date)
for i in items:
print(' ', i)
讨论
groupby() 函数扫描整个序列并且查找连续相同值(或者根据指定key函数返回值相同)的元素序列。在每次迭代时，它会返回一个值和一个迭代器
有两点需要注意的地方：
1.groupby() 仅仅检查连续的元素，事先需要根据指定的字段将数据排序
2.如果只是想根据 date 字段将数据分组到一个大的数据结构中去，并且允许随机访问，最好使用 defaultdict() 构建多值字典
from collections import defaultdict
rows_by_date = defaultdict(list)
for row in rows:
rows_by_date[row['date']].append(row)
rows_by_date
这种方式会比先排序然后再通过 groupby() 函数迭代的方式运行得快一些。
过滤序列元素¶
有一个序列，用一些规则从中提取出需要的值
最简单的过滤序列元素的方法就是使用列表推导,为了避免对内存的过度消耗，可以考虑换用生成器表达式
如果过滤规则过于复杂，则可以将过滤操作放在一个函数中，然后使用 filter() 进行过滤，注意 filter()返回迭代器
列表和生成器表达式不仅可以过滤，还可以在过滤的过程中替换数据，配合 python 三元表达式食用效果更佳
mylist = [1, 4, -5, 10, -7, 2, 3, -1]
clip_neg = [n if n > 0 else 0 for n in mylist]
clip_neg
clip_pos = [n if n < 0 else 0 for n in mylist]
clip_pos
另外一个值得关注的过滤工具是 itertools.compress() 它以一个 iterable 对象和一个相对应的 Boolean 选择器序列作为输入参数。 然后输出 iterable 对象中对应选择器为 True 的元素.
addresses = [
'5412 N CLARK',
'5148 N CLARK',
'5800 E 58TH',
'2122 N CLARK',
'5645 N RAVENSWOOD',
'1060 W ADDISON',
'4801 N BROADWAY',
'1039 W GRANVILLE',
]
counts = [ 0, 3, 10, 4, 1, 7, 6, 1]
from itertools import compress
more5 = [n > 5 for n in counts]
more5
list(compress(addresses, more5))
p1 = {key: value for key, value in prices.items() if value > 200}
p1
大多数情况下字典推导能做到的，通过创建一个元组序列然后把它传给 dict() 函数也能实现。
p1 = dict((key, value) for key, value in prices.items() if value > 200)
p1
字典推导方式表意更清晰，并且实际上也会运行的更快些
映射名称到序列元素¶
有一段通过客户访问列表或者元组中元素的代码，但是这样有时候会使得你的代码难以阅读， 于是你想通过名称来访问元素
命名元组：collections.namedtuple() 函数通过使用一个普通的元组对象来帮你解决这个问题。
from collections import namedtuple
Subscriber = namedtuple('Subscriber', ['addr', 'joined'])
sub = Subscriber('jonesy@example.com', '2012-10-19')
sub
sub.addr
sub.joined
namedtuple 看起来像一个普通的类实例，但是它跟元组类型是可交换的，支持所有的普通元组操作，比如索引和解压。
命名元组的一个优点就是作为字典的替代，因为字典存储需要更多的内存空间。 如果你需要构建一个非常大的包含字典的数据结构，那么使用命名元组会更加高效。
但是，不像字典那样，命名元组是不可更改的
如果你真的需要改变属性的值，那么可以使用命名元组实例的 _replace() 方法， 它会创建一个全新的命名元组并将对应的字段用新的值取代
Stock = namedtuple('Stock', ['name', 'shares', 'price'])
s = Stock('ACME', 100, 123.45)
try:
s.shares=75
except Exception as e:
print(e)
s = s._replace(shares=75)
s
_replace() 方法还有一个很有用的特性就是当你的命名元组拥有可选或者缺失字段时候， 它是一个非常方便的填充数据的方法。 你可以先创建一个包含缺省值的原型元组，然后使用 _replace() 方法创建新的值被更新过的实例
from collections import namedtuple
Stock = namedtuple('Stock', ['name', 'shares', 'price', 'date', 'time'])
stock_prototype = Stock('', 0, 0.0, None, None)
def dict_to_stock(s):
return stock_prototype._replace(**s)
a = {'name': 'ACME', 'shares': 100, 'price': 123.45}
dict_to_stock(a)
b = {'name': 'ACME', 'shares': 100, 'price': 123.45, 'date': '12/17/2012'}
dict_to_stock(b)
如果要定义一个需要更新很多实例属性的高效数据结构，那么命名元组并不是你的最佳选择。这时候你应该考虑定义一个包含 slots 方法的类
转换并同时计算数据¶
需要在数据序列上执行聚集函数(比如 sum() , min() , max() )， 但是需要首先转换或过滤数据
一个非常优雅的方式去结合数据计算与转换就是使用一个生成器表达式参数。
nums = [1, 2, 3, 4, 5]
s = sum(x * x for x in nums)
s
语法：
当生成器表达式作为一个单独参数传递给函数时候的巧妙语法(你并不需要多加一个括号)
s = sum((x * x for x in nums)) # 显式的传递一个生成器表达式对象
s = sum(x * x for x in nums) # 更加优雅的实现方式，省略了括号
使用一个生成器表达式作为参数会比先创建一个临时列表更加高效和优雅
from collections import ChainMap
a = {'x': 1, 'z': 3 }
b = {'y': 2, 'z': 4 }
c = ChainMap(a,b)
print(c['x'])
print(c['y'])
print(c['z'])
ChainMap 接受多个字典并将它们在逻辑上变为一个字典。 然后，这些字典并不是真的合并在一起了， ChainMap 类只是在内部创建了一个容纳这些字典的列表 并重新定义了一些常见的字典操作来遍历这个列表。大部分字典操作都是可以正常使用的。
如果出现重复键，那么第一次出现的映射值会被返回，对于字典的更新或删除操作总是影响的是列表中第一个字典
new_child() parents() 以及 update() 方法
ChainMap 对于编程语言中的作用范围变量(比如 globals , locals 等)是非常有用的
values = ChainMap()
values['x'] = 1
values
# Add a new mapping
values = values.new_child()
values['x'] = 2
values
# Add a new mapping
values = values.new_child()
values['x'] = 3
values
values['x']
# Discard last mapping
values = values.parents
values['x']
# Discard last mapping
values = values.parents
values['x']
values
也可以使用 update() 方法合并两个字典，这会创建一个完全不同的字典对象(或者是破坏现有字典结构), ChainMap 执行 inplace 操作