6.3　使用标准库的扩展

我们会介绍标准库中一些对内置类型的扩展实现。这些是扩展或者修改了内置集合类的类型。在诸如Python 3 Object Oriented Programming这样的书中，已经用不同的方式介绍了它们中的大多数。

我们会介绍下面6个集合函数。

• namedtuple()函数会创建允许包含可命名属性的tuple类，我们可以使用这个函数而不是额外完整地定义一个仅仅为属性值命名的类。
• deque（注意这种不规则的拼写方式）是一个双端队列，一个类似list的集合，但是可以在任何一段快速地进行增加和弹出操作。可以用这个类的其中一部分属性来创建常规的栈或队列。
• 在一些情况下，我们可以使用ChainMap，而不是合并不同的映射。这是一个将多个映射连接起来的方法。
• 一个OrderedDict集合是会保持所有元素原始插入顺序的一种映射。
• defaultDict（注意这种不规则的拼写方式）是dict的一个子类，它内部使用一个工厂函数为所有没有值的键提供默认值。
• Counter也是一个dict的子类，它可以被用来统计对象，进而创建频率表。但是，它实际上是一个更复杂的数据结构，通常我们称为多重集合（multiset）或者包（bag）。

我们会看到上述每一个集合的示例。通过学习这些库集合，我们应该学会很重要的两课。

• 什么是已经存在而不需要我们自己重新创建的。
• 如何通过扩展抽象基类的方式向Python语言中添加有趣且有用的新结构。

同时，阅读库的源码也非常重要。这些源码会向我们展示许多Python中使用的面向对象编程技术。除了这些基本的集合外，主要就是模块了，如下所述。

• Heapq模块是包含了一系列将堆队列（heap queue）的属性添加到一个现有的list对象上的函数。堆队列的不变性是指堆上的所有元素按顺序存储，这样可以对堆队列进行升序的快速检索。如果我们在一个list结构上使用heapq方法，我们就不再需要显式地排序列表。这个方法可以带来很大的性能提升。
• array模块是一种对特定值的存储方式进行优化的序列，这为包括了大量简单值的集合提供了一些类似列表的特性。

6.3.1　namedtuple()函数

namedtuple()函数根据提供的参数创建一个新类。这个类会有一个类名，一些字段名和一对可选的用于定义类行为的关键字。

使用namedtuple()会将类定义浓缩成在一个很短的不可变对象的定义中。在我们需要一组命名属性的时候，它让我们不用再编写冗长而复杂的类定义。

比如，对于打牌，我们可能会想将下面的代码加入类定义中。

from collections import namedtuple
BlackjackCard = namedtuple('BlackjackCard','rank,suit,hard,soft')

我们定义了一个新的类，它带有4个命名属性：rank、suit、hard和soft。由于这些对象都是不可变的，因此我们不需要担心一个不守规矩的程序试图修改一个BlackjackCard实例的rank值。

我们可以用一个工厂函数创建这个类的不同实例，如下所示。

def card( rank, suit ):
　　if rank == 1:
　　　　return BlackjackCard( 'A', suit, 1, 11 )
　　elif 2 <= rank < 11:
　　　　return BlackjackCard( str(rank), suit, rank, rank )
　　elif rank == 11:
　　　　return BlackjackCard( 'J', suit, 10, 10 )
　　elif rank == 12:
　　　　return BlackjackCard( 'Q', suit, 10, 10 )
　　elif rank == 13:
　　　　return BlackjackCard( 'K', suit, 10, 10 )

上面的代码会根据不同的牌面值创建带有正确软总和和硬总和的BlackjackCard实例。通过用不同的参数填充tuple的子类模板，最终会创建一个名为namedtuple的新类。基本上，这种模板都是以类似下面这样的代码开始的。

class TheNamedTuple(tuple):
　　slots = ()
　　fields = {fieldnames!r}
　　def new(_cls, {arg_list}):
　　　　return _tuple.__new(_cls, ({arg_list}))

模板代码扩展了内置的tuple类，这里没有其他特殊的地方。

它将slots设为空元组。有两种方式来管理实例变量：slots和dict。通过设置了slots，dict被禁止修改，同时也保证了不会有新的实例变量被添加到这个类的对象中。此外，生成的对象依然保持在最小的大小。

模板中创建了一个名为_fields的类级变量，这个变量用于为类中的字段命名。{field_names!r}用于接收字段名列表。

模板定义了一个new()方法用来初始化不可变对象。{arg_list}被用来接收定义如何创建每个实例的参数列表。

还有其他的一些方法函数，以上介绍为了解namedtuple函数是如何工作的提供了一些提示。

当然，我们可以继承一个namedtuple类，然后添加新的属性。但是，当我们试图往namedtuple类中添加新的属性时，必须非常小心。属性的列表和new()的参数会编码后存储在_fields中。

下面是一个继承namedtuple类的例子：

BlackjackCard = namedtuple('BlackjackCard','rank,suit,hard,soft')
class AceCard( BlackjackCard ):
　　slots = ()
　　def new( self, rank, suit ):
　　　　return super().new( AceCard, 'A', suit, 1, 11 )

我们用slots保证子类中没有dict，我们无法添加任何新属性。我们重载了new()，这样我们就可以只用两个值（rank和suit）构造实例，但是重载的new()会填充所有的4个值。

6.3.2　deque类

一个list对象旨在为容器内的任何位置元素的修改提供一致的性能。但是，有一些操作会损失性能。最值得注意的是，任何在list头部的操作（list.insert(0, item)或者list.pop(0)）都会损失一些性能，因为列表的大小改变了，同时所有元素的位置也改变了。

deque——一个双向队列——旨在为列表中的第1个和最后一个元素提供一致的性能。它的追加和弹出操作会比内置的list对象快。

通过总是从尾部弹出，一副牌的设计避免了list对象潜在的性能缺陷。

但是，由于我们只使用了list对象中很少的一部分特性，或许一个像deque这样的结构能够更好地适应我们的需求。我们只是用list存储所有的牌，这样就可以实现洗牌和从集合中弹出的操作。除了洗牌，我们的程序从未通过下标访问元素。

尽管deque.pop()方法可能非常快，但是不是非常适合洗牌操作。洗牌会随机地访问容器中的元素，deque并不是为这种操作所设计的。

为了找出潜在的开销，我们可以像下面这样，用timeit来比较用list和deque洗牌的性能。

>>> timeit.timeit('random.shuffle(x)',"""
… import random
… x=list(range(652))""")
597.951664149994
>>>
>>> timeit.timeit('random.shuffle(d)',"""
… from collections import deque
… import random
… d=deque(range(652))""")
609.9636979339994

我们使用random.shuffle()调用timeit。一个基于list对象，另一个基于deque。

结果说明deque的洗牌操作仅仅比list慢一点——大约慢2%，这样的差别可以忽略不计。我们可以很自信地尝试将list换成deque。

需要做的修改如下。

from collections import dequeue
class Deck(dequeue):
　　def init( self, size=1 ):
　　　　super().init()
　　　　for d in range(size):
　　　　　 cards = [ card(r,s) for r in range(13) for s in Suits ]
　　　　　 super().extend( cards )
　　　　random.shuffle( self )

在Deck的定义中，我们把list换成了deque，其他部分保持不变。

现在性能的差别有多大呢？让我们测试一下创建100000张牌的性能。

>>> timeit.timeit('x.pop()', "x=list(range(100000))",
number=100000)
0.032304395994287916
>>> timeit.timeit('x.pop()', "from collections import deque;
x=deque(range(100000))", number=100000)
0.013504189992090687

这里，我们用了x.pop()来调用timeit。一个基于list，另一个基于deque。

处理时间几乎减少了一半（准确地说是42%）。数据结构上的一个小改变为我们节省了大量的开销。

通常，为程序选择最优的数据结果是非常重要的。多尝试几种不同的数据结构可以告诉我们哪一种更高效。

6.3.3　使用ChainMap

将映射连接在一起的场景非常符合Python中关于本地与全局的概念。当我们在Python中使用一个变量时，会按照先本地命名空间、后全局命名空间的顺序搜索这个变量。除了搜索这两种命名空间外，Python还会在本地命名空间中设置一个变量，但是这个变量不会影响到全局命名空间。这种默认的行为（没有使用global或者nonlocal语句）也是ChainMap的工作方式。

当我们的程序开始运行时，我常常会从命令行参数、配置文件、操作系统环境变量甚至有可能是基于安装范围的配置中获取属性。我们希望可以将这些属性整合到一个类似于字典的结构中，这样我们就可以轻易地对配置进行定位。

不使用类似下面这样的程序启动代码，它结合了多个不同来源的配置选项。

import argparse
import json
import os
parser = argparse.ArgumentParser(description='Process some
integers.')
parser.add_argument( "-c", "—configuration", type=open,
nargs='?')
parser.add_argument( "-p", "—playerclass", type=str, nargs='?',
default="Simple" )
cmdline= parser.parse_args('-p Aggressive'.split())

if cmdline.configuration:
　　config_file= json.load( options.configuration )
　　options.configuration.close()
else:
　　config_file= {}

with open("defaults.json") as installation:
　　defaults= json.load( installation )
# Might want to check ~/defaults.json and
/etc/thisapp/defaults.json, also.

from collections import ChainMap
options = ChainMap(vars(cmdline), config_file, os.environ,
defaults)

上面的代码向我们展示不同来源的配置，有如下几种。

• 命令行参数。我们看到了一个令牌参数——playerclass，但是通常还会有许多其他这样的参数。
• 其中一个参数——configuration，是带有一些额外参数的配置文件的文件名。这个参数应该用JSON表示并且会读取这个文件的内容。
• 此外，还有一个defaults.json文件以及另外一个可以寻找配置值的地方。

基于上面的代码，我们可以建立一个单一的ChainMap对象使用案例，在这个案例中，我们可以在指定的位置中查找参数。ChainMap实例会按顺序在每一个映射中搜索指定值。这为我们提供了一种简洁、易于使用的处理运行时选项和参数的方法。

在第13章“配置文件和持久化”和第16章“使用命令行”中，我们会再次探讨这个主题。

6.3.4　OrderedDict集合

OrderedCollection集合很聪明地使用了两种存储结构。使用一个基本的dict对象类型用来匹配键和值。另外，使用存储了键的双向列表用来维护插入顺序。

OrderedDict的一个常用场景是处理HTML或者XML文件，这些文件中对象的顺序必须保留，但是对象之间有可能通过ID或者IDREF属性互相引用。通过将ID用作字典的键，我们可以优化对象间的这种关系。我们可以使用OrderedDict结构保持源文档中对象的顺序。

这里不想将处理XML作为探讨的主题，这是第9章“序列化和保存——JSON、YAML、Pickle、CSV和XML”的主题。

考虑这个简短的示例XML文档，该文档索引之间包含非常复杂的引用。我们假设这是一个微型博客的源文件，它包含了具有ID属性的一系列有序的元素，同时也包含了使用IDREF属性引用原始元素的索引。

我们将这个XML分为两个部分。

<blog>
　　<topics> … </topics> <indices> … </indices>
</blog>

topics和indices会各有它们自己的内容，下面是这个博客中topics的部分。

　　<topics>
　　　　<entry ID="UUID98766"><title>first</title><body>more
　　　　　words</body></entry>
　　　　<entry
　　ID="UUID86543"><title>second</title><body>words</body></entry>
　　　　<entry
ID="UUID64319"><title>third</title><body>text</body></entry>
　　</topics>

每一个topics都包含一系列的entry。每一个entry都有一个唯一的ID。这里在暗示它们应该属于通用唯一标识符（Universally Unique ID，UUID），但我们还没有给出实际的例子。

下面是博客中表示indices的XML代码。

<indices>
　　<bytag>
　　　　<tag text="#sometag">
　　　　　　<entry IDREF="UUID98766"/>
　　　　　　<entry IDREF="UUID86543"/>
　　　　</tag>
　　　　<tag text="#anothertag">
　　　　　　<entry IDREF="UUID98766"/>
　　　　　　<entry IDREF="UUID64319/>
　　　　</tag>
　　</bytag>
</indices>

indices中的每个元素通过tag来表示。可以看到，每个tag中都包括了一个entry的列表。每一个entry都包含了一个指向原始博客对应元素的引用。

下面的代码会解析源文件并且生成一个OrderedDict集合。

from collections import OrderedDict
import xml.etree.ElementTree as etree

doc= etree.XML( source ) # Parse

topics= OrderedDict() # Gather
for topic in doc.findall( "topics/entry" ):
　　topics[topic.attrib['ID']] = topic
for topic in topics: # Display
　　print( topic, topics[topic].find("title").text )

第1部分，# Parse，会解析XML源文件，然后创建一个ElementTree对象。

第2部分，# Gather，会遍历topics中所有的entry。topics中的每一个元素都会根据ID存入OrderedDict集合中。元素间原本的顺序会被保留，这样就可以按正确的顺序呈现出来。

最后一部分，# Display，会以原始顺序显示entry和它们的ID。

6.3.5　defaultdict子类

当一个键不存在时，默认的dict类型会抛出一个异常。defaultdict集合类型会执行一个给定的函数，并将执行结果作为这个不存在的键值存入字典中。

defaultdict类的一个常见应用是为对象创建索引。当有一些对象共同包含一个键时，我们可以创建一个对象列表共享这个键。

下面的代码向我们展示了如何将庄家的牌面值作为结果集的索引。

outcomes = defaultdict(list)
self.play_hand( table, hand )
outcome= self.get_payout()
outcomes[hand.dealer_card.rank].append(outcome)

outcomes[rank]中的值是一个模拟的收益列表，我们可以求这些值的平均数或总数来统计收益情况。可以通过计算赢和输的次数或者进行其他的定量分析来制定能够让损失最小化收益最大化的策略。

一些情况下，我们可能会想用defaultdict集合提供一个常量。比起container. get(key,"N/A")，更倾向于使用container[key]。当key不存在时，总是返回一个字符串常量。实现这个行为的难点在于defaultdict类会使用一个无参的函数创建默认值，没有办法为其指定一个常量。

我们可以创建一个无参的lambda对象，这种方式非常符合我们的需求，下面是一个例子。

>>> from collections import defaultdict
>>> messages = defaultdict( lambda: "N/A" )
>>> messages['error1']= 'Full Error Text'
>>> messages['other']
'N/A'

当键不存在时，总是返回一个默认值，并且将键（本例中是'other'）添加到字典中。我们可以通过查找所有值是"N/A"的键来确定添加了多少新值。

>>> [k for k in messages if messages[k] == "N/A"]
['other']

正如你从上面的输出中看到的，我们找到了默认值"N/A"的键。

6.3.6　counter集合

defaultdict类的一个最常用场景是为事件计数，可使用下面这样的代码来完成。

frequency = defaultdict(int)
for k in some_iterator():
　　frequency[k] += 1

以上代码计算了k在some_iterator()生成的序列中出现的次数。

由于这种需求很常见，因此有一个defaultdict的等价对象提供了和上面的代码一样的功能——它就是Counter。但是，相对来说，Counter集合比一个简单的defaultdict类更加复杂。它可用于确定最常用值的场景，也就是统计学家说的众数（mode）。

我们需要调整defaultdict对象中的值来找到众数。这并不难，但是由于这是一种样板代码，因此会让人感到厌烦，代码看起来像下面这样。

by_value = defaultdict(list)
for k in frequency:
　　by_value[ frequency[k] ].append(k)

我们创建了另一个字典。这个by_value字典的键是上面frequency字典中的值。每一个键都与原本some_iterator()返回的值关联。

接着，我们可以用下面的代码定位并按出现频率排序并显示出的最常用值。

for freq in sorted(by_value, reverse=True):
　　print( by_value[freq], freq )

这会创建一个频率分布图，它向我们展示了一个给定频率的所有值和所有共享这些键值的频率计数。

上面的所有属性都是Counter集合的一部分，下面是一个基于某些数据创建频率分布图的例子。

from collections import Counter
frequency = Counter(some_iterator())
for k,freq in frequency.most_common():
　　print( k, freq )

这个例子告诉我们，通过向Counter提供可迭代的对象，我们就可以轻易地获得统计数据。它会收集可迭代对象中每个值的频率数据。本例中，我们提供了一个返回可迭代对象的函数some_iterator()。我们也可以选择提供一个序列或者其他集合。

然后，我们可以降序地显示结果。但是，等等！这并不是Counter的全部。

Counter集合并非仅仅是defaultdict集合的变种。这个类名有一些误导的成分。一个Counter对象实际是一个“多重集合”，有时候也被称为“包”。

它是一个类似set的集合，但是在包中是允许重复的。它不是一个用下标或者位置来标志元素的序列，顺序在包中并不重要。它也不是一个键值映射。它像是一个元素就代表它们本身并且顺序无关的集合（set）。但是，它又不是一个集合，因为，正如这个例子中所看到的，元素可以重复。

由于元素可以重复，Counter对象用一个整数来统计多次出现的元素，因此它可以被用来创建频率表。但是，它的用处不止如此。由于包类似于一个集合，因此我们可以通过比较两个包中的元素来创建并集或者交集。

让我们创建两个包。

>>> bag1= Counter("aardwolves")
>>> bag2= Counter("zymologies")
>>> bag1
Counter({'a': 2, 'o': 1, 'l': 1, 'w': 1, 'v': 1, 'e': 1, 'd': 1,
's': 1, 'r': 1})
>>> bag2
Counter({'o': 2, 'm': 1, 'l': 1, 'z': 1, 'y': 1, 'g': 1, 'i': 1,
'e': 1, 's': 1})

我们通过扫描一个字母序列来创建包。对于每一个出现超过一次的字母，会有对应一个大于一的计数。

我们可以很容易地得到两个包的并集。

>>> bag1+bag2
Counter({'o': 3, 's': 2, 'l': 2, 'e': 2, 'a': 2, 'z': 1, 'y': 1,
'w': 1, 'v': 1, 'r': 1, 'm': 1, 'i': 1, 'g': 1, 'd': 1})

这个结果显示了两个字符串中所有的字符。有3个o。毫不意外地，其他的字母不是很流行。

我们也能同样容易地得到两个包的不同元素。

>>> bag1-bag2
Counter({'a': 2, 'w': 1, 'v': 1, 'd': 1, 'r': 1})
>>> bag2-bag1
Counter({'o': 1, 'm': 1, 'z': 1, 'y': 1, 'g': 1, 'i': 1})

第1个表达式显示的是bag1中有而bag2中没有的元素。

第2个表达式显示的是bag2中有而bag1中没有的元素。注意，o在bag2中出现了两次并且在bag1中也出现了一次。结果只是从bag1中移除了其中的一个o。