第一章 数据结构与算法

0.保留最后的n个元素。

主要是collections.deque，提供了两端都可以操作的队列。设置了参数maxlen，构造函数会新建一个固定大小的队列。当队列中的数已经达到maxlen， 会从进队列的另一端删除数据。 重点是collections.deque。

1.查找最大或最小的N个元素。

这里主要讲的heapq，heapq模块来建立堆结构(二叉树)。进而进行排序以及搜索。官方文档
这里只是比较了heap[k] <= heap[2*k+1] heap[k] <= heap[2*k+2] 并没有比较左子节点与右子节点的关系。这个需要确认？！

heapq.heappush（heapq，item）
将item推送到堆上，保持堆不变。

heapq.heappop（heapq）
弹出并返回堆中的最小项，保持堆不变。如果堆为空，IndexError则引发。要获取最小的项目而不弹出它，heap[0]。

heapq.heappushpop（heapq，item）
在堆上推送项目，然后弹出并返回堆中的最小项目 。合并后的操作比heappush() 单独调用后更有效heappop()。

heapq.heapify（x）列表就地生成堆。

heapq.heapreplace（heapq，item）
弹出并返回堆中的最小项，并同时推送新项。堆大小不会改变。如果堆为空，IndexError则引发。
这一步操作比heappop()后续操作更有效， heappush()并且在使用固定大小的堆时更合适。pop / push组合总是返回堆中的元素并将其替换为item。
返回的值可能大于添加的项目。如果不需要，请考虑使用heappushpop()。它的推/弹组合返回两个值中较小的一个，在堆上留下较大的值。

该模块还提供三种基于堆的通用功能。

heapq.merge（* iterables，key = None，reverse = False ）
将多个已排序的输入合并为单个排序的输出（例如，合并来自多个日志文件的带时间戳的条目）。返回 排序值上的迭代器。类似sorted(itertools.chain(*iterables))但返回一个iterable，不会同时将数据全部拉入内存，并假设每个输入流已经排序（从最小到最大）。有两个可选参数，必须指定为关键字参数。key指定一个参数的键函数，用于从每个输入元素中提取比较键。默认值为 None（直接比较元素）。reverse是一个布尔值。如果设置为True，则合并输入元素，就好像每个比较都被反转一样。

heapq.nlargest（n，iterable，key = None ）
返回一个列表，其中包含iterable定义的数据集中的n个最大元素 。 key（如果提供）指定一个参数的函数，该函数用于从iterable中的每个元素中提取比较键（例如， ）。相当于： 。key=str.lowersorted(iterable, key=key, reverse=True)[:n]

heapq.nsmallest（n，iterable，key = None ）
返回一个列表，其中包含iterable定义的数据集中的n个最小元素 。 key（如果提供）指定一个参数的函数，该函数用于从iterable中的每个元素中提取比较键（例如， ）。相当于： 。key=str.lowersorted(iterable, key=key)[:n]

后两个函数对于较小的n值表现最佳。对于较大的n值，使用该sorted()函数更有效。此外，何时 n==1使用内置min()和max() 功能更有效。如果需要重复使用这些函数，请考虑将iterable转换为实际堆。

2.字典相关

2.1 defaultdict、setdefault和get

defaultdict 为不存在键设置默认的值的属性。用法是defaultdict(工厂函数)。当获取值的时候会默认返回一个工厂函数生成的值，如a = defaultdict(int), a['b']的返回值是0。 setdefault()是dict的一个方法，当获取的key不存在的时候，会设置一个默认的值，这个跟dict的get方法十分类似，区别在于setdefault()当key不存在时，在将默认值返回的同时，会将默认的值写入原字典中，get()只是将默认值返回,并不修改原来的字典的值。

2.2 字典key的顺序

2.2.1 OrderedDict() 保序字典。内部维护着一个根据键插入顺序排序的双向链表。每次当一个新的 元素插入进来的时候，它会被放到链表的尾部。对于一个已经存在的键的重复赋值不会 改变键的顺序。但值得注意得是，保序字典是普通字典大小得两倍。

2.2.2 sorted() 为根据字典的值进行排序：1. 对key进行排序 sorted(dict) 返回排序后的key的list。 2.对value排序：sorted(dict, key=lambda k:dict[key]),返回对value排序后的key的list。对value排序还有一种方法：sorted(zip(dict.values(), dict.keys)),进行key，value转换，组成元组，然后进行排序。

2.2.3 operator.itemgetter() 函数。上边的基本都对单一的dict对象进行排序。如果对list中多个dict进行单个或者多个的key进行排序，就需要用到itemgetter()方法。

from operator import itemgetter

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}
]
sorted(rows, key=itemgetter('fname'))  # 可用lambda替代  sorted(row, key=lambda x:x['fname'])

# 根据多个key值进行比较
sorted(rows, key=itemgetter("fname", "lname")) # 可用lambda替代sorted(rows, key=lambda x:(x['fname'],x['lname']))

2.3 两个字典间的差异

dict.keys() 返回的是类set的视图("a set-like object providing a view on D's keys")，当源字典开始变化，视图返回的值也会随之变化。
连个字典之间可以通过 & 来获取之间的交集，通过- 来获取之间的差集。通过 | 来获取之前的并集。

3. 命名切片

slice() 函数实现切片对象，主要用在切片操作函数里的参数传递。可以被用在任何切片允许使用的地方。

4.序列中出现次数最多的元素

collections.Counter 类就是为hashable对象计数，是字典的子类，目的用来跟踪值出现的次数，它是一个无序的容器类型，以字典的键值对形式存储，其中元素作为key，其计数作为value。计数值可以是任意的int（包括0和负数）。一个Counter对象就是一个字典，将元素反应到她出现的次数上，其操作跟字典基本类似。

4.1 创建Counter对象

c = Counter()  # 创建一个空的Counter类
c = Counter('gallahad')  # 从一个可iterable对象（list、tuple、dict、字符串等）创建
c = Counter({'a': 4, 'b': 2})  # 从一个字典对象创建
c = Counter(a=4, b=2)  # 从一组键值对创建

4.2 获取其中的值

>>> from collections import Counter
>>> c = Counter(a=4, b=2)  # 从一组键值对创建
>>> c.get('a')
4
>>> c['a']
4
>>> c['c'] # 如果是缺失值的话，会返回0，而不会报错
0

4.3 计数器的更新（update和subtract）

# update 是表示增加
>> c = Counter('which')
>>> c.update('witch')  # 使用另一个iterable对象更新
>>> c['h']
3
>>> d = Counter('watch')
>>> c.update(d)  # 使用另一个Counter对象更新
>>> c['h']
4

#subtract 减去
>>> c = Counter('which')
>>> c.subtract('witch')  # 使用另一个iterable对象更新
>>> c['h']
1
>>> d = Counter('watch')
>>> c.subtract(d)  # 使用另一个Counter对象更新
>>> c['a']
-1

4.4 键的删除

>>> c = Counter("abcdcba")
>>> c
Counter({'a': 2, 'c': 2, 'b': 2, 'd': 1})
>>> c["b"] = 0
>>> c
Counter({'a': 2, 'c': 2, 'd': 1, 'b': 0})
>>> del c["a"]
>>> c
Counter({'c': 2, 'b': 2, 'd': 1})

4.5 算数和集合操作

>>> c = Counter(a=3, b=1)
>>> d = Counter(a=1, b=2)
>>> c + d  # c[x] + d[x]
Counter({'a': 4, 'b': 3})
>>> c - d  # subtract（只保留正数计数的元素）
Counter({'a': 2})
>>> c & d  # 交集:  min(c[x], d[x])
Counter({'a': 1, 'b': 1})
>>> c | d  # 并集:  max(c[x], d[x])
Counter({'a': 3, 'b': 2})

5.通过某个字段将记录分组

itertools.groupby() 函数扫描整个序列并且查找连续相同值 (或者根据指定 key 函数返回值
相同) 的元素序列。在每次迭代的时候，它会返回一个值和一个迭代器对象，这个迭代
器对象可以生成元素值全部等于上面那个值的组中所有对象, 一个非常重要的准备步骤是要根据指定的字段将数据排序。groupby()仅仅检查连续的元素。

6.过滤序列元素

itertools.compress()它以一个 iterable
对象和一个相对应的 Boolean 选择器序列作为输入参数。然后输出 iterable 对象中
对应选择器为 True 的元素。当你需要用另外一个相关联的序列来过滤某个序列的时
候，这个函数是非常有用的。

compress() 函数的关键在于，需要先创建一个Boolean的序列。通过true映射相对应的值。返回一个迭代器。

from itertools import compress

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 = [1, 2, 3, 4, 5, 6, 7, 8]

list(compress(addresses, [n > 5 for n in counts]))

7.ChainMap()

ChainMap()类 接受多个dict并将它们在逻辑上变为一个字典，通过链的方式将多个 dict“链”在一起，从而允许程序可直接获取任意一个 dict 所包含的 key 对应的 value。简单来说，ChainMap 相当于把多个 dict 合并成一个大的 dict，但实际上底层并未真正合并这些 dict，因此程序无须调用多个 update() 方法将多个 dict 进行合并。由于 ChainMap 只是将多个 dict 链在一起，并未真正合并它们，因此在多个 dict 中完全可能具有重复的 key，在这种情况下，排在“链”前面(下标小的)的 dict 中的 key 具有更高的优先级。

ChainMap()通过parents返回新的ChainMap()类来切换优先级，通过new_child()方法来创建新的最高级空dict。其他的方法和操作字典类似。值得注意的是，keys()方法和values()方法返回的值是去重后的。

8.namedtuple 具名元组

collection.namedtuple 是一个工厂函数。它可以用来构建一个带字段名的元组和一个有名字的类——这个带名字的类对调试程序有很大帮助。而且用namedtuple构建的类的实例所消耗的内存和元组是一样的， 因为字段名都被存在对应的类里面。

>>> from collections import namedtuple
>>> Beijing = namedtuple('Beijing', ['dongcheng', 'xicheng'])
>>> beijing = Beijing("001","002")
>>> beijing
Beijing(dongcheng='001', xicheng='002')
>>> beijing[0] # 取值
'001'
>>> beijing[1] # 取值
'002'
>>> beijing.dongcheng
'001'
>>> beijing._fields # 类方法，显示类的属性
('dongcheng', 'xicheng')
>>> beijing._asdict() # 转换成保序字典
OrderedDict([('dongcheng', '001'), ('xicheng', '002')])
>>> beijing._replace(dongcheng = '003') # 替换，返回新的具名元组
Beijing(dongcheng='003', xicheng='002')

9.用bisect来管理已排序的序列官方文档

bisect模块包含两个主要的函数：bisect 和 insort 用来二分查找(返回的是对插入点的下标)和有序队列插入数据(插入后数据仍保序)。

>>> import bisect
>>> a = [1,3,2,4,8,6]
>>> a.sort()
>>> a
[1, 2, 3, 4, 6, 8]
>>> bisect.bisect(a, 5) # bisect 等同于bisect_right 返回插入点的下标
4
>>> a.insert(4, 5)
>>> a
[1, 2, 3, 4, 5, 6, 8]
>>> bisect.insort(a, 7) # insort 等同于 insort_right 保序插入数值
>>> a
[1, 2, 3, 4, 5, 6, 7, 8]