第一章: 数据结构和算法¶

1.3 保留最后N个元素¶

在队列两端插入或删除元素时间复杂度都是 O(1) ，而在列表的开头插入或删除元素的时间复杂度为 O(N) 。

1.4 查找最大或最小的N个元素¶

heapq模块有两个函数：nlargest() 和 nsmallest()

如果你想在一个集合中查找最小或最大的N个元素，并且N小于集合元素数量，那么这些函数提供了很好的性能。因为在底层实现里面，首先会先将集合数据进行堆排序后放入一个列表中：

堆数据结构最重要的特征是 heap[0] 永远是最小的元素。并且剩余的元素可以很容易的通过调用 heapq.heappop() 方法得到，该方法会先将第一个元素弹出来，然后用下一个最小的元素来取代被弹出元素(这种操作时间复杂度仅仅是``O(log N)``，N是堆大小)。

当要查找的元素个数相对比较小的时候，函数 nlargest() 和 nsmallest() 是很合适的。如果你仅仅想查找唯一的最小或最大(N=1)的元素的话，那么使用 min() 和 max() 函数会更快些。类似的，如果N的大小和集合大小接近的时候，通常先排序这个集合然后再使用切片操作会更快点 ( sorted(items)[:N] 或者是 sorted(items)[-N:] )。需要在正确场合使用函数 nlargest() 和 nsmallest() 才能发挥它们的优势 (如果N快接近集合大小了，那么使用排序操作会更好些)。

1.6 字典中的键映射多个值¶

需要注意的是， defaultdict 会自动为将要访问的键(就算目前字典中并不存在这样的键)创建映射实体。如果你并不需要这样的特性，你可以在一个普通的字典上使用 setdefault() 方法来代替。比如：

d = {} # A regular dictionary
d.setdefault('a', []).append(1)
d.setdefault('a', []).append(2)
d.setdefault('b', []).append(4)

一般来讲，创建一个多值映射字典是很简单的。但是，如果你选择自己实现的话，那么对于值的初始化可能会有点麻烦，你可能会像下面这样来实现：

d = {}
for key, value in pairs:
    if key not in d:
        d[key] = []
    d[key].append(value)

如果使用 defaultdict 的话代码就更加简洁了：

d = defaultdict(list)
for key, value in pairs:
    d[key].append(value)

1.7 字典排序¶

OrderedDict 内部维护着一个根据键插入顺序排序的双向链表。每次当一个新的元素插入进来的时候，它会被放到链表的尾部。对于一个已经存在的键的重复赋值不会改变键的顺序。

需要注意的是，一个 OrderedDict 的大小是一个普通字典的两倍，因为它内部维护着另外一个链表。所以如果你要构建一个需要大量 OrderedDict 实例的数据结构的时候(比如读取100,000行CSV数据到一个 OrderedDict 列表中去)，那么你就得仔细权衡一下是否使用 OrderedDict 带来的好处要大过额外内存消耗的影响。

1.9 查找两字典的相同点¶

这些操作也可以用于修改或者过滤字典元素。比如，假如你想以现有字典构造一个排除几个指定键的新字典。下面利用字典推导来实现这样的需求：

# Make a new dictionary with certain keys removed
c = {key:a[key] for key in a.keys() - {'z', 'w'}}
# c is {'x': 1, 'y': 2}

一个字典就是一个键集合与值集合的映射关系。字典的 keys() 方法返回一个展现键集合的键视图对象。键视图的一个很少被了解的特性就是它们也支持集合操作，比如集合并、交、差运算。所以，如果你想对集合的键执行一些普通的集合操作，可以直接使用键视图对象而不用先将它们转换成一个set。

字典的 items() 方法返回一个包含(键，值)对的元素视图对象。这个对象同样也支持集合操作，并且可以被用来查找两个字典有哪些相同的键值对。

尽管字典的 values() 方法也是类似，但是它并不支持这里介绍的集合操作。某种程度上是因为值视图不能保证所有的值互不相同，这样会导致某些集合操作会出现问题。不过，如果你硬要在值上面执行这些集合操作的话，你可以先将值集合转换成set，然后再执行集合运算就行了。

1.10 删除序列相同元素并保持顺序¶

如果序列上的值都是 hashable 类型，那么可以很简单的利用集合或者生成器来解决这个问题。比如：

def dedupe(items):
    seen = set()
    for item in items:
        if item not in seen:
            yield item
        seen.add(item)

下面是使用上述函数的例子：

>>> a = [1, 5, 2, 1, 9, 1, 5, 10]
>>> list(dedupe(a))
[1, 5, 2, 9, 10]
>>>

这个方法仅仅在序列中元素为 hashable 的时候才管用。如果你想消除元素不可哈希(比如 dict 类型)的序列中重复元素的话，你需要将上述代码稍微改变一下，就像这样：

def dedupe(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(a, key=lambda d: (d['x'],d['y'])))
[{'x': 1, 'y': 2}, {'x': 1, 'y': 3}, {'x': 2, 'y': 4}]
>>> list(dedupe(a, key=lambda d: d['x']))
[{'x': 1, 'y': 2}, {'x': 2, 'y': 4}]
>>>

1.12 序列中出现次数最多的元素¶

collections.Counter

Counter 实例一个鲜为人知的特性是它们可以很容易的跟数学运算操作相结合。比如：

1.13 通过某个关键字排序一个字典列表¶

使用 operator 模块的 itemgetter 函数

1.14 排序不支持原生比较的对象¶

选择使用lambda函数或者是 attrgetter() 可能取决于个人喜好。但是， attrgetter() 函数通常会运行的快点，并且还能同时允许多个字段进行比较。这个跟 operator.itemgetter() 函数作用于字典类型很类似(参考1.13小节)。例如，如果 User 实例还有一个 first_name 和 last_name 属性，那么可以向下面这样排序：

by_name = sorted(users, key=attrgetter('last_name', 'first_name'))

同样需要注意的是，这一小节用到的技术同样适用于像 min() 和 max() 之类的函数。比如：

>>> min(users, key=attrgetter('user_id'))
User(3)
>>> max(users, key=attrgetter('user_id'))
User(99)
>>>

有时候，过滤规则比较复杂，不能简单的在列表推导或者生成器表达式中表达出来。比如，假设过滤的时候需要处理一些异常或者其他复杂情况。这时候你可以将过滤代码放到一个函数中，然后使用内建的 filter() 函数。示例如下：

values = ['1', '2', '-3', '-', '4', 'N/A', '5']
def is_int(val):
    try:
        x = int(val)
        return True
    except ValueError:
        return False
ivals = list(filter(is_int, values))
print(ivals)
# Outputs ['1', '2', '-3', '4', '5']

filter() 函数创建了一个迭代器，因此如果你想得到一个列表的话，就得像示例那样使用 list() 去转换。

列表推导和生成器表达式通常情况下是过滤数据最简单的方式。其实它们还能在过滤的时候转换数据。

过滤操作的一个变种就是将不符合条件的值用新的值代替，而不是丢弃它们。

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

1.18 映射名称到序列元素¶

命名元组的一个主要用途是将你的代码从下标操作中解脱出来。因此，如果你从数据库调用中返回了一个很大的元组列表，通过下标去操作其中的元素，当你在表中添加了新的列的时候你的代码可能就会出错了。但是如果你使用了命名元组，那么就不会有这样的顾虑。

命名元组另一个用途就是**作为字典的替代**，因为字典存储需要更多的内存空间。如果你需要构建一个非常大的包含字典的数据结构，那么使用命名元组会更加高效。但是需要注意的是，不像字典那样，一个**命名元组是不可更改**的。比如：

如果你真的需要改变属性的值，那么可以使用命名元组实例的 _replace() 方法，它会创建一个全新的命名元组并将对应的字段用新的值取代。

>>> s = Stock('ACME', 100, 123.45)
>>> s
Stock(name='ACME', shares=100, price=123.45)
>>> s.shares = 75
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
AttributeError: can't set attribute
>>>

>>> s = s._replace(shares=75)
>>> s
Stock(name='ACME', shares=75, price=123.45)
>>>

最后要说的是，如果你的目标是定义一个需要更新很多实例属性的高效数据结构，那么命名元组并不是你的最佳选择。这时候你应该考虑定义一个包含 __slots__ 方法的类(参考8.4小节)。

1.19 转换并同时计算数据¶

在使用一些聚集函数比如 min() 和 max() 的时候你可能更加倾向于使用生成器版本，它们接受的一个key关键字参数或许对你很有帮助。比如，在上面的证券例子中，你可能会考虑下面的实现版本：

# Original: Returns 20
min_shares = min(s['shares'] for s in portfolio)
# Alternative: Returns {'name': 'AOL', 'shares': 20}
min_shares = min(portfolio, key=lambda s: s['shares'])

1.20 合并多个字典或映射¶

现在假设你必须在两个字典中执行查找操作(比如先从 a 中找，如果找不到再在 b 中找)。一个非常简单的解决方案就是使用 collections 模块中的 ChainMap 类

一个 ChainMap 接受多个字典并将它们在逻辑上变为一个字典。然后，这些字典并不是真的合并在一起了， ChainMap 类只是在内部创建了一个容纳这些字典的列表并重新定义了一些常见的字典操作来遍历这个列表。大部分字典操作都是可以正常使用的.

如果出现重复键，那么第一次出现的映射值会被返回。因此，例子程序中的 c['z'] 总是会返回字典 a 中对应的值，而不是 b 中对应的值。

作为 ChainMap 的替代，你可能会考虑使用 update() 方法将两个字典合并。比如：

>>> a = {'x': 1, 'z': 3 }
>>> b = {'y': 2, 'z': 4 }
>>> merged = dict(b)
>>> merged.update(a)
>>> merged['x']
1
>>> merged['y']
2
>>> merged['z']
3
>>>

这样也能行得通，但是它需要你创建一个完全不同的字典对象(或者是破坏现有字典结构)。同时，如果原字典做了更新，这种改变不会反应到新的合并字典中去。

>>> a['x'] = 13
>>> merged['x']
1

ChainMap 使用原来的字典，它自己不创建新的字典。所以它并不会产生上面所说的结果，比如：

>>> a = {'x': 1, 'z': 3 }
>>> b = {'y': 2, 'z': 4 }
>>> merged = ChainMap(a, b)
>>> merged['x']
1
>>> a['x'] = 42
>>> merged['x'] # Notice change to merged dicts
42
>>>