我们可以扩展一些标准库抽象基类（ABCs）来创建新类型的集合。ABCs 还为我们提供了扩展内置容器的设计指南。这使我们能够更精确地调整特性或定义适合我们的问题域的新数据结构。
我们将了解容器类的 ABC 的基础知识。有相当多的抽象用于组装内置 Python 类型，例如list、tuple、dict、set和frozenset。我们将回顾作为容器所涉及的各种特殊方法，并提供容器的各种特性。我们将这些方法分为核心容器方法，与更专业的sequence、map和set方法分开。我们将讨论扩展内置容器以添加功能。我们还将研究包装内置容器以及通过包装将方法委派给底层容器。
最后，我们将研究构建全新的容器。这是一个具有挑战性的领域，因为 Python 标准库中已经存在大量有趣且有用的收集算法。为了避免深入的计算机科学研究，我们将建立一个相当蹩脚的收藏。在开始实际应用之前，仔细研究 Cormen、Leiserson、Rivest 和 Stein 的算法介绍是至关重要的。最后，我们将总结一些用于扩展或创建新集合的设计考虑。
在本章中，我们将介绍以下主题：
- 藏品的基本知识
- 特殊方法示例
- 使用标准库扩展
- 创建新类型的集合
- 缩小集合的类型
- 定义一种新的序列
- 创建一种新的映射
- 创建一种新的集合
本章的代码文件可在上找到 https://git.io/fj2U2 。
collections.abc模块提供了丰富的 ABC，可将集合分解为多个离散的特征集。一个类的一组相关特性称为协议：其思想是获取、设置和删除项目等都是类似列表的行为的协议。类似地，__iter__()方法是定义 iterable 集合的协议的一部分。列表通常实现两种协议，但某些数据结构可能支持较少的协议。mypy算法经常利用对给定协议的支持来确定对象是否被正确使用。
我们可以成功地使用list类，而无需深入思考各种特性以及它们与set类或dict类的关系。然而，一旦我们开始研究 ABC，我们就会发现这些类有一些微妙之处。通过分解每个集合的各个方面，我们可以看到重叠的区域，它们表现为优雅的多态性，甚至在不同的数据结构之间。
基类的底部是集合核心协议的一些定义。
这些是通常定义单个特殊方法的基类：
Container基类需要具体类来实现__contains__()方法。此特殊方法实现了in操作符。Iterable基类需要__iter__()。for语句、生成器表达式以及iter()函数都使用了这种特殊方法。Sized基类需要__len__()。此方法由len()函数使用。实施__bool__()也是谨慎的，但本 ABC 不要求这样做。Hashable基类需要__hash__()。这是由hash()功能使用的。如果实现了这一点，则意味着对象是不可变的。
这些抽象类定义中的每一个都用于构建我们可以在应用程序中使用的结构的更高级别的复合定义。这些复合结构包括较低级别的基类Sized、Iterable和Container。下面是一些我们可能在应用程序中使用的复合基类：
Sequence和MutableSequence类建立在基础之上，包括index()、count()、reverse()、extend()和remove()等方法。Mapping和MutableMapping类包括keys()、items()、values()和get()等方法。Set和MutableSet类包括比较运算符和算术运算符，用于执行集合运算。
如果我们更深入地研究内置集合，我们可以看到 ABC 定义如何组织我们需要编写或修改的特殊方法。
collections模块还包含三个具体实现：UserDict、UserList和UserString。UserDict是内置词典的一个版本，详细内容已公开。类似地，UserList和UserString提供了可以通过子类扩展的实现。这些有助于了解集合是如何构建的。在较旧版本的 Python 中，它们被用作超类，并被扩展，因为内置类型不容易扩展。在 Python3 中，内置类型的扩展非常简单：除了作为示例代码之外，很少使用这些类型。
让我们来看看下一节中一些特殊方法的例子。
当我们观察 21 点Hand物体时，我们有一个有趣的关于包容的特例。我们经常想知道手中是否有王牌。如果我们将Hand定义为list的扩展，那么我们就不能要求通用 ace。我们只能要求特定的卡。我们必须编写类似以下示例的内容：
any(c.rank == 'A' for c in hand.cards) 这将连续检查每张卡片。对于很少进行检查的小型集合，这种设计几乎没有什么影响。另一方面，如果我们模拟数百万只手，那么这种搜索将被频繁重复，以至于成本会令人不安。
对于其他问题域，集合可能包含数百万项，我们当然不能连续扫描数百万项。更好的对象集合方案可能会有所帮助。理想情况下，我们希望这样：
'A' in hand.cards 这意味着我们正在修改扩展了list的Hand对象的contains的含义。我们不是在寻找一个Card实例；我们只是在寻找一个Card对象的rank属性。我们可以覆盖__contains__()方法来执行此操作：
def __contains__(self, rank: int) -> bool:
return any(c.rank==rank for rank in hand.cards) 这允许我们对手牌中给定的等级使用更简单的in测试。个别卡片的系列检查仍然存在，但它被封装在Hand类中，我们可以引入基于字典的专用索引来优化它。类似的设计考虑可应用于__iter__()和__len__()特殊方法。不过，要小心。更改len()的语义或集合如何与for语句交互可能是灾难性的。
下一节将解释如何使用标准库扩展。
我们将研究一些内置类的扩展，这些类已经是标准库的一部分。这些是扩展或修改内置集合的集合。其中大部分都以某种形式出现在达斯蒂·菲利普斯（Dusty Phillips）的《Python 3 面向对象编程-第三版》（第三版）等书中。
我们将查看此库中的以下四个集合：
deque（注意非典型类名）是一个双端队列，一个类似列表的集合，可以在任意一端执行快速追加和弹出。此类功能的子集将创建单端堆栈或队列。ChainMap是多个映射的视图。不必将映射合并在一起，我们可以将它们分开，并在它们之间建立链，以确定哪个映射包含请求的密钥defaultdict（注意非典型拼写）是一个dict子类，它使用工厂函数为缺少的键提供值。Counter是dict子类，可用于计算对象以创建频率表。然而，它实际上是一种更复杂的数据结构，称为多集或包。
此库中有两个集合已被更高级的版本所取代：
namedtuple()函数创建了一个具有命名属性的tuple子类。这已被typing模块中的NamedTuple定义所取代。我们将强调新的typing.NamedTuple类，因为它允许类型提示。遗留功能不再有用。OrderedDict集合是一种映射，在该映射中维护原始密钥输入顺序。这个维护密钥顺序的功能现在是内置dict类的一流部分，因此不再需要这个特殊集合。
我们将看到前面集合类的示例。从研究图书馆藏书中可以学到两个重要的教训：
- 标准库中已有哪些功能；这将使我们免于再创造
- 如何扩展 ABC，为语言添加有趣和有用的结构
此外，阅读库的源代码也很有帮助。源代码将向我们展示许多 Python 面向对象编程技术。除了这些基础，还有更多的模块。详情如下:
heapq模块是一组函数，将堆队列结构强加给现有list对象。堆队列不变量是堆中维护的那些项的集合，以允许按升序快速检索。如果我们在list结构上使用heapq方法，我们将永远不必显式地对列表排序。这可以显著提高性能。array模块是一种序列，用于优化某些类型值的存储。这在潜在的大量简单值集合上提供了类似列表的功能。
我们不会提供这些高级模块的详细示例。此外，当然，还有更深层的计算机科学支持这些不同的数据结构定义。
让我们看看下面几节中的不同类。
NamedTuple类需要许多类级属性。这些属性通常具有类型提示，并提供一种为元组的属性命名的方法
使用 NamedTuple 子类可以将类定义压缩为简单不可变对象的非常短的定义。它使我们不必为我们想要命名一组固定属性的常见情况编写更长更复杂的类定义。
对于扑克牌之类的东西，我们可能希望在类定义中插入以下代码：
from typing import NamedTuple
class BlackjackCard_T(NamedTuple):
rank: str
suit: Suit
hard: int
soft: int我们定义了一个新类并提供了四个命名属性：rank、suit、hard和soft。因为这些对象中的每一个都是不可变的，所以我们不需要担心行为不好的应用程序试图更改BlackjackCard实例的排名。
我们可以使用 factory 函数创建此类的实例，如下代码所示：
def card_t(rank: int , suit: Suit) -> BlackjackCard_T:
if rank == 1 :
return BlackjackCard_T( "A" , suit, 1 , 11 )
elif 2 <= rank < 11 :
return BlackjackCard_T( str (rank), suit, rank, rank)
elif rank == 11 :
return BlackjackCard_T( "J" , suit, 10 , 10 )
elif rank == 12 :
return BlackjackCard_T( "Q" , suit, 10 , 10 )
elif rank == 13 :
return BlackjackCard_T( "K" , suit, 10 , 10 )
else :
raise ValueError ( f"Invalid Rank {rank}" )card_t()函数将建立一个BlackjackCard实例，并为各种卡等级正确设置硬总计和软总计。这里的目的是使用card_t(7, Suit.Hearts)创建BlackjackCard类的实例。各点将通过card_t()功能自动设置。
NamedTuple的子类将包含一个名为_fields的类级属性，该属性命名字段。此外，_field_types属性提供了为属性提供的类型提示的详细信息。这些允许对NamedTuple子类进行复杂的内省。
当然，我们可以在NamedTuple类定义中包含方法。包含方法的示例如下所示：
class BlackjackCard_T(NamedTuple):
rank: str
suit: Suit
hard: int
soft: int
def is_ace( self ) -> bool:
return False
class AceCard(BlackjackCard):
def is_ace(self) -> bool:
return True子类不能添加任何新属性。但是，子类可以有意义地重写方法定义。这种技术可以有效地创建NamedTuple类的多态子类。
list对象旨在为容器内的任何元件提供统一的性能。某些操作会受到性能惩罚。最值得注意的是，任何从列表前面扩展的操作（如list.insert(0, item)）或从列表前面删除的操作（如list.pop(0)）都会产生一些开销，因为列表的大小发生了更改，每个元素的位置随后都必须更改。
deque——一种双端队列——旨在为列表的第一个和最后一个元素提供统一的性能。这个想法是附加和弹出将比内置的list对象更快。
Class names are usually in title case. However, the deque class doesn't follow the common pattern.
我们对一副卡片的设计避免了list对象的潜在性能陷阱，因为它总是从末尾弹出，而不是从开头弹出。使用默认的pop()或显式的pop(-1)，通过使用低成本位置删除 at 项，利用列表的不对称性。
deque.pop()方法非常快速，可以从列表的两端开始工作。虽然这很方便，但我们可以检查洗牌的性能是否会受到影响。洗牌将随机访问容器，而deque并不是为此而设计的。
为了确认潜在成本，我们可以使用timeit来比较list和deque洗牌性能，如下所示：
>>> timeit.timeit('random.shuffle(x)',"""
... import random
... x=list(range(6*52))""")
597.951664149994
>>>
>>> timeit.timeit('random.shuffle(d)',"""
... from collections import deque... import random
... d=deque(range(6*52))""")
609.9636979339994 我们使用random.shuffle()调用timeit。第一个示例处理一个list对象；第二个示例适用于deque对象。
这些结果表明，洗牌一个deque对象只比洗牌一个list对象慢一点点——大约慢 2%。这种区别是不值得分割的。我们可以自信地尝试用一个deque对象代替list。
这一变化相当于：
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%）。我们从数据结构的微小变化中节省了大量资金。
通常，为应用程序选择最佳的数据结构非常重要。尝试几种变体可以告诉我们什么更有效。
将映射链接在一起的用例非常符合 Python 的局部和全局定义的概念。当我们在 Python 中使用变量时，首先搜索本地名称空间，然后按该顺序搜索全局名称空间。除了在两个名称空间中搜索变量外，还可以在本地名称空间中设置变量，而不会干扰全局名称空间。这种默认行为（没有global或nonlocal语句）也是ChainMap的工作方式。
当我们的应用程序开始运行时，我们通常拥有来自命令行参数、配置文件、操作系统环境变量的属性，可能还有随软件安装的默认设置文件。它们具有明确的优先顺序，其中命令行上提供的值最重要，而安装范围内的默认设置最不重要。因为ChainMap对象将按顺序搜索各种映射，所以它允许我们将多个参数源合并到一个类似字典的结构中，这样我们就可以轻松定位设置
我们可能有一个应用程序启动，它结合了以下几种配置选项：
import argparse
import json
import os
import sys
from collections import ChainMap
from typing import Dict, Any
def get_options(argv: List[ str ] = sys.argv[ 1 :]) -> ChainMap:
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(argv)
if cmdline.configuration:
config_file = json.load(cmdline.configuration)
cmdline.configuration.close()
else :
config_file = {}
default_path = (
Path.cwd() / "Chapter_7" / "ch07_defaults.json")
with default_path.open() as default_file:
defaults = json.load(default_file)
combined = ChainMap(
vars (cmdline), config_file, os.environ, defaults)
return combined前面的代码向我们展示了几个来源的配置，例如：
- 命令行参数。在本例中，只有一个参数，称为
playerclass，但实际应用程序通常会有很多、更多的参数。 - 其中一个参数
configuration是带有附加参数的配置文件的名称。这应该是 JSON 格式，并且文件的内容被读取。 - 此外，还有一个
defaults.json文件，其中还有另一个地方可以查找配置值。
根据前面的来源，我们可以构建一个ChainMap对象。此对象允许按指定顺序在每个列出的位置中查找参数。ChainMap实例用例将搜索从最高优先级到最低优先级的每个映射，查找给定的键并返回值。这为我们提供了一个整洁、易于使用的运行时选项和参数源。
我们将在第 14 章、配置文件和持久化以及第 18 章、处理命令行中再次了解这一点。
OrderedDict集合是一个 Python 字典，它增加了一个特性。将保留插入键的顺序。
OrderedDict的一个常见用法是在处理 HTML 或 XML 文件时，其中必须保留对象的顺序，但对象可能通过ID和IDREF属性进行交叉引用。我们可以使用 ID 作为字典键来优化对象之间的连接。我们可以使用OrderedDict结构保留源文档的排序。
在 3.7 版中，内置的dict类同样保证保留插入字典键的顺序。下面是一个例子：
>>> some_dict = {'zzz': 1, 'aaa': 2}
>>> some_dict['mmm'] = 3
>>> some_dict {'zzz': 1, 'aaa': 2, 'mmm': 3}在 Python 的早期版本中，不能保证字典中键的顺序与插入键的顺序相匹配。键的顺序过去是任意的，很难预测。OrderedDict类在这些较旧的 Python 版本中添加了插入顺序保证。由于现在保证键的顺序与插入键的顺序相同，OrderedDict类是冗余的
普通dict类型在找不到键时引发异常。一个defaultdict集合类的做法有所不同。它对给定函数求值，并将该函数的值作为默认值插入字典，而不是引发异常。
Class names are usually in upper TitleCase . However, the defaultdict class doesn't follow this pattern.
defaultdict类的一个常见用例是为对象创建索引。当多个对象具有公共密钥时，我们可以创建共享该密钥的对象列表。
下面是一个函数，它根据两个值的摘要来累积不同值的列表：
from typing import Dict, List, Tuple, DefaultDict
def dice_examples(n: int = 12 , seed: Any= None ) -> DefaultDict[int, List]:
if seed:
random.seed(seed)
Roll = Tuple[ int , int ]
outcomes: DefaultDict[ int , List[Roll]] = defaultdict( list )
for _ in range (n):
d1, d2 = random.randint( 1 , 6 ), random.randint( 1 , 6 )
outcomes[d1+d2].append((d1, d2))
return outcomesApple T0At 的类型提示表明，骰子的骰子是由整数组成的二元组。outcomes对象有一个提示，它将是一个具有整数键的字典，关联的值将是Roll实例的列表。
词典是使用outcomes[d1+d2].append((d1, d2))构建的。给定两个随机数，d1和d2，总和就是键值。如果此键值在outcomes映射中不存在，list()函数用于构建空列表的默认值。如果密钥已经存在，则只需获取该值，并使用append()方法累积实际的一对数字。
作为另一个例子，我们可以使用 adefaultdict集合类来提供一个常量值。我们可以用这个来代替container.get(key,"N/A")表达式。
我们可以创建一个零参数lambda对象。这个很好用。下面是一个例子：
>>> from collections import defaultdict
>>> messages = defaultdict(lambda: "N/A")
>>> messages['error1']= 'Full Error Text'
>>> messages['other']
'N/A'
>>> messages['error1'] 'Full Error Text'在第一次使用messages['error1']时，为'error1'键分配了一个值。此新值将替换默认值。第二次使用messages['other']将向字典添加默认值
我们可以通过查找值为"N/A"的所有键来确定创建了多少个新键：
>>> [k for k in messages if messages[k] == "N/A"]
['other'] 正如您在前面的输出中所看到的，我们找到了分配了默认值"N/A"的键。这通常是对正在积累的数据的有益总结。它向我们显示与默认值关联的所有键。
defaultdict类最常见的用例之一是累积关键实例的计数。计数关键点的简单方法如下所示：
frequency = defaultdict(int)
for k in some_iterator():
frequency[k] += 1 本例统计每个键值k在some_iterator()的值序列中出现的次数。
这个用例非常常见，defaultdict主题上有一个变体，它执行前面代码中所示的相同操作，称为Counter。然而，一个Counter集合要比一个简单的defaultdict类复杂得多。
下面是一个示例，它从一些数据源创建一个频率直方图，按频率降序显示值：
from collections import Counter
frequency = Counter(some_iterator())
for k, freq in frequency.most_common():
print(k, freq) 这个例子向我们展示了如何通过向Counter提供任何可匹配的项目来轻松收集统计数据。它将收集该 iterable 项中值的频率数据。在本例中，我们提供了一个名为some_iterator()的 iterable 函数。我们可能提供了一个序列或其他集合。
然后我们可以按受欢迎程度的降序显示结果。但是等等！还不止这些。
Counter集合不仅仅是defaultdict集合的简单变体。这个名字有误导性。一个Counter对象实际上是一个 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa。
它是一个集合，设置为，但允许在包中重复值。它不是由索引或位置标识的项目序列；秩序不重要。它不是具有键和值的映射。它就像一个集合，其中的项目代表它们自己，顺序并不重要。但是，它不同于集合，因为在这种情况下，元素可以重复。
由于元素可以重复，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})这显示了两个字符串之间的整个字母组。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}) 第一个表达式显示了bag1中不在bag2中的 us 字符。
第二个表达式显示的是bag2中不在bag1中的 us 字符。注意，字母o在bag2中出现两次，在bag1中出现一次。差异仅删除了bag1中的一个o字符。
在下一节中，我们将看到如何创建新类型的集合。
我们将看一些对 Python 内置容器类的扩展。我们将不展示扩展每个容器的示例。
我们将选取一个扩展特定容器的示例，并了解该过程的工作原理：
- 定义需求。这可能包括对维基百科的研究，通常从这里开始：http://en.wikipedia.org/wiki/Data_structure 。数据结构的设计通常涉及围绕缺失项和重复项的复杂边缘情况。
- 如有必要，查看
collections.abc模块，了解创建新功能必须实现哪些方法。 - 创建一些测试用例。这还需要仔细研究算法，以确保正确覆盖边缘情况。
- 根据前面的研究步骤编写代码。
在尝试发明一种新的数据结构之前，我们需要强调研究基础知识的重要性。除了在网上搜索概述和摘要外，还需要详细信息。请参阅以下任一项：
- Cormen、Leiserson、Rivest 和 Stein 的算法简介
- Aho、Ullman 和 Hopcroft 的数据结构和算法
- 史蒂文·斯基纳的算法设计手册
如前所述，ABC 定义了三大类集合：序列、映射和集合。我们有三种设计策略，可用于创建我们自己的新系列：
- 扩展：这是一个已有的序列。
- 包裹：这是一个已有的序列。
- 发明：这是一个从头开始创建的新序列。
原则上，我们可以给出多达九个例子——每种基本风格的集合和每种基本的设计策略。我们不会把这个话题打得这么惨的。我们将深入挖掘以创建新类型的序列，学习如何扩展和包装 现有序列。
由于有如此多的扩展映射（如ChainMap、OrderedDict、defaultdict和Counter），因此我们将仅简单介绍创建新类型的映射。我们还将深入挖掘以创建一种新的有序多集或包。
让我们在下一节缩小集合的类型。
Python3 允许我们提供大量类型提示来描述集合的内容。这有两个好处：
- 它帮助我们可视化数据结构。
- 支持运行mypy确认代码正确使用数据结构。
非集合类型（int、str、float、complex等）都使用类型名称作为其类型提示。内置集合在typing模块中都有并行类型定义。通常会看到from typing import List, Tuple, Dict, Set将这些类型名称导入到模块中
每个类型提示都接受参数以进一步缩小定义范围：
List[T]提示声明对象将是list并且所有项目都将是T类型。例如，可以将[1, 1, 2, 3, 5, 8]描述为List[int]。Set[T]提示与List[T]提示类似。它声称集合中的所有项目都将属于T类型。例如，{'a', 'r', 'd'}可以描述为Set[str]。Dict[K, V]提示声明对象将是dict，所有键都将有一个类型K，所有值都将有一个类型V。例如，{'A': 4, 'B' 12}可以描述为Dict[str, int]。
Tuple暗示往往更为复杂。元组有两种常见情况：
- 类似于
Tuple[str, int, int, int]的提示描述了一个包含字符串和三个整数值的四元组，例如(' crimson', 2 20, 20, 60)。大小是显式指定的。 - 类似于
Tuple[int, ...]的提示描述了大小不确定的元组。所有项目均为int类型。未指定大小。...符号是 Python 语言中的一个标记，是该类型提示语法的一级部分。
为了描述集合中可能存在None值的对象，使用Optional类型。我们可能会有一个类型提示，例如List[Optional[int]]来描述一个混合了int和None对象的列表，例如[1, 2, None, 42]。
由于数字的类型强制规则，我们通常可以使用float类型提示总结数值算法，例如：
def mean(data: List[float]) -> float: ...此函数还将处理整数值列表。mypy程序识别类型强制规则，并将mean([8, 9, 10])识别为该函数的有效使用。
在下一节中，我们将定义一种新的序列。
我们在进行统计分析时的一个常见要求是计算数据集合的基本平均值、模式和标准差。我们的 21 点模拟将产生必须进行统计分析的结果，看看我们是否真的发明了更好的策略。
当我们模拟一个游戏的游戏策略时，我们将开发一些结果数据，这些数据将是一系列数字，显示使用给定策略多次玩游戏的最终结果
我们可以将结果累积到内置的list类中。我们可以通过
计算平均值，其中
是
中的元素数：
def mean(outcomes: List[ float ]) -> float :
return sum (outcomes) / len (outcomes)标准偏差可通过
计算：
def stdev(outcomes: List[ float ]) -> float :
n = float ( len (outcomes))
return math.sqrt(
n * sum (x** 2 for x in outcomes) - sum (outcomes)** 2
) / n这两个都是相对简单的计算函数。然而，随着事情变得越来越复杂，像这样的松散函数就变得不那么有用了。面向对象编程的好处之一是将功能与数据绑定在一起。
我们的第一个示例不涉及重写list的任何特殊方法。我们将简单地子类化list以添加将计算统计数据的方法。这是一种非常常见的扩展。
我们将在第二个示例中重新讨论这个问题，以便修改和扩展特殊方法。这需要对 ABC 特殊方法进行一些研究，看看我们需要添加或修改什么，以便我们的新列表子类能够正确继承内置list类的所有特性。
因为我们正在研究序列，所以我们还必须与 Pythonslice符号进行斗争。我们将在与__getitem__、__setitem__、__delitem__和部分一起研究切片是什么以及它在内部如何工作。
第二个重要的设计策略是包装。我们将围绕列表创建一个包装器，并查看如何将方法委托给包装的列表。包装在对象持久化方面有一些优势，这是第 10 章、序列化和保存的主题——JSON、YAML、Pickle、CSV 和 XML。
我们还可以看看需要做什么来从头开始创造一种新的序列。
将均值和标准差特征直接合并到list的子类中是很有意义的。我们可以这样扩展list：
class StatsList( list ):
def __init__ ( self , iterable: Optional[Iterable[ float ]]) -> None :
super (). __init__ (cast(Iterable[Any], iterable))
@property
def mean( self ) -> float :
return sum ( self ) / len ( self )
@property
def stdev( self ) -> float :
n = len ( self )
return math.sqrt(
n * sum (x ** 2 for x in self ) - sum ( self ) ** 2
) / n通过对内置list类的简单扩展，我们可以积累数据并报告数据项收集的统计数据。
请注意缩小列表类的类型所涉及的相对复杂性。内置列表结构的类型List实际上是List[Any]。为了使算术运算能够工作，内容必须是List[float]。通过说明__init__()方法只接受Iterable[float]值，mypy被迫确认StatsList的参数将满足此标准。假设我们有一个原始数据源：
def data_gen() -> int:
return random.randint( 1 , 6 ) + random.randint( 1 , 6 )这个小小的data_gen()函数是各种可能函数的替代品。这可能是一个复杂的模拟。它可能是实际测量的来源。由类型提示定义的此函数的基本功能是创建一个整数值。
我们可以想象一个整体模拟脚本可以使用StatsList类，如下所示：
random.seed( 42 )
data = [data_gen() for _ in range ( 100 )]
stats = StatsList(data)
print ( f"mean = { stats.mean : f } " )
print ( f"stdev= { stats.stdev : .3f } " )此代码段使用列表理解创建了一个包含 100 个样本的原始list对象。由于数据对象是根据data_gen()函数构建的，因此很明显数据对象的类型为List[int]，由此创建了一个StatsList对象。生成的stats对象具有mean和stdev属性，它们是基列表类的扩展。
请注意，前面示例中的计算是延迟的；它们只在被要求时才完成。这也意味着，每次请求时都会执行这些操作。这可能是相当大的开销，具体取决于使用这些类的对象的上下文。
将这些统计摘要转换为急切的计算可能是明智的，因为我们知道何时从列表中添加和删除元素。尽管有更多的编程来创建这些函数的渴望版本，但在积累大量数据的情况下，它会对提高性能产生净影响。
急切的统计计算的要点是避免计算和的循环。如果我们在创建列表时急切地计算总和，就可以避免在数据中出现额外的循环。
当我们查看Sequence类的特殊方法时，我们可以看到在序列中添加、删除和修改数据的所有位置。我们可以使用此信息重新计算所涉及的两个和。我们从Python 标准库文档的collections.abc部分开始，第 8.4.1 节，在处 http://docs.python.org/3.4/library/collections.abc.html#collections-抽象基类。
以下是MutableSequence类所需的方法：__getitem__、
__setitem__、__delitem__、__len__、insert、append、reverse、extend、pop、remove和__iadd__。文档中还提到了继承序列方法。然而，由于它们是针对不可变序列的，我们当然可以忽略它们。
以下是更新每种方法的统计结果所必须采取的措施的详细信息：
__getitem__：状态没有变化。__setitem__：这会更改一个项目。我们需要从每笔款项中取出旧项目，并将新项目折叠到每笔款项中。__delitem__：删除一个项目。我们需要从每笔款项中扣除旧款。__len__：状态没有变化。insert：新增一项。我们需要把它折成每一笔。append：这也增加了一个新项目。我们需要把它折成每一笔。reverse：平均值或标准偏差值没有变化。extend：增加了很多新项目。所有项目都必须合并到总数中。pop：删除一个项目。我们需要从每笔款项中扣除旧款。remove：删除一个项目。我们需要从每笔款项中扣除旧款。__iadd__：这是+=增广赋值语句，就地添加。它实际上与extend关键字相同。
我们不会详细介绍每种方法，因为实际上有两种用例的组合：
- 加入一个新值
- 删除一个旧值
更换壳体是拆卸和折叠操作的组合。
以下是渴望的StatsList2课程的要素。我们将看到insert()和pop()方法：
class StatsList2( list ):
"""Eager Stats."""
def __init__ ( self , iterable: Optional[Iterable[ float ]]) -> None :
self .sum0 = 0 # len(self), sometimes called "N"
self .sum1 = 0.0 # sum(self)
self .sum2 = 0.0 # sum(x**2 for x in self)
super (). __init__ (cast(Iterable[Any], iterable))
for x in self :
self ._new(x)
def _new( self , value: float ) -> None :
self .sum0 += 1
self .sum1 += value
self .sum2 += value * value
def _rmv( self , value: float ) -> None :
self .sum0 -= 1
self .sum1 -= value
self .sum2 -= value * value
def insert( self , index: int , value: float ) -> None :
super ().insert(index, value)
self ._new(value)
def pop( self , index: int = 0 ) -> None :
value = super ().pop(index)
self ._rmv(value)
return value我们提供了三个带有注释的内部变量来显示这个类将维护的不变量。我们将这些称为和不变量，因为它们中的每一个都包含一种特殊的和，在每一种状态改变后都保持不变（始终为真）。这种急切计算的本质是_rmv()和_new()方法，它们根据列表的变化更新我们的三个内部总和，从而使关系真正保持不变。
当我们删除一个项目时，即在成功的pop()操作之后，我们必须调整我们的金额。当我们添加一个项目时（最初或通过insert()方法），我们还必须调整我们的总和。我们需要实现的其他方法将使用这两种方法来确保三个和不变量保持不变。对于给定的值列表 L，我们确保L.sum0始终为
、L.sum1始终为
、L.sum2始终为
。我们可以使用总和来计算平均值和标准偏差。
其他方法，如append()、extend()和remove()在许多方面与这些方法类似。我们没有展示它们，因为它们很相似。
我们可以通过播放一些数据来了解此列表的工作原理：
>>> sl2 = StatsList2( [2, 4, 3, 4, 5, 5, 7, 9, 10] )
>>> sl2.sum0, sl2.sum1, sl2.sum2
(9, 49, 325)
>>> sl2[2]= 4
>>> sl2.sum0, sl2.sum1, sl2.sum2
(9, 50, 332)
>>> del sl2[-1]
>>> sl2.sum0, sl2.sum1, sl2.sum2
(8, 40, 232)
>>> sl2.insert( 0, -1 )
>>> sl2.pop()
-1
>>> sl2.sum0, sl2.sum1, sl2.sum2
(8, 40, 232) 我们可以创建一个列表，并初步计算总和。随后的每一次变化都会急切地更新各种总和。我们可以更改、删除、插入和弹出项目；每次更改都会产生一组新的和。
剩下的就是添加我们的平均值和标准偏差计算，我们可以按如下方式进行：
@property
def mean( self ) -> float :
return self .sum1 / self .sum0
@property
def stdev( self ) -> float :
return math.sqrt(
self .sum0* self .sum2 - self .sum1* self .sum1
) / self .sum0它们利用已经计算的总和。没有额外的数据循环来计算这两个统计数据。
StatsList2示例没有向我们展示__setitem__()或__delitem__()的实现，因为它们涉及切片。在我们能够正确地实现这些方法之前，我们需要查看切片的实现。
序列有两种不同类型的索引：
a[i]。这是一个简单的整数索引。a[i:j]或a[i:j:k]：这些是具有start:stop:step值的slice表达式。切片表达式可能非常复杂，不同类型的默认值有七种不同的变体。
此基本语法适用于三种上下文：
- 在表达式中，依赖
__getitem__()获取值 - 在赋值的左侧，依靠
__setitem__()设置一个值 - 在
del语句中，依赖__delitem__()删除一个值
当我们做类似于seq[:-1]的事情时，我们会写一个slice表达式。底层的__getitem__()方法将被赋予一个slice对象，而不是一个简单的整数。
参考手册告诉我们一些关于切片的事情。slice对象将有三个属性：start、stop和step。它还将具有一个名为indices()的方法函数，该函数将正确计算切片的任何省略属性值。
我们可以使用一个扩展了list的普通类来探索slice对象：
class Explore(list):
def __getitem__( self, index ):
print( index, index.indices(len(self)) )
return super().__getitem__( index ) 此类将转储slice对象和indices()函数结果的值。然后，使用超类实现，以使列表正常运行。
在这门课上，我们可以尝试不同的slice表达式，看看我们得到了什么：
>>> x = Explore('abcdefg')
>>> x[:]
slice(None, None, None) (0, 7, 1)
['a', 'b', 'c', 'd', 'e', 'f', 'g']
>>> x[:-1]
slice(None, -1, None) (0, 6, 1)
['a', 'b', 'c', 'd', 'e', 'f']
>>> x[1:]
slice(1, None, None) (1, 7, 1)
['b', 'c', 'd', 'e', 'f', 'g']
>>> x[::2]
slice(None, None, 2) (0, 7, 2)
['a', 'c', 'e', 'g'] 在前面的slice表达式中，我们可以看到slice对象有三个属性，这些属性的值直接来自 Python 语法。当我们为indices()函数提供适当的长度时，它返回一个三元组值，包括 start、stop 和 step 值。
在实现__getitem__()、__setitem__()和__delitem__()方法时，必须使用两种参数值：int和slice。此变体行为需要两种不同的类型提示。使用@overload装饰器提供提示。
当我们重载各种序列方法时，我们必须在方法体中适当地处理切片情况。这需要使用isinstance()函数来识别是否提供了slice对象或简单int作为参数值。
下面是一个处理切片的__setitem__()方法：
@overload
def __setitem__ ( self , index: int , value: float ) -> None : ...
@overload
def __setitem__ ( self , index: slice , value: Iterable[ float ]) -> None : ...
def __setitem__ ( self , index, value) -> None :
if isinstance (index, slice ):
start, stop, step = index.indices( len ( self ))
olds = [ self [i] for i in range (start, stop, step)]
super (). __setitem__ (index, value)
for x in olds:
self ._rmv(x)
for x in value:
self ._new(x)
else :
old = self [index]
super (). __setitem__ (index, value)
self ._rmv(old)前面的方法有两个处理路径：
- 如果索引是一个
slice对象，我们将计算start、stop和step值。然后，我们将找到所有要删除的旧值。然后，我们可以调用超类操作并折叠替换旧值的新值。 - 如果索引是一个简单的
int对象，则旧值是单个项，新值也是单个项。
注意，__setitem__()需要使用@overload描述符编写多个类型提示。另一方面，__delitem__()定义依赖于Union[int, slice]，而不是两个重载定义。
以下是__delitem__()方法，该方法可用于切片或整数：
def __delitem__ ( self , index: Union[ int , slice ]) -> None :
# Index may be a single integer, or a slice
if isinstance (index, slice ):
start, stop, step = index.indices( len ( self ))
olds = [ self [i] for i in range (start, stop, step)]
super (). __delitem__ (index)
for x in olds:
self ._rmv(x)
else :
old = self [index]
super (). __delitem__ (index)
self ._rmv(old)前面的代码也扩展了切片以确定可以删除哪些值。如果索引是一个简单整数，则只删除一个值。
当我们向StatsList2类引入适当的切片处理时，我们可以创建完成基本list类所做的一切的列表，并且（快速）返回列表中当前值的平均值和标准偏差。
Note that these method functions will each create a temporary list object, olds; this involves some overhead that can be removed. As an exercise for the reader, it's helpful to rewrite the _rmv() function to eliminate the use of the olds variable.
我们将看看如何包装 Python 的一个内置容器类。包装现有类意味着某些方法必须委托给底层容器。
由于在任何内置集合中都有大量方法，因此包装集合可能需要相当数量的代码。在创建持久类时，包装比扩展具有优势。这就是第 10 章序列化和保存的主题——JSON、YAML、Pickle、CSV 和 XML。在某些情况下，我们希望公开内部集合，以避免编写大量委托给内部列表的序列方法。
适用于统计数据类的一个常见限制是，它们只需要是插入。我们将禁用许多方法函数。这是类特性中的一种戏剧性变化，建议使用包装类而不是扩展。
例如，我们可以设计一个只支持append和__getitem__的类。它将结束一个list类。以下代码可用于从模拟中积累数据：
class StatsList3:
def __init__ ( self ) -> None :
self ._list: List[ float ] = list ()
self .sum0 = 0 # len(self), sometimes called "N"
self .sum1 = 0\. # sum(self)
self .sum2 = 0\. # sum(x**2 for x in self)
def append( self , value: float ) -> None :
self ._list.append(value)
self .sum0 += 1
self .sum1 += value
self .sum2 += value * value
def __getitem__ ( self , index: int ) -> float :
return self ._list. __getitem__ (index)
@property
def mean( self ) -> float :
return self .sum1 / self .sum0
@property
def stdev( self ) -> float :
return math.sqrt(
self .sum0* self .sum2 - self .sum1* self .sum1
) / self .sum0此类有一个内部_list对象，它是基础列表。我们提供了一个显式类型提示，以显示对象应该是List[float]。列表最初为空。由于我们只将append()定义为更新列表的一种方式，因此我们可以轻松地维护各种总和。我们需要小心地将工作委托给超类，以确保在我们的子类处理参数值之前，列表实际上已经更新。
我们可以直接将__getitem__()委托给内部列表对象，而无需检查参数或结果。
我们可以按如下方式使用此类：
>>> sl3 = StatsList3()
>>> for data in 2, 4, 4, 4, 5, 5, 7, 9:
... sl3.append(data)
...
>>> sl3.mean
5.0
>>> sl3.stdev
2.0 我们创建了一个空列表，并将项目附加到列表中。当我们将总和作为附加项进行维护时，我们可以非常快速地计算平均值和标准偏差。
我们没有提供__iter__()的定义。然而，尽管有此遗漏，此类实例仍将是可移植的。
因为我们已经定义了__getitem__()，所以现在有几件事是可行的。我们不仅可以获取项，而且还可以发现，将有一个默认实现，允许我们遍历值序列。
下面是一个例子：
>>> sl3[0]
2
>>> for x in sl3:
... print(x)
...
2
4
4
4
5
5
7
9 前面的输出告诉我们，集合周围的最小包装器通常足以满足许多用例。
请注意，例如，我们并没有使列表变得相当大。如果我们试图获取大小，它将引发异常，如以下代码段所示：
>>> len(sl3)
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: object of type 'StatsList3' has no len() 我们可能需要添加一个__len__()方法，将实际工作委托给内部_list对象。我们可能还想将__hash__设置为None，这是一个谨慎的做法，因为这是一个可变对象。
我们可能需要定义__contains__()并将此功能委托给内部_list。这将创建一个极简主义容器，提供容器的低级功能集。
当我们的设计涉及包装现有类时，我们需要确保我们的类是可移植的。当我们查看collections.abc.Iterable的文档时，我们发现我们只需要定义__iter__()就可以使对象变得可编辑。__iter__()方法可以返回正确的Iterator对象，也可以是生成器函数。
创建一个Iterator对象，虽然不太复杂，但很少有必要。创建生成器函数要简单得多。对于包装的集合，我们应该始终简单地将__iter__()方法委托给基础集合。
对于我们的StatsList3类，它将如下所示：
def __iter__(self):
return iter(self._list) 此方法函数将迭代委托给基础列表对象的Iterator。
Python 有一个名为dict的内置映射和许多库映射。除了对dict（defaultdict、Counter和ChainMap的collections模块扩展之外，还有几个其他库模块包含类似映射的结构。
shelve模块是另一个映射的重要示例。我们将在第 11 章通过货架存储和检索对象中了解这一点。dbm模块与shelve类似，它还将一个键映射到一个值。
mailbox模块和email.message模块都有类，这些类为用于管理本地电子邮件的邮箱结构提供类似于dict的接口。
就设计策略而言，我们可以扩展或包装一个现有映射以添加更多功能。
我们可以升级Counter，将平均值和标准偏差添加到存储为频率分布的数据中。事实上，我们也可以很容易地从这个类中计算中位数和模式。
下面是对Counter的StatsCounter扩展，添加了一些统计函数：
import math
from collections import Counter
class StatsCounter(Counter):
@property
def mean( self ) -> float :
sum0 = sum (v for k, v in self .items())
sum1 = sum (k * v for k, v in self .items())
return sum1 / sum0
@property
def stdev( self ) -> float :
sum0 = sum (v for k, v in self .items())
sum1 = sum (k * v for k, v in self .items())
sum2 = sum (k * k * v for k, v in self .items())
return math.sqrt(sum0 * sum2 - sum1 * sum1) / sum0我们用两种新方法扩展了Counter类，以计算频率分布的平均值和标准偏差。这些公式与前面展示的在list对象上进行急切计算的示例类似，尽管它们是在Counter对象上进行的惰性计算。
我们使用sum0 = sum(v for k,v in self.items())来计算一个值之和v，忽略k键。我们可以用下划线（_代替k来强调我们忽略了键。我们还可以使用sum(v for v in self.values())来强调我们没有使用钥匙。我们更喜欢sum0和sum1的明显平行结构。
我们可以使用这个类有效地收集统计数据，并对原始数据进行定量分析。我们可能会使用一个Counter对象来收集结果，并进行多次模拟。
下面是与代表实际结果的示例数据列表的交互：
>>> sc = StatsCounter( [2, 4, 4, 4, 5, 5, 7, 9] )
>>> sc.mean
5.0
>>> sc.stdev
2.0
>>> sc.most_common(1)
[(4, 3)]
>>> list(sorted(sc.elements()))
[2, 4, 4, 4, 5, 5, 7, 9] most_common()的结果以两个元组的序列报告，模式值（4）和值出现的次数（3）。我们可能希望得到前三个值，将模式与下两个不太受欢迎的项括在一起。我们通过评估得到了几个流行的值，例如sc.most_common(3)。
elements()方法重建了一个list，它类似于原始数据，并正确地重复了项目。
从排序的元素中，我们可以提取中间值，即最中间的项：
@property
def median( self ) -> Any:
all = list ( sorted ( self .elements()))
return all[ len (all) // 2 ]这种方法不仅懒惰，而且内存浪费；它创建可用值的整个序列只是为了找到最中间的项。
虽然它很简单，但这通常是一种昂贵的 Python 使用方法。
更聪明的方法是通过sum(self.values())//2计算有效长度和中点。一旦知道这一点，就可以按该顺序访问密钥，使用计数计算给定密钥的位置范围。最终，将找到一个包含中点范围的关键点。
代码如下所示：
@property
def median2( self ) -> Optional[ float ]:
mid = sum ( self .values()) // 2
low = 0
for k, v in sorted ( self .items()):
if low <= mid < low + v: return k
low += v
return None我们通过按键和按键出现的次数来定位最中间的按键。请注意，这使用了内部的sorted()功能，这并非没有成本。
通过timeit我们可以了解到奢侈版需要 9.5 秒；更智能的版本需要 5.2 秒。
让我们来看看如何在下一节中创建一种新的集合。
创建一个全新的收藏需要一些前期工作。我们需要有新的算法或新的内部数据结构来提供对内置集合的重大改进。在设计新系列之前，进行彻底的大 O复杂度计算非常重要。在实现之后使用timeit也很重要，以确保新集合确实比可用的内置类有所改进。
例如，我们可能希望创建一个二进制搜索树结构，以保持元素的正确顺序。由于我们希望这是一个可变结构，我们必须执行以下类型的设计活动：
- 设计基本的二叉树结构。
- 确定哪种结构是基础：
MutableSequence、MutableMapping或MutableSet。 - 查看Python 标准库文档第 8.4.1 节
collections.abc部分中的特殊收集方法。
二元搜索树具有包含键值的节点和两个分支：对于小于该节点键值的所有键值，小于分支，对于大于或等于该节点键值的键值，大于**或等于分支。
我们需要检查我们的集合与 Python ABC 之间的匹配情况：
- 二叉树不适合某些序列特征。值得注意的是，我们通常不使用带二叉树的整数索引。我们通常通过搜索树中的元素的键来引用它们。虽然我们可以不费吹灰之力地强制使用整数索引，但它将涉及到
树遍历。 - 树可以用于映射的键；这将以相对较低的成本保持键的有序性。
- 它是
set或Counter类的一个很好的替代品，因为它可以容忍一个密钥的多个副本，使得它很容易像袋子一样。
我们将研究如何创建一个已排序的多集或包。这可以包含一个对象的多个副本。它将依赖于对象之间相对简单的比较测试。
这是一个相当复杂的设计。有很多细节。要创建一个背景，阅读像这样的文章很重要 http://en.wikipedia.org/wiki/Binary_search_tree 。在上一个维基百科页面的末尾有一些外部链接，这些链接将提供进一步的信息。学习 Cormen、Leiserson、Rivest 和 Stein 的算法简介等书中的基本算法是非常必要的；Aho、Ullman 和 Hopcroft 的数据结构和算法；或者史蒂文·斯基纳的算法设计手册。
我们将集合分为两类：TreeNode和Tree。这将使我们能够将设计分为基本数据收集和 Pythonic Façade 设计模式，以匹配其他收集
TreeNode类将包含该项以及more、less和parent引用。这是价值观的核心集合。它处理插入和删除。此外，为了使用__contains__()或discard()而搜索特定项目将委托给TreeNode类。
基本搜索算法的轮廓如下所示。
- 如果目标项等于自身项，则返回
self。 - 如果目标项小于
self.item，则递归使用less.find(target item)。 - 如果目标项大于
self.item，则递归使用more.find(target.item)。
对于维护树结构的更多实际工作，我们将使用与TreeNode类类似的委托。
我们将使用立面设计模式将TreeNode的细节包装成一个 Pythonic 界面。这将定义可见的外部定义Tree本身。立面设计也可以称为包装物；其想法是添加特定接口所需的功能。Tree类提供MutableSetABC 所需的外部接口，并将这些需求与TreeNode类中的实现细节区分开来。
如果有一个根节点是空的并且总是比所有其他键值比较少，那么算法可能会稍微简单一些。这在 Python 中可能是一个挑战，因为我们事先不知道节点可能拥有什么类型的数据；我们无法轻松定义根节点的底部值。相反，我们将使用一个特例值None，并承受检查根节点的if语句的开销。
我们将从包装器或 Façade 类开始，Tree。这是MutableSet类扩展的核心，该类提供了最小的方法函数：
class Tree(collections.abc.MutableSet):
def __init__ ( self , source: Iterable[Comparable] = None ) -> None :
self .root = TreeNode( None )
self .size = 0
if source:
for item in source:
self .root.add(item)
self .size += 1
def add( self , item: Comparable) -> None :
self .root.add(item)
self .size += 1
def discard(self, item: Comparable) -> None:
if self.root.more:
try:
self.root.more.remove(item)
self.size -= 1
except KeyError:
pass
else:
pass
def __contains__ ( self , item: Any) -> bool :
if self .root.more:
self .root.more.find(cast(Comparable, item))
return True
else :
return False
def __iter__ ( self ) -> Iterator[Comparable]:
if self .root.more:
for item in iter ( self .root.more):
yield item
# Otherwise, the tree is empty.
def __len__ ( self ) -> int :
return self .size初始化设计类似于Counter对象的初始化设计；此类将接受 iterable 并将元素加载到结构中。数据源提供类型提示Iterable[Comparable]。此提示对该集合可以处理的项的类型施加了限制。如果集合用于不支持适当可比协议方法的项目，则mypy将报告错误。
以下是Comparable类型提示的定义：
class Comparable( metaclass =ABCMeta):
@abstractmethod
def __lt__ ( self , other: Any) -> bool : ...
@abstractmethod
def __ge__ ( self , other: Any) -> bool : ...Comparable类定义是一个抽象，需要两种方法：__lt__()和__ge__()。这是一类对象与<、<=、>和>=操作员正常工作的最低要求。这定义了可排序或排序的对象之间的可比较协议。
add()和discard()方法都会更新树，同时也会跟踪总体大小。通过递归遍历树来保存计数节点。这些方法还将其工作委托给树根的TreeNode对象。
__contains__()特殊方法执行递归查找。mypy要求进行初始检查，以确保树在根节点中包含值。如果没有if语句，类型提示表明more属性可以是None
__iter__()特殊方法是发电机功能。它还将实际工作委托给TreeNode类中的递归迭代器。
我们定义了discard()；当试图丢弃丢失的键时，可变集要求此项保持静默。抽象超类提供了remove()的默认实现，如果找不到键，则会引发异常。两种方法函数都必须存在；我们基于remove()定义discard()，通过沉默异常。在某些情况下，基于discard()定义remove()可能更容易，如果发现问题，则会引发异常。
因为这个类扩展了MutableSet抽象，所以自动提供了许多特性。这使我们不必通过复制和粘贴编程来创建大量样板特性。在某些情况下，我们的数据结构可能有比默认值更高效的实现，并且我们可能希望覆盖从抽象超类继承的其他方法。
整个Tree类依赖TreeNode类来处理包中各个项目的添加、删除和迭代的实现细节。这个类相当大，所以我们将分四个部分来介绍它。
第一部分显示了初始化、表示的基本元素，以及如何使属性可见：
class TreeNode:
def __init__ (
self ,
item: Optional[Comparable],
less: Optional[ "TreeNode" ] = None ,
more: Optional[ "TreeNode" ] = None ,
parent: Optional[ "TreeNode" ] = None ,
) -> None :
self .item = item
self .less = less
self .more = more
if parent:
self .parent = parent
@property
def parent( self ) -> Optional[ "TreeNode" ]:
return self .parent_ref()
@parent.setter
def parent( self , value: "TreeNode" ):
self .parent_ref = weakref.ref(value)
def __repr__ ( self ) -> str :
return f"TreeNode( { self .item !r} , { self .less !r} , { self .more !r} )" 每个单独的节点必须有一个对项目的引用。具有比给定项小或比给定项多的项的附加节点是可选的。类似地，父节点也是可选的。
parent方法的属性定义用于确保父属性实际上是weakref属性，但它看起来像一个强引用。有关弱引用的更多信息，请参见第 3 章无缝集成-基本特殊方法。我们在TreeNode父对象和它的子对象之间有相互引用；这种圆形可能使移除TreeNode物体变得困难。使用weakref会打破循环，允许引用计数在节点不再被引用时快速删除节点。
注意，TreeNode类型提示是从类定义内部对类的引用。这种循环性可能是一个语法问题，因为类尚未完全定义。为了生成有效的自引用类型提示，mypy允许使用字符串。当运行mypy时，字符串解析为正确的类型对象。
以下是查找和迭代节点的方法：
def find( self , item: Comparable) -> "TreeNode" :
if self .item is None : # Root
if self .more:
return self .more.find(item)
elif self .item == item:
return self
elif self .item > item and self .less:
return self .less.find(item)
elif self .item < item and self .more:
return self .more.find(item)
raise KeyError
def __iter__ ( self ) -> Iterator[Comparable]:
if self .less:
yield from self .less
if self .item:
yield self .item
if self .more:
yield from self .more我们看到了find()方法，它从一棵树到相应的子树执行递归搜索，以查找目标项。共有 6 起案件：
- 当这是树的根节点时，我们将跳过它。
- 当此节点具有目标项时，我们将返回它。
- 当目标项小于该节点的项并且在小于侧有一个分支时，我们将下降到该子树中进行搜索。
- 当目标项多于此节点的项并且在more侧有一个分支时，我们将下降到该子树中进行搜索。
- 剩下两种情况：目标项小于当前节点，但没有小于分支；或者目标项大于当前节点，但没有大于分支。这两种情况都意味着在树中找不到该项，导致
KeyError异常。
__iter__()方法对该节点及其子树进行所谓的有序遍历。通常，这是一个生成函数，它从每个子树集合上的迭代器生成值。虽然我们可以创建一个单独的迭代器类，它与我们的Tree类相关联，但是当这个生成器函数完成我们所需要的一切时，没有什么好处。
__iter__()的结果有一个类型提示Iterator[Comparable]。这反映了对树中包含的项施加的最小约束。
下面是该类的下一部分，用于向树中添加新节点：
def add( self , item: Comparable):
if self .item is None : # Root Special Case
if self .more:
self .more.add(item)
else :
self .more = TreeNode(item, parent = self )
elif self .item >= item:
if self .less:
self .less.add(item)
else :
self .less = TreeNode(item, parent = self )
elif self .item < item:
if self .more:
self .more.add(item)
else :
self .more = TreeNode(item, parent = self )这是对添加新节点的正确位置的递归搜索。结构与find()方法平行。
最后，我们有（更复杂的）处理从树中删除节点。这需要谨慎地重新链接丢失节点周围的树：
def remove( self , item: Comparable):
# Recursive search for node
if self .item is None or item > self .item:
if self .more:
self .more.remove(item)
else :
raise KeyError
elif item < self .item:
if self .less:
self .less.remove(item)
else :
raise KeyError
else : # self.item == item
if self .less and self .more: # Two children are present
successor = self .more._least()
self .item = successor.item
if successor.item:
successor.remove(successor.item)
elif self .less: # One child on less
self ._replace( self .less)
elif self .more: # One child on more
self ._replace( self .more)
else : # Zero children
self ._replace( None )
def _least( self ) -> "TreeNode" :
if self .less is None :
return self
return self .less._least()
def _replace( self , new: Optional[ "TreeNode" ] = None ) -> None :
if self .parent:
if self == self .parent.less:
self .parent.less = new
else :
self .parent.more = new
if new is not None :
new.parent = self .parentremove()方法分为两部分。第一部分是对目标节点的递归搜索。
找到节点后，需要考虑三种情况：
- 当我们删除一个没有子节点的节点时，我们只需删除它并更新父节点以将链接替换为
None。使用从移除的节点到父节点的弱引用意味着内存清理和重用是即时的。 - 当我们删除一个子节点时，我们可以向上推一个子节点以替换父节点下的该节点。
- 当有两个孩子时，我们需要重组树。我们定位后续节点（在
more子树中最小的项）。我们可以用这个后续节点的内容替换要删除的节点。然后，我们可以删除重复的前后继节点。
我们依靠两种私人方法。_least()方法对给定树中的最小值节点执行递归搜索。_replace()方法检查父对象，看它是否应该接触less或more属性。
我们建立了一个全新的收藏。ABC 定义自动包含许多方法。这些继承的方法可能不是特别有效，但是它们是被定义的，可以工作，我们没有为它们编写代码。
>>> s1 = Tree(["Item 1", "Another", "Middle"])
>>> list(s1)
['Another', 'Item 1', 'Middle']
>>> len(s1)
3
>>> s2 = Tree(["Another", "More", "Yet More"])
>>>
>>> union= s1 | s2
>>> list(union)
['Another', 'Another', 'Item 1', 'Middle', 'More', 'Yet More']
>>> len(union)
6
>>> union.remove('Another')
>>> list(union)
['Another', 'Item 1', 'Middle', 'More', 'Yet More'] 这个例子向我们展示了 set 对象的 setunion操作符可以正常工作，尽管我们没有专门为它提供代码。由于这是一个包，物品也被正确复制。
在使用容器和集合时，我们有一个多步骤的设计策略：
- 考虑序列、映射和集合的内置版本。
- 考虑在集合模块中的库扩展，以及额外的，如 AutoT0T、AUT1 T1、和 TY2 T2。
- 考虑现有类定义的组成。在许多情况下，
tuple对象列表或dict列表提供了所需的特性。 - 考虑扩展前面提到的类中的一个，以提供其他方法或属性。
- 考虑将现有结构包装为提供附加方法或属性的另一种方式。
- 最后，考虑一种新的数据结构。一般来说，有很多仔细的分析可用。从维基百科的文章开始，比如这篇：http://en.wikipedia.org/wiki/List_of_data_structures 。
一旦确定了设计备选方案，评估将分为两部分：
- 接口与问题域的匹配程度。这是一个相对主观的决定。
- 通过
timeit测量数据结构的性能。这是一个完全客观的结果。
避免分析瘫痪是很重要的。我们需要有效地找到合适的藏品。
在大多数情况下，最好对正在工作的应用程序进行分析，以确定哪种数据结构是性能瓶颈。在某些情况下，在开始实施之前，考虑数据结构的复杂性因素将揭示其对特定类型问题的适用性。
Perhaps the most important consideration is this: for the highest performance, avoid search.
避免搜索是集合和映射需要哈希对象的原因。可散列对象可以位于集合或映射中，几乎不需要任何处理。在列表中按值（而不是按索引）查找项目可能需要大量时间。
下面是一个错误集合的比较，例如列表的使用和集合的正确使用：
>>> import timeit
>>> timeit.timeit('l.remove(10); l.append(10)', 'l =
list(range(20))')
0.8182099789992208
>>> timeit.timeit('l.remove(10); l.add(10)', 'l = set(range(20))')
0.30278149300283985 我们从列表中删除并添加了一个项目以及一个集合。
显然，滥用列表使其执行类似集合的操作会使集合的运行时间延长 2.7 倍。
作为第二个例子，我们将滥用一个列表，使其像映射一样。这是基于一个真实的示例，其中原始代码有两个平行列表来模拟映射的键和值。
我们将比较两个平行列表的正确映射，如下所示：
>>> timeit.timeit('i = k.index(10); v[i]= 0', 'k=list(range(20));
v=list(range(20))')
0.6549435159977293
>>> timeit.timeit('m[10] = 0', 'm=dict(zip(list(range(20)),list(range(20))))' )
0.0764331009995658 第一个示例使用两个平行列表。一个列表用于查找值，然后对并行列表进行更改。在另一种情况下，我们只是更新了一个映射。
显然，对两个平行列表执行索引和更新是一个可怕的错误。通过list.index()定位某物所需的时间是通过映射和哈希值定位某物所需时间的 8.6 倍。
在本章中，我们研究了一些内置类定义。内置集合是大多数设计工作的起点。我们通常以tuple、list、dict或set开头。我们可以利用namedtuple()为应用程序的不可变对象创建的tuple扩展。
除了这些类之外，我们还可以使用collections模式下的其他标准库类：
dequeChainMapdefaultdictCounter
我们也有三种标准的设计策略。我们可以包装这些现有的任何类，也可以扩展一个类。
最后，我们还可以发明一种全新的收藏品。这需要定义许多方法名和特殊方法。
在下一章中，我们将密切关注内置数字以及如何创建新类型的数字。与容器一样，Python 提供了丰富的内置数字。当创建一种新的数字时，我们必须定义许多特殊的方法。
在看了数字之后，我们可以看一些更复杂的设计技术。我们将看看如何创建自己的装饰器，并使用它们来简化类定义。我们还将介绍如何使用 mixin 类定义，这与 ABC 定义类似。