第 5 章 基于数组的序列
5.1 python 序列类型¶
在本章中，我们探讨 python 的各种“序列”类，即内嵌的列表类(list) 、元组类(tuple) 和字符串类(str) 。这些类之间有明显的共性，最主要的是：每个类都支持用下标访问序列元素，比如使用语法 seq[k] ；每个类都使用数组这种低层次概念表示序列。然而，在 python 中，这些类所表示的抽象以及实例化的方式有着明显的区别。因为这些类被广泛用于 python 程序中，又因为它们能够成为构件块，用这些构件块可以开发更复杂的数据结构， 所以，我们迫切需要搞清楚这些类的公共行为和内部运作机制。
行为¶
一个优秀的程序员有必要正确理解类的外部语义。列表、字符串和元组的使用看似简单，然而在理解与这些类相关的行为上，却有一些重要的细节（比如说复制序列意味着什 么，或者取序列的一部分又意味着什么） 。对类的行为有误解很容易导致程序中出现无意识 的错误。因此，我们要在头脑中为这些类建立准确的模型。这些模型将会帮助我们研究更高级的用法，比如使用多维数据集合表示列表的列表。
实现细节¶
关注这些类的内部实现似乎有悖于面向对象编程的原则。在 2.1.2 节中，我们强调过封装的原则，指出在使用类时不需要知道其内部实现细节。虽然这句话没错，即程序员仅需要理解类的公共接口的语法和语义就能够用类的实例写出合法且准确的代码，但程序的效率很大程度上依赖于其所使用组件的效率
渐近和实验分析¶
对于 python 序列类，我们依据在第 3 章给出的渐近分析符号来描述其各种操作的效率。我们也将对主要操作执行实验分析，给出和更具理论化的渐近分析相一致的实验性结论。
5.2 低层次数组¶
为了能准确描述 python 所表示序列类型的方法，我们必须先讨论计算机体系结构的低层次内容。计算机主存由位信息组成，这些位通常被归类成更大的单元，这些单元则取决于精准的系统架构。一个典型的单元就是一个宇节，相当于 8 位。
计算机系统拥有庞大数量的存储字节，为了能跟踪信息存储在哪个字节，计算机采用了 一个抽象概念， 即我们熟悉的存储地址。实际上，每个存储字节都和一个作为其地址的唯一 数字相关联（更正式地说，数字的二进制表示作为地址） 。例如，使用这种方式，计算机系统能够将” 字节＃2150" 中的数据和”字节＃2157" 中的数据进行对比。存储地址通常和存储系统的物理设计相协调，我们因此通常以顺序的方式描述这些数字。图 5 -1 给出了这样一 个图表，在该图表中，每个字节均被指定了存储地址。
尽管编号系统具有顺序性，但计算机硬件也是这样设计的，因此，从理论上说，基于这种存储地址， 主存的任何字节都能被有效地访问。从这个意义上说，我们将计算机主存称为随机存储存储器(Random Access Memory, RAM ) 。也就是说，检索字节＃8675309 就和检索字节＃309 一样容易。（在实践中，有很多复杂的因素，包括对缓存和外部存储器的使用， 我们会在 15 章解决一些这样的问题）使用渐近分析的符号，我们认为存储器的任一单个字节被存储或检索的运行时间为 O(1) 。
一般来说，编程语言记录标识符和其关联值所存储的地址之间的联系。比如，标识符 x 可能和存储器中的某一值关联，而标识符 y 和另一值关联。常见的编程任务就是记录一系列相关对象。例如，我们可能希望某一视频游戏能够记录此游戏的前十名玩家的分数。在此任务中，我们不会用 10 个变量来记录，而更倾向于为一个组赋以组名，并使用索引值指向该组内的高分。
一组相关变量能够一个接一个地存储在计算机存储器的一块连续区域内。我们将这样的表示法称为数组( array ) 。举一个实际的例子，一个文本字符串是以一列有序字符的形式存储的。在 python 中， 每个字符都用 Unicode 字符集表示，对于大多数计算机系统， python 内部用 16 位表示每个 Unicode 字符（ 即 2 个字节） 。因此， 一个 6 个字符的字符串，比 如 'SAMPLE' ，将会被存储在存储器的连续 12 个字节中，如图 5-2 所示。
虽然该字符串需要 12 个字节的存储空间，但我们仍把它描述为 6 字符数组。我们会将数组中的每个位置称为单元，并用整数索引值描述该数组，其中单元的开始编号为 0 、1 、 2 等。例如，在图 5-2 中，索引为 4 的数组单元的内容为 L, 并且存储在存储器的 2154 和 2155 字节中
数组的每个单元必须占据相同数量的字节。之所以这样要求，是为了允许使用索引值能够在常量时间内访问数组内的任一单元。尤其是，假如知道某一数组的起始地址（例如，在 图 5-2 中，起始地址为 2146 )，每个元素所占的字节数（例如，每个 Unicode 字符占 2 个字 节），和所要求的字符的索引值，通过计算 start + cellsize* index 便可得出其正确的内存地址。通过这个公式得出，单元 0 正好起始于数组的起始地址，单元 1 正好起始于数组起始地址后的一个 cellsize 字节， 等等。例如，图 5-2 中的单元 4 起始地址为 2146+2*4=2146+8=2154
当然，在数组内计算内存地址的算法是自动处理的。因此，程序员可以把字符数组理解得更通俗、更抽象，如图 5 - 3 所示。
5.2.1 引用数组¶
再举一个有用的例子： 假设想要为某医院开发一套医疗信息系统，来记录当前分配到病床的病人的名字。假定医院有 200 张床，为方便起见，这些床编号为 0 ~ 199 。我们可以考虑使用基于数组的数据结构来记录最近分配到这些病床上的病人的名字。例如，在 python 中，我们可能会用到一张姓名清单，如下所示：
['Rene','Joseph','Janet','Jonas','Helen' , 'Virginia' ,...]
在 python 中，为了用数组表示这样的列表， 必须要满足数组的每个单元字节数都相同这一条件。然而，元素是字符串，它们串的长度显然不同。python 可以用最长字符串（不仅目前存储的字符串，将来也可能存储任何字符串）来为每个单元预留足够的空间，但那样太浪费了。
相反， python 使用数组内部存储机制（即对象引用，来表示一列或者元组实例。在最低层，存储的是一块连续的内存地址序列，这些地址指向一组元素序列。图 5-4 所示即为该列表的高层视图。
虽然单个元素的相对大小可能不同，但每个元素存储地址的位数是固定的（比如，每个地址 64 位） 。在这种方式下， python 可以通过索引值以常量时间访问元素列表或元组。
在图 5-4 中，我们把医院病人的名字描述为字符串列表。当然，更有可能的是，该医疗信息系统可以管理每个病人更全面的信息，也许可以表示成 Patient 类的一个实例。从列表实现的观点看，同样的原则也适用于此，即列表仅保存那些对象引用的序列。同时需要注意，空对象(None) 的引用能作为列表的元素来表示医院的空床位。
列表和元组是引用结构这一事实对这些类的语义来说是很重要的。一个列表实例可能会以多个指向同一个对象的引用作为列表元素， 一个对象也可能被两个或更多列表中的元素所指向，因为列表仅仅存储返回对象的引用。例如，在计算列表的一小段时，结果产生了一个新的列表实例，该新列表指向了和原列表相同的元素，如图 5 - 5 所示。
当列表的元素是不变的对象时，正如图 5-5 中的整数实例一样，则两张表共享元素就显得没那么重要了，因为任何一张表都不能改变共享 对象。比如，若在此结构图中执行语句 temp[2] = 15, 这并未改变已存在的整数对象，而是 将 temp 列表单元 2 中的引用指向了不同的对象。图 5-6 所示即为执行后的结构图。
当通过复制创建一个新的列表时也是同样的情况：比如 backup = list(primes) ，就会对原列表复制出一张新列表。这张新列表即为浅拷贝（见 2.6 节），该列表和原列表指向同样的元素。当这些元素不可变时， 浅拷贝也没关系。假如列表的元素是可变的，利用 copython 模块的 deepcopython 函数可以复制列表的元素，得到一个具有全新元素的新列表，这种方式称为深拷贝
再给出一个更有用的例子：在 python 中，使用诸如 counters = [0]*8 这样的语法来初始 化整数数组，这是很常见的一种做法。该语法构造出一张长度为 8 、各元素为 0 的列表。从技术上讲，列表的 8 个单元都指向同一个对象，如图 5-7 所示。
乍一看，在此结构图中，这种极端的重叠现象着实令人担忧。然而，我们可以依据指向的整数是不可变的这一事实。即使执行诸如counters[2] += 1 这样的语法，技术上也不能改变现有的整数。只是计算出一个新的整数，值为 0 + 1, 并使单元 2 指向了这个新的值。图 5 -8 所示即为执行后的结构图。
下面对列表引用性质给出最后一个演示，我们注意到使用 extend 命令能将一个列表的所有元素添加到另一张列表的末尾。扩展列表的过程不是将那些元素复制过来，而是将元素的引用复制到末尾。图 5-9 所示即为调用 extend 函数的结果。
5.2.2 python 中的紧凑数组¶
在本节的介绍中，我们强调字符串是用字符数组表示的（而不是用数组的引用） 。我们将会谈到更直接的表示方式一紧凑数组(compact array) ， 因为数组存储的是位， 这些位表示原始数据（在字符串情况下，这些位即是字符） 。
在计算性能方面，紧凑数组比引用结构多几大优势。最重要的是，使用紧凑结构会占用更少的内存，因为在内存引用序列的显示存储上没有开销（原始数据除外），即引用结构通常会将 64 位地址存入数组，无论存储单个元素的对象有多少位。另外， 字符串中的每个 Unicode 字节存储在紧凑数组中仅需要两个字节。如果每个字符都以单字符字符串独立存储，那显然将会占用更多字节
接下来研究另一个案例，假设想要存储 100 万个 64 位整数。理论上，我们或许希望仅仅占用 64 000 000 位，然而通过估计得出 python 列表将会占用的容量是该容量的 4 ~ 5 倍。每个列表元素都将产生一个 64 位存储地址，并将此地址存储于原始数组中，整数实例会被存储于内存的其他地方。python 允许查询每个对象在主存中实际占用多少位字节——用系统模块中的 getsizeof 函数即可得出。在我们的系统中， 一个标准整型对象需要占用 14 字节 内存（超出 4 字节的部分用于表示实际 64 位地址） 。总之，列表每个条目要占用 18 个字节， 而不是像整数紧凑列表那样仅需要 4 个字节。
紧凑结构在高性能计算方面的另一个重要优势是：原始数据在内存中是连续存放的。注意，引用结构没有这种情况。也就是说，即使列表对存储地址做了谨慎的规定，但是这些元素会被存入内存的什么位置并不受该列表所决定。由于缓存的工作性质和计算机的存储层次结构，将数据存到其他可能用于相同计算的数据旁边通常是有利的。
尽管引用结构明显效率低下，但在本书中，我们更看重 python 列表和元组所提供的便利。我们将会在第 15 章讨论紧凑结构，届时将集中讨论内存使用对数据结构和算法的影响。python 提供了几种用于创建不同类型的紧凑数组的方法。
紧凑数组主要通过一个名为 array 的模块提供支撑。该模块定义了一个类（也命名为 array ) ，该类提供了紧凑存储原始数据类型的数组的方法。图 5-10 所示即为这样一个整型数组的描述
array 类的公共接口通常和 python 的 list （列表） 一致。然而，该类的构造函数需要以类型代码 ( type code ) 作为第一个参数，也即一个字符，该字符表明要存入数组的数据类型。举一个实际的例子， 类型代码 'i' 表明这是一个（有符号的） 整型数组，通常表示每个元素至少 16 位。我们可以把图 5 - 10 所示的数组声明如下：
primes = array('i' , [2, 3, 5, 7, 11, 13, 17, 19])
类型代码允许解释器确定数组的每个元素需要多少位。正如表 5-1 所示， array 模块支持 类型代码，这些类型代码主要是基于 C 编程语言(python 使用最广泛的发布版就是用 C 语言 实现） 的本地数据类型。C 语言数据的精确位数是跟系统有关的，但可以给出通常的范围。
array 模块不支待存储用户自定义数据类型的紧凑数组。这种结构的紧凑数组可以用一个名为 ctypes 的底层模块来创建(5.3. 1 节将会对 ctypes 模块做更多讨论） 。
5.3 动态数组和摊销¶
在计算机系统中，创建低层次数组时，必须明确声明数组的大小，以便系统为其存储分配连续的内存。例如，图 5 - 11 给出了一个 12 字节的数组，该数组被分配在地址 2146 ~ 2157 的位置。
由于系统可能会占用相邻的内存位置去存储其他数据，因此数组大小不能靠扩展内存单元来无限增加。在表示 python 元组( tuple ) 或者字符串(str) 实例的情形中，这种限制就没什么问题了。由于这些类的实例变量都是不可变的，因此当对象实例化时，低层数组的大小就已确定了。
python 列表( Iist ) 类提供了更有趣的抽象。虽然列表在被构造时已经有了确定的长度，但该类允许对列表增添元素，对列表的总体大小没有明显的限制。为了提供这种抽象， python 依赖于一种算法技巧，即我们所熟知的动态数组( dynamic array )
为了理解动态数组的语义，首先关键的一点是： 一张列表通常关联着一个底层数组，该数组通常比列表的长度更长。例如，用户创建了一张具有 5 个元素的列表，系统可能会预留 一个能存储 8 个对象引用的底层数组（而不止 5 个） 。通过利用数组的下一个可用单元，剩余的长度使得增添列表元素变得很容易。
假如用户持续增添列表元素，所有预留单元最终将被耗尽。此时，列表类向系统请求一 个新的、更大的数组，并初始化该数组，使其前面部分能与原来的小数组一样。届时，原来的数组不再需要，因此被系统回收。这种策略直观上就像寄居蟹，当旧的贝壳不足以容纳它时，它便会钻到更大的贝壳里
try与except（该部分内容来自 python 标准库的内置文档）
try语句的工作原理如下：
- 首先，执行 try 子句 （
try和except关键字之间的（多行）语句）。- 如果没有触发异常，则跳过 except 子句，
try语句执行完毕。- 如果在执行
try子句时发生了异常，则跳过该子句中剩下的部分。 如果异常的类型与except关键字后指定的异常相匹配，则会执行 except 子句，然后跳到 try/except 代码块之后继续执行。- 如果发生的异常与 except 子句 中指定的异常不匹配，则它会被传递到外部的
try语句中；如果没有找到处理程序，则它是一个 未处理异常 且执行将终止并输出如上所示的消息。
try语句可以有多个 except 子句 来为不同的异常指定处理程序。 但最多只有一个处理程序会被执行。 处理程序只处理对应的 try 子句 中发生的异常，而不处理同一try语句内其他处理程序中的异常。 except 子句 可以用带圆括号的元组来指定多个异常，例如:... except (RuntimeError, TypeError, NameError): ... pass
经验证明， python 的 list 类确实基于这种策略。我们在代码段 5-1 中给出源代码，在代码段 5-2 中给出程序样例输出，并使用了 sys 模块提供的 getsizeof 函数。该函数用于给出在 python 中存储对象的字节数。对于列表，该函数仅给出此列表关联的数组和其他实例变量 的字节数之和，而不包括任何分配给被该列表引用的元素的内存。
import sys
try:
n = int(sys.argv[1])
except:
n = 100
import sys # provides getsizeof function
data = []
for k in range(n): # NOTE: must fix choice of n
a = len(data) # number of elements
b = sys.getsizeof(data) # actual size in bytes
print('Length: {0:3d}; Size in bytes: {1:4d}'.format(a, b))
data.append(None) # increase length by one
测试样例输出
Length: 0; Size in bytes : 72
Length: 1; Size in bytes : 104
Length: 2; Size in bytes : 104
Length: 3; Size in bytes : 104
Length: 4; Size in bytes : 104
Length: 5; Size in bytes : 136
Length: 6; Size in bytes : 136
Length: 7; Size in bytes : 136
Length: 8; Size in bytes : 136
Length: 9; Size in bytes : 200
Length: 10; Size in bytes : 200
Length: 11; Size in bytes : 200
Length: 12; Size in bytes : 200
Length: 13; Size in bytes : 200
Length: 14; Size in bytes : 200
Length: 15; Size in bytes : 200
Length: 16; Size in bytes : 200
Length: 17; Size in bytes : 272
Length: 18; Size in bytes : 272
Length: 19; Size in bytes : 272
Length: 20; Size in bytes : 272
Length: 21; Size in bytes : 272
Length: 22; Size in bytes : 272
Length: 23; Size in bytes : 272
Length: 24; Size in bytes : 272
Length: 25; Size in bytes : 272
Length: 26; Size in bytes : 352
在评估实验结果时，首先注意代码段 5-2 的第一行输出。可以注意到， 空列表已经请求了一定数量字节的内存（在我们的系统中是 72 个） 。事实上， python 中每个对象都保存了一些状态，例如，标志着该对象属于哪个类的引用。尽管不能直接访问列表的私有实例变量， 但可以推测该列表以某种形式保存的一些状态信息，类似于：
- _n → 列表当前存储的实际元素的个数
- _capacity → 当前所分配数组中允许存储的元素最大个数
- _A → 当前所分配数组的引用（最初为 None)
当第 1 个元素添入列表时，我们就会检查底层结构的大小是否改变。特别需要注意的 是， 字节数从 72 跳到 104, 增加了 32 个字节。本实验是在 64 位机器上运行的，这表明每个内存地址是 64 位（即 8 个字节） 。我们推测增加的 32 个字节即为分配的用于存储 4 个对象引用的底层数组大小。这一推测符合这样的事实：当对列表增添第 2 个、第 3 个或者第 4 个元素时，我们没有发现在内存占用上有任何改变。
当增添第 5 个元素时，我们注意到内存占用的字节数从 104 跳到 136 。假定列表最初占 72 个字节， 最后变为总共 136 字节，增加 64 = 8 X 8 个字节，这表明我们提供了 8 个对象引用的扩展空间。另外，当增添第 9 个元素前，内存占用都不再增加，这也跟实验结果相一 致。从这个角度来讲， 200 个字节可被视为最初的 72 个字节再加上用于存储 16 个对象引用 的 128 个字节。当增添第 17 个元素后，整个存储占用将变为 272 = 72 + 200 = 72+ 25 X 8, 因此，足够存储 25 个对象引用。
因为列表是引用结构，对列表实例使用函数 getsizeof 得出的结果仅包括该列表主要结构的大小，不算由对象（即列表元素）所占用的内存。在实验中，我们不断给列表增添 None 对象，并不关心单元将会放什么内容，但是我们可以向列表中增添任何类型对象，结果不受 元素大小（即 getsizeof(data) ）所给出的字节数的影响。
假如想继续该实验并做进一步迭代，我们或许想搞清楚：每次当前一个数组使用完后，python 会创建一个多大的数组（见练习 R-5.2 和 C-5. 13 ) 。在探究使用 python 创建的精确字节数之前，我们先继续本节学习，接下来给出用于实现动态数组和执行该数组性能渐近分析 的一般方法。
5.3.1 实现动态数组¶
尽管 python 的 list 类给出了动态数组的一种高度优化的实现（我们在本书的后续部分要依赖该实现方法） ， 但学习该类是如何被实现的仍对我们有指导性意义。
关键在于提供能够扩展用于存储列表元素的数组 A 的方法。当然，实际上我们不能扩展数组，因为它的大小是固定的。当底层数组已满，而有元素要添入列表时，我们会执行下面的步骤：
- 分配一个更大的数组 B
- 设 B[i] = A[i] ( i = 0, ··· , n - 1 ) ，其中 n 表示条目的当前数量
- 设 A = B , 也就是说，我们以后使用 B 作为数组来支持列表
- 在新的数组里增添元素
图 5-12 中给出了上述步骤的示意图。
接下来需要思考一个问题： 新数组应该多大？通常的做法是： 新数组大小是已满的旧数组大小的 2 倍。在 5.3.2 节中，我们会对这种做法进行数学分析。
在代码段 5-3 中，我们使用 python 给出了动态数组的一种具体实现。DynamicArray 类的设计便是运用了本节所讨论的思想。虽然和 python 中 list 类的接口一致，但这里仅提供部分功能： append 方法以及访问器__len__ 和 __getitem__。底层数组的创建由 ctypes 模块 提供。因为在本书的剩余部分不会一直使用这种底层结构，所以我们不再对 ctypes 模块进行详细说明。我们在私有实例方法_make_array 中封装了必要的指令，该指令用于声明原始数组。扩展的主要过程在非公开的 _resize 方法中实现。
import ctypes # provides low-level arrays
class DynamicArray:
"""A dynamic array class akin to a simplified python list."""
def __init__(self):
"""Create an empty array."""
self._n = 0 # count actual elements
self._capacity = 1 # default array capacity
self._A = self._make_array(self._capacity) # low-level array
def __len__(self):
"""Return number of elements stored in the array."""
return self._n
def __getitem__(self, k):
"""Return element at index k."""
if not 0 <= k < self._n:
raise IndexError('invalid index')
return self._A[k] # retrieve from array
def append(self, obj):
"""Add object to end of the array."""
if self._n == self._capacity: # not enough room
self._resize(2 * self._capacity) # so double capacity
self._A[self._n] = obj
self._n += 1
def _resize(self, c): # nonpublic utitity
"""Resize internal array to capacity c."""
B = self._make_array(c) # new (bigger) array
for k in range(self._n): # for each existing value
B[k] = self._A[k]
self._A = B # use the bigger array
self._capacity = c
def _make_array(self, c): # nonpublic utitity
"""Return new array with capacity c."""
return (c * ctypes.python_object)() # see ctypes documentation
def insert(self, k, value):
"""Insert value at index k, shifting subsequent values rightward."""
# (for simplicity, we assume 0 <= k <= n in this verion)
if self._n == self._capacity: # not enough room
self._resize(2 * self._capacity) # so double capacity
for j in range(self._n, k, -1): # shift rightmost first
self._A[j] = self._A[j-1]
self._A[k] = value # store newest element
self._n += 1
def remove(self, value):
"""Remove first occurrence of value (or raise ValueError)."""
# note: we do not consider shrinking the dynamic array in this version
for k in range(self._n):
if self._A[k] == value: # found a match!
for j in range(k, self._n - 1): # shift others to fill gap
self._A[j] = self._A[j+1]
self._A[self._n - 1] = None # help garbage collection
self._n -= 1 # we have one less item
return # exit immediately
raise ValueError('value not found') # only reached if no match
5.3.2 动态数组的摊销分析¶
本节中，我们对动态数组相关操作的运行时间做具体分析。我们用 3.3.1 节介绍的大 Ω 符号，对这些操作的算法或步骤的运行时间给出渐近下界。
用新的、更大的数组替换数组的策略乍一看可能看起来很慢，因为单个追加操作可能需要 Ω(n) 的时间来执行，其中 n 是数组中当前元素的数量。 但是，请注意，通过在数组替换期间将容量加倍，我们的新数组允许我们在必须再次替换数组之前添加 n 个新元素。 这样，每个昂贵的操作都有许多简单的追加操作（见图 5.13）。 这一事实使我们能够证明，就其总运行时间而言，对最初为空的动态数组执行一系列操作是有效的。
我们使用一种称为摊销(amortization) 的算法设计模式进行证明： 事实上，在动态数组中执行一系列增添操作效率是非常高的。为了做摊销分析 ( amortized analysis) ，我们使用一种会计学技巧：把计算机视为一个投币装置，对每个固定的运行时间均支付一枚网络硬币(cyber-dollar) 。当执行一个操作时，当前 “银行账户” 中要有足够的网络硬币来支付此次操作的运行时间。因此，在任意计算中所花费的网络硬币总数将会和该计算的运行时间成正比。使用该分析方法的妙处在于我们可以增加某些操作的投入，以减低其他操作所需的网络硬币。
命题 5-1: 设 S 是一个由具有初始大小的动态数组实现的数组，实现策略为： 当数组已满时， 将此数组大小扩大为原来的 2 倍。S 最初为空， 对 S 连续执行 n 个增添操作的运行时间为 O(n)
证明： 假定不需要扩大数组的情况下，向 S 中增加一个元素所需时间需支付一个网络硬币。另外， 假定数组大小从 k 增长到 2k 时，初始化该新数组需要 k 个网络硬币。我们将会对每个增添操作索价 3 个网络硬币。因此， 对不需要扩大数组的增添操作我们多付了 2 个网络硬币。在不需要扩大数组的增添操作中，我们多收的 2 个硬币将被视为 “存入“ 该元素所插入的单元中。当数组 S 大小为 \(2^i\) 并且 S 中有\(2^i\) 个元素时，对于 \(i \ge 0\), 增加元素将会出现溢出。此时，将数组大小扩大 1 倍需要 \(2^i\) 个网络硬币。幸运的是，这些硬币能够在内存单元从 \(2^{i-1}\) 到 \(2^i - 1\) 中找到（见图 5-14 ) 。注意到前一次溢出出现在当元素个数第一次比 \(2^{i-1}\) 大时，所以，在单元 \(2^{i-1}\) 到 \(2^i-1\) 中存储的网络硬币还未消费。因此，我们有了一个有效的摊销方案： 每个操作索要 3 个网络硬币，所有运行时间都用硬币来支付， 即我们可以用 3n 个网络硬币来支付 n 次增添操作。换句话说，每个增添操作的摊销运行时间为 O(1) ； 因此， n 次增添操作的总体运行时间为 O(n)
大小按几何增长¶
虽然在命题 5 - 1 的证明中，我们每次都是把数组扩大 1 倍，但是对 “数组大小以任意几何增长级数（见 2.4.2 节对几何级数的讨论）扩大，每次操作的摊销运行时间仍为 O(1)" 这 一结论是可以证明的。当选定了几何基数时， 在运行效率和内存使用之间便存在一个折中问 题。例如， 当基数为 2 时（即数组扩大两倍），假如最后一个插入操作使得数组大小发生改变， 则数组的大小本质上会变为其需要的 2 倍来结束该事件。如果不希望最后浪费太多内存，可以让数组当前大小仅增大 25% （ 即几何基数为 1.25) ，这种做法会在中间出现更多的调整数组大小的事件。使用一个更大的常数，例如在命题 5-1 的证明中使用的常数为每个操作需要 3 个网络硬币，我们仍可能证明摊销运行时间为 O(1) （见练习 C-5.15 ) 。证明的关键是：增添的内存大小是否正比于当前数组大小
避免使用等差数列¶
为了避免一次扩充太大空间，可能会对动态数组执行这样的策略： 每次要调整数组大小时，都要预留固定数量的额外单元。不幸的是，这种策略的整体性能明显糟糕。在极端情况 下，如果每次增加一个单元， 则会导致每个增添操作都将调整数组大小，继而就是类似地求 和 1 + 2 + 3+ … + n, 所以总体运行时间为 Ω(\(n^2\)) 。如图 5 -15 所示， 如果每次增加 2 个或 3 个单元也只是稍微改善，但总体运行时间仍为 \(n^2\)
每次调整大小时都采用固定的增量，因此中间数组大小将会成等差数列，正如命题 5-2 所示，总体运行时间在操作个数上表现为平方。从直观上讲，即使每次增加 1000 个单元， 对于大数据集来说，也无济于事。
命题 5-2: 对初始为空的动态数组执行连续 n 个增添操作， 固定的增量，则运行时间为 \(\Omega(n^2)\) 。
证明： 设 c > 0 , 表示每次调整数组大小时的固定增量。在连续的 n 个 append 操作中， 时间将会花费在分别初始化大小为 c, 2c, 3c, … , mc 的数组上面， 其中 \(m= [n/c]\) , 因此，总体运行时间将会正比于 \(c + 2c + 3c +···+ mc\) 。根据命题 3-3, 得出和为
■
因此，执行 n 个 append 操作花费的时间为 \(\Omega(n^2)\)
从命题 5 -1 和 5 -2 中得到一个教训： 算法设计中，一个细微的差异在渐近性能上能表现出巨大的不同， 细致的分析在设计数据结构中能起到重要的作用。
内存使用和紧凑数组¶
当对动态数组增添数据时， 这种按几何增长的模式所带来的另一结果是： 最终数组大小都确保能正比于元素总个数。也就是说，数据结构占用 O(n) 的内存，这是数据结构一个非常理想的属性。
假如一个容器，例如一张 python 列表，能够提供删除一个或多个元素的操作，那就更要注意确保动态数组占用 O(n) 的内存。风险是：重复的插入操作可能会导致底层数组肆意增大，当许多元素被删除后，元素的实际数量与数组大小之间便不存在正比关系。
有时，会对这种数据结构采用一种健壮的实现方式一一紧凑底层数组，在此期间，单个操作都保持 O(1) 的摊销绑定。然而，注意确保在扩充和收缩底层数组时，结构不能摊销（改变），因为在这种情况下，摊销绑定将不能实现。在练习 C-5.16 中，我们探索一种策略：无论实际元素个数比数组大小的 1/4 少多少，我们都对半平分数组，这样能确保数组大小至少是元素个数的 4 倍。在练习 C -5.17 和 C-5.18 中，我们将探究这种策略的摊销分析。
以下内容摘录自 Wiki：
摊销分析在电脑科学中，是用于算法分析中的方法，摊销分析常用于分析数据结构（动态的数据结构），在使用摊销分析前须知道数据结构各种操作所可能发生的时间，并计算出最坏情况下的操作情况并加以平均，得到操作的平均耗费时间。摊销分析只能确保最坏情况性能的每次操作耗费的平均时间，并不能确认平均情况性能。
一个简单的例子，一个长度为 n 的 list，在 list 的最后要加入一笔新的资料此时要花费的操作时间为 O(n)，此时也是加入新的资料的最糟糕的情况。但是，一个 n 个插入的操作序列仍然可以在 O(n) 的时间内完成，因为剩下的插入可以在常数时间内完成，因此 n 个插入可以在 O(n) 的时间内完成。因此每操作的平摊耗费为 O(n) / n = O(1)。
注意摊销分析与平均时间分析和概率算法的概率分析不同。在平均时间分析中，我们平均化所有可能的输入；在概率算法的概率分析中，我们平均化所有可能的随机选择；在摊销分析中，我们平均化一系列操作的耗费。平摊分析假设的是最坏情况输入并且通常不运行随机选择。
摊销分析中几种常用的技术:
聚合分析决定 n 个操作序列的耗费上界 T(n)，然后计算平均耗费为 T(n) / n。 记账方法确定每个操作的耗费，结合它的直接执行时间及它在对运行时中未来操作的影响。通常来说，许多短操作增量累加成“债”，而通过减少长操作的次数来“偿还”。 势能方法类似记账方法，但通过预先储蓄“势能”而在需要的时候释放。
动态数组
动态数组的摊销分析 考虑一个随元素个数增加而增长的动态数组，比如 Java 的 ArrayList 或者 C++的 std::vector。如果我们的数组大小从 4 开始，那么来向其中增加四个元素的时间就是一个常数。然而，若要将第五个元素加入其中，那么会花费更多时间，因为我们此时必须要创建一个两倍于当前数组大小的数组（8 个元素），把老元素拷贝到新数组中，然后增加一个新元素。接下来的三次加入操作也同样会花费常数时间，然后在数组被填满后则又需要一轮新的加倍扩充。
一般地，如果我们考虑任意一个任意的 n 大小的数组并对其进行 n + 1 次加入操作。我们注意到，所有的加入操作都是常数时间的，除了最后一个，它会花费 O(n) 时间在大小加倍上。因为我们进行了 n + 1 次加入操作，我们可以将数组加倍的时间平摊到所有的加入操作上，因此得到加入操作的平均时间是 \({\frac {nO(1)+O(n)}{n+1}}=O(1)\)。它是一个常数。
总结¶
对于最坏情况下（初始底层数组大小为 1 ，加入 n 个元素），若以每次扩增底层数组大小的二倍为例，并且在未达到需要扩容的大小前，每次增加元素所需的时间复杂度是 O(1)，那么总共需要花费的时间复杂度为
因此，摊销到每一次增添元素的操作上，每次增添元素所需要的时间复杂度为
此外，同样考虑每次增添数组时仅增加常数大小的扩增方法，当从最坏情况出发时，所需要的时间复杂度为
5.3.3 python 列表类¶
5.3 节开篇处的代码段 5-1 和 5-2 给出了实验性证据： python 列表类使用动态数组的形式来存储内容。然而，对中间数组大小的细致测试（见练习 R-5.2 和 C-5.13 ) 表明， python 既不是使用纯粹的几何级数，也不是使用等差数列来扩展数组。
这表明， append 方法的 python 实现很清晰地展现了摊销常量时间的行为。我们可以用实验证明这一事实。虽然我们应该关注一些更花费时间的调整数组大小的操作， 但单个增添操作通常都执行得太快， 以至于我们很难精确测量该过程的时间。通过对初始为空的列表执 行连续 n 个增添操作，并算出每个操作所平均花费的时间，我们就能对摊销花费在每个操作上的时间做更精准的测量。代码段 5 -4 给出了一个函数来执行这个实验。
import sys
from time import time
try:
maxN = int(sys.argv[1])
except:
maxN = 10000000
from time import time # import time function from time module
def compute_average(n):
"""Perform n appends to an empty list and return average time elapsed."""
data = []
start = time() # record the start time (in seconds)
for k in range(n):
data.append(None)
end = time() # record the end time (in seconds)
return (end - start) / n # compute average per operation
从技术上说，从开始到结束所耗费的时间，除了调用 append 函数的时间，还包括维持循环迭代的时间。如表 5-2 所示，随着 n 值的增大， 给出了该实验的实证结果。我们看到较小的数据集往往会有更大的平均花费时间，也许部分原因在于循环的开销。在使用这种方式测量摊销花费时，也会产生一些自然偏差，因为最终调整大小都跟 n 有关会对其产生影响。从整体来看，每个 append 操作的摊销时间都独立于 n, 这点似乎很明确。
5.4 python 序列类型的效率¶
在上一节中，我们依据执行策略和效率，初步学习了 python 列表( list ) 类的基础内容。在本节中，我们继续检测所有 python 序列类型的性能。
5.4.1 python 的列表和元组类¶
列表类的 nonmutating 行为是由元组(tuple) 类所支持的。我们注意到元组比列表的内存利用率更高， 因为元组是固定不变的，所以没必要创建拥有剩余空间的动态数组。表 5 -3 给出了列表和元组类中 nonmutating 行为的渐近效率。下面对其中的内容进行解释。
常量时间操作¶
实例的长度之所以能在常量时间内得到， 是因为该实例明确包含了这一状态信息。通过访问底层数组，保证了 data[j] 的常量时间效率
表 5.3：列表和元组类的非变异行为的渐近表现。 标识符 data、data1 和 data2 指定列表或元组类的实例，n、n1 和 n2 指定它们各自的长度。 对于包含检查和索引的方法，k 表示最左边出现的索引（如果没有出现，则 k = n）。 对于两个序列之间的比较，我们让 k 表示它们不同意的最左边的索引，否则 k = min(n1,n2)。
搜寻值的出现¶
每个 count 、index 和__contains__方法均从左往右迭代遍历序列。实际上， 2.4.3 节的代码段 2-14 演示了这些行为是怎样被实现的。值得注意的是，当执行 count 方法时，必须循环遍历整个序列。当检索该容器中是否存在某个元素或者确定某个元素下标时，假如该 元素存在， 一旦从左开始第一次找到它，便立即退出循环。因此， count 方法需要检测序列的 n 个元素，而 index 和 __contains__方法只有在最坏的情况下才会检测 n 个元素，但往往都会更快。我们可以给出实验证据：设 data = list(range(10 000 000))，在 data 中找 5, 在 data 中找 9 999 995, 或者甚至失败的测试，如在 data 中找 -5, 比较这些测试之间的相对效率。
字典比较¶
两个序列之间的对比被定义为字典。在最坏的情况下，评估这一情况需要运行时间正比于两序列中长度较短序列的迭代（因为当一个序列结束时，字典结果已能被确定） 。而在一 些情况下，能更高效地评估测试结果。例如，若评估 [7, 3 , … ] < [7, 5,... ］， 很明显，不用再测试列表剩余部分便已知结果是 True, 因为左运算对象的第二个元素严格小于右运算对象的第二个元素。
创建新的实例¶
表 5 -3 的后三个行为是在一个或多个原有实例的基础上构造的一个新实例。在所有情况下，运行时间都取决于构造和初始化实例所耗费的时间，因此，渐近行为正比于该实例的长度。于是，我们发现数据段 [6 000 000 : 6 000 008] 能够被立即构建成功，因为它仅有 8 个 元素。数据段 [6 000 000 : 7 000 000] 有一百万个元素，因此要花费更多的时间去创建。
变异行为¶
表 5 -4 描述了 list 类变异行为的效率。最简单的行为是 data[j] ＝ val , 且该行为被特殊的__ setitem__方法所支持。此行为在最坏情况下的运行时间为 O(1) ，因为其仅用一个新值替换列表的一个元素。其他元素不受影响且底层数组的大小不变。值得分析的更有趣的行为是向列表中增添元素或从列表中删除元素
表 5.4：列表类变异行为的渐近表现。 标识符 data、data1 和 data2 指定列表类的实例，n、n1 和 n2 指定它们各自的长度。
向列表中增添元素¶
在 5.3 节中，我们充分探讨了 append 方法。在最坏的情况下，因为底层数组需要调整， 因此运行时间为 Ω(n) ，但在摊销情况下，运行时间为 O(1) 。列表同样支持 insert(k, value) 这一方法，此方法将给定的值插入列表索引 \(0\le k\le n\) 的位置，该位置通过将所有后续元素向前移动一个单位得到。为了解释清楚，在代码段 5-3 介绍的 DynamicArray 类的语义 下，代码段 5-5 给出了此方法的一种实现方式，使用了代码段 5-3 的 DynamicArray 类。在分析此过程的效率时有两个复杂因素。首先，我们注意到增添一个元素需要调整动态数组大小。这部分工作对于每个 append 操作来说，在最坏情况下运行时间为 Ω(n) ，但摊销时间仅 O(1) 。 insert 操作的另一个代价是移动元素来为新元素提供位置。此过程的时间取决于新元素的索引以及由此产生的移动后续元素的个数。
def insertion_sort(A):
"""Sort list of comparable elements into nondecreasing order."""
for k in range(1, len(A)): # from 1 to n-1
cur = A[k] # current element to be inserted
j = k # find correct index j for current
while j > 0 and A[j-1] > cur: # element A[j-1] must be after current
A[j] = A[j-1]
j -= 1
A[j] = cur # cur is now in the right place
如图 5-16 所示，循环过程将索引 n-1 的引用复制到索引 n 内，将索引 n-2 的引用复制到索引 n-1 内，如此往复，直到将索引 k 的引用复制到索引 k+1 内。插入索引 k 内需要 的总摊销时间为 O(n - k + 1)
在 5.3.3 节中， 当探讨 python 的 append 方法的效率时，我们做了这样的实验：在不同大小的列表上重复调用，计算耗费时间的平均值（见代码段 5-4 和表 5-2) 。我们将用 insert 方法重复该实验，并尝试用三种不同的访问模式。
- 第一种情况，我们在列表的开始位置进行重复插入，
for n in range(N)
data.insert(0,None)
- 第二种情况，我们在列表接近中间的位置进行重复插入，
for n in range(N):
data .insert(n // 2, None)
- 第三种情况，我们在列表的结束位置进行重复插入，
for n in range(N):
data.insert(n, None)
表 5 -5 给出了实验的结果，记录了每个操作的平均时间（不是整个循环的总时间） 。正如所预料的那样，我们看到在列表的开始位置做插入是最费时的，每个操作插入时间呈线性，因而运行时间仍为 Ω(n) 。在结束位置做插入表现为 O(1) 的运行时间，类似于增添操作。
从列表中删除元素¶
python 的 list 类提供了几种从列表中删除元素的方法。调用 pop() 删除列表的最后一个 元素。这是最高效的，因为其他所有元素都保持在自己的原有位置。这虽然是一个效率为 O(1) 的操作， 但由于 python 不定时地收缩底层数组以节省内存，因此绑定是摊销的。
带参数的方法 pop(k) 能够删除列表中索引为 k < n 的元素，并把所有后续元素往左移动，以填补由删除操作导致的空缺。该操作的效率 为 O(n < k)，因为移动的数量取决于索引 k 的选择，如图 5 -17 所示。注意，这表明 pop(0) 是最耗时的调用，运行时间为 Ω(n) 。（见练习 R-5.8 中的实验）
list 类提供了另一种名为 remove 的方法，该方法允许调用者指定要删除的值（不是值的索引） 。正式地说，该方法仅删除列表中第一次 出现的指定值，当未找到该值时，生成一个 ValueError 异常。在代码段 5-6 中，再次利用 DynamicArray 类做说明，给出此行为的一种实现方式。
有趣的是，对于 remove 方法来说，没有 “ 高效＂的情况：每一次调用都需要 Ω(n) 的运行时间。该过程部分工作用于从列表开头进行搜索，直至找到索引为 k 的值，而剩余的从 k 到最后的迭代用于往左移动元素。该线性行为能用实验观察到（见练习 C-5.24 ) 。
def remove(self, value):
”””Remove first occurrence of value (or raise ValueError).”””
# note: we do not consider shrinking the dynamic array in this version
for k in range(self. n):
if self. A[k] == value: # found a match!
for j in range(k, self. n − 1): # shift others to fill gap
self. A[j] = self. A[j+1]
self. A[self. n − 1] = None # help garbage collection
self. n −= 1 # we have one less item
return # exit immediately
raise ValueError( value not found ) # only reached if no match
扩展列表¶
python 提供了一个名为 extend 的方法，该方法能将一张列表的所有元素增添到另一张列表的末尾。在作用上，调用 data.extend(other) 输出的结果和如下代码输出的结果相同：
for element in other
dara.append(element)
在任何情况下，运行时间都正比于另一张列表的长度，并且之所以摊销，是因为第一张列表的底层数组需要调整大小以容纳增添的元素。
在实践中，相对于重复调用 append 方法，我们倾向于选择 extend 方法，因为渐近分析中隐含的常数明显更小。Extend 方法效率更高缘于三个方面： 首先，使用合适的 python 方法总会有一些优势，因为这些方法通常使用本地编译语言进行执行（不是用作解释 python 代码） 。其次，与调用很多独立的函数相比，调用一个函数完成所有工作的开销更小。最后， extend 提升的效率来源于更新列表的最终大小能提前计算出。假如第二个数据集是非常大的，当重复调用 append 方法时，底层动态数组会有多次调整大小的风险。若调用一次 extend 方法，最多执行一次调整操作。练习 C-5.2 2 用实验探究了这两种方法的相对效率。
构造新列表¶
有几种用于构造新列表的语法。在几乎所有情况下，该行为的渐近效率在创建列表的长度方面是线性的。然而，与前面讨论的 extend 方法的情况类似，在实际效率上有明显的不同
在 1.9.2 节中，使用一个诸如 squares = [k*k for k in range(1,n + 1)] 的例子作为
squares = []
for k in range(1, n+1):
squares.append(k*k)
的一种速记方式，并由此引入了列表推导式( list comprehension ) 的话题。实验将会证明使用列表推导式语法比不断增添数据来建表速度明显更快（见练习 C-5.23 ) 。
类似地，使用乘法操作初始化一张具有固定值的列表，也是一种很常见的 python 风格。例如，语句 [0]*n 生成一张长度为 n 、所有值都等于 0 的列表。这样做不但语法简便，而且比逐步构造这样的表效率更高
5.4.2 python 的字符串类¶
在 python 中，字符串是非常重要的。我们在 1.3 节中，通过对不同运算符的讨论，介绍了字符串的使用。在附录 A 的表 A-1 ～表 A-4 中，给出了该类已命名方法的综合概要。本节中，我们不再正式分析每个行为的效率，却希望在一些值得注意的问题上做一些批注。一般来说，我们用 n 表示字符串的长度。对于那些需要另一个字符串作为样例的操作，我们用 m 表示样例字符串的长度。
对许多行为的分析常靠直觉。例如，生成新字符串的方法（如 capitalize 、center 、strip 方法）需要的时间与该方法所生成的字符串长度之间呈线性关系。字符串的许多行为（例如， islower ) 以布尔条件进行测试，在最坏情况下需要检查 n 个字符， 此时运行时间为 Ω(n) 。但是当结果很明显时，循环就很快结束（例如，若第一个字符是大写字母， islower 能立即返回 False) 。比较操作符（例如， ＝＝，＜） 也属于这一种情况
样例匹配¶
有一些更有趣的行为，从箕法角度来说，这些行为在某种程度上取决于在较大的字符串中找到字符样例。所要寻找的目标是这些方法的核心（例如__contains__、find 、index 、 count 、replace 和 split ) 。字符串算法将会是第 13 章的课题， 13.2 节的重心是特别著名的模式匹配 ( pattern matching) 问题。有一种运行时间为 O(m n) 的简单实现方法： 我们为此样例考虑了 n - m + 1 种可能的起始索引， 每个起始索引都需要花费 O(m) 的运行时间用于检查该样例是否匹配。而在 13.2 节中，我们将会编写一个算法， 用于在 O(n) 时间内寻找最大长度为 n 的字符串中长度为 m 的字符串
组成字符串¶
最后，我们想对几种能组成大字符串的方法进行评论。接下来做一个学术练习，假定有一个较大的字符串 document , 我们的目标是生成一个新的字符串 letters, 该字符串仅包含原字符串的英文字母字符（ 即，将空格、数字、标点符号除去） 。我们或许会采用如下循环来 得到结果，
# WARNING: do not do this
letters = '' # start with empty string
for c in document:
if c.isalpha():
letters += c # concatenate alphabetic character
虽然上面的代码段实现了该目标，但其效率可能非常低下。因为字符串大小固定，指令 letters + = c 很可能计算串联部分 letters + c, 并把结果作为新的字符串实例且重新分配给标识符 letters 。构造新字符串所用时间与该字符串的长度成正比。假如最终结果有 n 个字符，连续串联计符所花费的时间与所谓的求和公式 1 + 2 + 3 + … + n 成正比，因此，运行时间为 Ω(\(n^2\)) 。
这类效率低的代码在 python 中很普遍，大概跟代码的自然外观有点关系，且容易对＋＝ 操作符如何与字符串连接产生误解。python 解释器后来的一些实现方法中对开发进行了最优化，能够允许这类代码的运行时间为线性，但不是所有 python 实现方法都支持。最优化如 下： 指令 letters += c 之所以会产生新的字符串实例，是因为假如程序中有另一个变量要引用原字符串， 则原字符串必须保持不变。另一方面，假如 python 知道在该问题中对该字符串没有其他引用，但通过直接改变字符串（作为一个动态数组）可以更高效地实现＋＝。当发生上述情况时， python 解释器已经为每个对象包含了所谓的引用计数器。该计数器部分用于确定某个对象是否能被垃圾回收（见 15. 1. 2 节） 。但在此情形中，计数器给出了一种方法， 用于检测是否存在对字符串的其他引用，因此，允许最优化。
保证能在线性时间内组成字符串的另一个更标准的 python 术语是使用临时表存储单个数据，然后使用字符串类的 join 方法组合最终结果。将此技巧用于我们之前例子将会如下编写：
str.join(iterable)
返回一个由 iterable 中的字符串拼接而成的字符串。 如果 iterable 中存在任何非字符串值包括
bytes对象则会引发TypeError。 调用该方法的字符串将作为元素之间的分隔。
temp = []
for c in document:
if c.isalpha():
temp.append(c)
letters = '' .join(temp)
该方法能确保运行时间为 O(n) 。首先，我们注意到连续 n 次 append 调用共需要 O(n) 的运行时间，其运行时间可以根据此操作的摊销花费定义得出。最后对 join 的调用也能保证在组合字符串的最终长度上花费的时间呈线性。
正如在上一节末尾所讨论的那样，我们使用列表推导式语法来创建临时表，而不是重复调用 append 方法，能够进一步提高实际执行速度。方案如下：
letters = ''.join([c for c in document if c.isalpha()])
还有更好的方法——我们使用生成器理解可以完全避免使用临时表：
letters = ''.join(c for c in document if c.isalpha())
5.5 使用基于数组的序列¶
5.5.1 为游戏存储高分¶
我们学习的第一个应用是为某款视频游戏存储一列高分条目。这是许多必须存储一系列对象的应用程序的代表。我们可能很容易选择为医院的病人存储记录或者登记某足球队队员的姓名。然而，这里我们将关注存储高分条目，这是一个简单且数据丰富的应用程序，足以表示一些重要的数据结构概念。
刚开始，我们考虑在对象中存储什么信息来表示高分条目。显然，信息中一定含有一个表示分数的整数，我们用_score来表示。另一个有用的信息是得分者姓名，我们用_name 表示。我们能继续增加字段表示得分的数据或者得分的游戏统计的字段。但我们忽略一些使得例子变得容易的细节。在代码段 5-7 中，我们给出一个 python 类 GameEntry，用于表示游戏条目：
class GameEntry:
"""Represents one entry of a list of high scores."""
def __init__(self, name, score):
"""Create an entry with given name and score."""
self._name = name
self._score = score
def get_name(self):
"""Return the name of the person for this entry."""
return self._name
def get_score(self):
"""Return the score of this entry."""
return self._score
def __str__(self):
"""Return string representation of the entry."""
return '({0}, {1})'.format(self._name, self._score) # e.g., '(Bob, 98)'
存储高分的类¶
为了存储一系列高分，我们编写一个类并将其命名为 Scoreboard , 一个 scoreboard 对象只能存储一定数量的高分，一旦达到存储界限，新的分数必须严格大于得分板上最低的 “最高分”才能记入 scoreboard 。理想的 scoreboard 的长度取决于游戏，可能为 10 、50 或者 500 。因为这个长度非常依赖游戏，我们将它指定为 Scoreboard 结构的参数。
在内部，我们将会使用名为_board 的 python 列表( list ) 来管理表示高分的 GameEntry 实例。因为希望 scordboard 最终能被填满，所以使初始化列表尽可能大以便能存储最多的分数，但起初将所有条目都设为 None 。最初给列表分配了最大化的容量，因此执行过程中不 再需要调整大小。当添加条目时，我们将会从列表的索引 0 开始，从最高分到最低分依次存储。图 5-18 所示即为这种数据结构的一个典型样例。
代码段 5-8 给出了 Scoreboard 类的一个完整的 python 实现方法。构造函数非常简单。下面的语旬
self._board = [None] * capacity
创建一张所需长度的列表，而所有条目都是 None 。其中还包含一个额外的实例变量 _n, 用于表示表内当前的实际条目数。为了方便，我们的类也支持__getitem__方法，此 方法通过给定的索引，使用 board[i]能检索获得一个条目（或者假如没有这样的条目就返回 None)，我们也支持简单的 __str__ 方法，该方法返回用每行一个条目表示整个 scoreboard 的字符串。
class Scoreboard:
"""Fixed-length sequence of high scores in nondecreasing order."""
def __init__(self, capacity=10):
"""Initialize scoreboard with given maximum capacity.
All entries are initially None.
"""
self._board = [None] * capacity # reserve space for future scores
self._n = 0 # number of actual entries
def __getitem__(self, k):
"""Return entry at index k."""
return self._board[k]
def __str__(self):
"""Return string representation of the high score list."""
return '\n'.join(str(self._board[j]) for j in range(self._n))
def add(self, entry):
"""Consider adding entry to high scores."""
score = entry.get_score()
# Does new entry qualify as a high score?
# answer is yes if board not full or score is higher than last entry
good = self._n < len(self._board) or score > self._board[-1].get_score()
if good:
if self._n < len(self._board): # no score drops from list
self._n += 1 # so overall number increases
# shift lower scores rightward to make room for new entry
j = self._n - 1
while j > 0 and self._board[j-1].get_score() < score:
self._board[j] = self._board[j-1] # shift entry from j-1 to j
j -= 1 # and decrement j
self._board[j] = entry # when done, add new entry
if __name__ == '__main__':
board = Scoreboard(5)
for e in (
('Rob', 750), ('Mike',1105), ('Rose', 590), ('Jill', 740),
('Jack', 510), ('Anna', 660), ('Paul', 720), ('Bob', 400),
):
ge = GameEntry(e[0], e[1])
board.add(ge)
print('After considering {0}, scoreboard is:'.format(ge))
print(board)
print()
增添一个条目¶
Scoreboard 类中最有趣的方法是 add 方法，该方法能够考虑到将新的条目添加至 scorebord 中。要记住： 每个条目不一定要绑定一个高分。假如 board 还没有满，任何一个新的条目都可以被记录。一旦 board 巳满，新的条目只有严格大于一个或多个分数时，才能被记入，特别是， scoreboard 中的最后一个条目是最低的高分。
当考虑新的分数时，我们先要确定该分数是否满足高分的条件。假如满足，若 board 未满，我们便增加有效分数的个数_n 。假如 board 已满，增添新的高分将会导致某个其他高分从 scoreboard 中被删除，因此条目的总数保持不变。
为了正确地将新条目放入列表中，最后的工作是将较低分往后移动一个位置（ 当 socreboard 已满时，最低分将会被完全删除） 。这个过程与在前面 list 类的 insert 方法的实现 方式很类似。在 scoreboard 情形中，不需要移动任何保存在数组尾部的 None 引用，因此该 过程能按图 5-19 所示的那样进行
为了完成最后的步骤，我们首先考虑索引 j = self._n - 1, 当完成此操作后，该索引指向 最后一个 GameEntry 实例。j 要么是新条目的正确索引，要么是一个或者多个暂时有更低分数的条目的索引。当循环执行到第 34 行时，只要索引 j - 1 条目的分数比新条目分数低，就把索引往右移动，j 自减 1。
5.5.2 为序列排序¶
上一节中，我们学习了一个应用程序：在序列中的给定位置增添对象，通过移动其他元素保持先前顺序不变。本节中，我们使用类似的技巧解决排序间题，即把开始元素无序的序列通过重新排序变成非递减序列。
插入排序算法¶
本书将介绍几种排序算法，其中大部分将在第 12 章中介绍。作为准备，本节将介绍一 种友好简单的排序算法——插入排序。对基于数组的序列，该算法按如下方式执行。我们从数组的第一个元素开始。一个元素本身已排序。接着我们考虑数组的下一个元素。假如它比第一个元素小，我们就把这两个数进行交换。之后我们考虑数组中的第三个元素，把它与左边前两个元素进行比较和交换，直至找到自己的位置。考虑第四个元素，把它与左边前三个元素进行比较和交换， 直至找到正确的位置。对第五、第六及其余元素继续执行上述操作， 直至整个数组被完全排序。我们可以用伪代码描述插入排序算法， 示例如代码段 5-9 所示
Algorithm InsertionSort(A): Input: An array A of n comparable elements Output: The array A with elements rearranged in nondecreasing order for k from 1 to n − 1 do Insert A[k] at its proper location within A[0], A[1], . . ., A[k]. Code Fragment 5.9: High-level description of the insertion-sort algorithm
这是对插入排序的一种简单高级的描述。假如回顾 5.5.1 节中的代码段 5-8 , 我们会看到在高分列表中插入新条目的操作与在插入排序算法中插入正被考虑的元素的操作几乎相同 （唯一不同是游戏高分从高到低已经排序） 。在代码段 5-10 中，我们给出插入排序算法的一种 python 实现方法，使用外层循环轮流考虑每个元素，内层循环移动正被考虑的元素，将其移动到其左边（已排序）子数组的合适位置。图 5-20 所示即为插入排序算法运行过程的示例。
图 5.20：在八个字符的数组上执行插入排序算法。每行对应于外循环的一次迭代，一行中序列的每个副本对应于内循环的一次迭代。 正在插入的当前元素在数组中突出显示，并显示为当前值
def insertion_sort(A):
"""Sort list of comparable elements into nondecreasing order."""
for k in range(1, len(A)): # from 1 to n-1
cur = A[k] # current element to be inserted
j = k # find correct index j for current
while j > 0 and A[j-1] > cur: # element A[j-1] must be after current
A[j] = A[j-1]
j -= 1
A[j] = cur # cur is now in the right place
插入排序的嵌套循环在最坏的情况下会导致 Ω(\(n^2\)) 的运行时间。如果数组最初是反序， 则工作量最大。另外，如果初始数组已基本排序或已完全排序，则插入排序运行时间为 O(n) ，因为内层循环迭代次数很少或完全没有迭代。
5.5.3 简单密码技术¶
字符串和列表的一个有趣应用是密码学(cryptography) ，它是一种秘密信息的科学及其应用。这一领域研究加密的方法，即将称为明文的信息转换成称为密文的加密信息。同样， 该领域也研究对应的解密方法，即将密文转变回原来的明文。
可以说最早的加密技术是凯撒密码 (Caesar cipher) ，该技术以尤利乌斯·凯撒的名字命名，凯撒使用此技术保护重要军事情报。（ 所有凯撒情报都是用拉丁语写的，当然，这使得我们大多数人都不能阅读这些情报！）凯撒密码是一种简单隐藏情报的方法，这些情报用字母表组成单词的语言编写。
凯撒密码涉及替换情报中的每一个字母，用在字母表中继该字母固定数目后的字母进行替换。因此，在英语情报中，我们可以把每个 A 都用 D 替换，每个 B 都用 E 替换，每个 C 都用 F 替换，等等，即移动三个字母。以此类推，直到用 Z 替换 W 。之后，我们将此替换模式循环，即将 X 用 A 替换， Y 用 B 替换， Z 用 C 替换
字符串和字符列表之间进行转换¶
给定的字符串是固定不变的，我们不能直接编辑实例对其加密。另外，我们的目标是产生一个新字符串。一种执行字符串转换的便捷方法是创建等效字符列表，编辑列表，然后将该列表重新组成（新）字符串。第一步可以通过把字符串作为参数传递给列表类的构造函数完成。
例如，表达式 list('bird') 会得到 ['b','i','r','d'］这样的结果。相应地，我们可以在空字符串上通过用字符列表作为参数调用 join 方法，并将该字符列表组成字符串。例如，调用 “.join(['b', 'i','r', 'd']) “ 返回字符串 'bird'
使用字符作为数组索引¶
如果我们像数组索引那样为每个字母编码，那么 A 就是 0 、B 是 1 、C 是 2, 等等，之后我们可以用 r 轮转写一个简单的公式表示凯撒密码：用字母 (i + r) mod 26 来替换每个字母 i' 这里的 mod 就是模数运算子(modulo operator)，当执行整除后返回余数。在 python 中 该运算子用 ％表示，这正是我们所需要的运算子，可以在字母表末尾处很容易地执行轮转， 因为 26 mod 26 是 0, 27 mod 26 是 1, 28 mod 26 是 2 。凯撒密码的解密算法与此相反一一 采用轮转，用每个字母前的第 r 个字母代替自己（即字母 i 被字母 (i - r) mod 26 替换） 。
我们可以用另一个字符串指明替换规则来描述转换过程。举一个具体的例子，假设正在使用一个三字符轮转的凯撒密码。我们应该提前计算出用于替换 A~Z 每个字母的字符串。比如， A 应该被 D 替换， B 被 E 替换，等等。26 个替换字母按顺序就是 " DEFGHIJKLMNOPQRSTUVWXYZABC” 。之后我们可以使用这个转换的字符串作为向导来加密情报。剩下的任务就是如何为原情报的每个字母快速地找到替换字母
幸运的是，我们可以依据字符在 Unicode 中用整数代码点表示这一事实，且拉丁字母表中大写字母的代码点是连续的（ 为简单起见，我们限制只对大写字母加密 ） 。python 支持在整数代码点和单字符字符串之间进行转换的函数。尤其是将单字符字符串作为参数传递到函 数 ord(c) 中，能得到该字节的整数代码点。相应地，将整数传入函数 chr(j)) 中能得到其所对应的单字符字符串。
在凯撒密码中，为了确定某个字节的替换字符，我们需要将字符 'A' ~ 'Z' 分别映射为 0 ~ 25 的整数。执行此变换的公式即为 j = ord(c) - ord('A') 。做一次检查，假如 c 为 'A' ，我 们得到 j = 0 。当 c = 'B' 时， 我们发现其顺序值正好比 'A' 多 1。故它们相差 1 。一般来说，由此计算得到的整数 j 能够在我们预先翻译的字符串中充当索引， 如图 5-21 所示。
代码段 5 - 11 给出了一个 python 类，可以为凯撒密码赋予任意轮转值，并且证明了此用法。运行此程序时（执行一个简单测试） ，得到的输出结果如下：
Secret: WKH HDJOH LV LQ SODB; PHHW DW MRH'V .
Message: THE EAGLE IS IN PLAY; MEET AT JOE'S .
该类的构造函数为给定值建立了加密前后的字符串。加密和解密算法就像一双手，本质上是相同的，所以我们用不公开的实例方法_transform 执行这两种算法。
class CaesarCipher:
"""Class for doing encryption and decryption using a Caesar cipher."""
def __init__(self, shift):
"""Construct Caesar cipher using given integer shift for rotation."""
encoder = [None] * 26 # temp array for encryption
decoder = [None] * 26 # temp array for decryption
for k in range(26):
encoder[k] = chr((k + shift) % 26 + ord('A'))
decoder[k] = chr((k - shift) % 26 + ord('A'))
self._forward = ''.join(encoder) # will store as string
self._backward = ''.join(decoder) # since fixed
def encrypt(self, message):
"""Return string representing encripted message."""
return self._transform(message, self._forward)
def decrypt(self, secret):
"""Return decrypted message given encrypted secret."""
return self._transform(secret, self._backward)
def _transform(self, original, code):
"""Utility to perform transformation based on given code string."""
msg = list(original)
for k in range(len(msg)):
if msg[k].isupper():
j = ord(msg[k]) - ord('A') # index from 0 to 25
msg[k] = code[j] # replace this character
return ''.join(msg)
if __name__ == '__main__':
cipher = CaesarCipher(3)
message = "THE EAGLE IS IN PLAY; MEET AT JOE'S."
coded = cipher.encrypt(message)
print('Secret: ', coded)
answer = cipher.decrypt(coded)
print('Message:', answer)
5.6 多维数据集¶
在 python 中，列表、元组和字符串是一维的。我们用单个索引便能访问序列中的每个 元素。但许多计算机应用程序都涉及多维数据集。例如，计算机图形通常用二维或三维来建模。地理信息通常表示为二维， 医学图像可以给出病人的三维扫描，公司估值通常基于大量的独立金融测试，这些均可以用多维数据来建模。二维数组有时也称为矩阵( matrix ) ，我们可以用两个索引 i 和 j 指向矩阵中的单元。第一个索引通常表示行号，第二个表示列号，并且在计算机学中，这两个索引习惯上从 0 开始。图 5-22 所示为整数数据的二维数据集。这 个数据集可以用来表示美国曼哈顿不同地区的商店数量。
在 python 中， 二维数据集通常表示为列表的列表。我们用多行列表表示二维数组， 每行本身表示一张列表。例如， 二维数据
在 python 中可以按照如下形式存储：
data = [ [22, 18, 709, 5, 33], [45, 32, 830, 120, 750], [4, 880, 45, 66, 61] ]
这样表示的好处是：我们可以很自然地使用诸如 data[1][3] 这样的语法表示 1 行 3 列的数据，比如，外表中第二个条目 data[1] 本身也是一张表，因此是可索引的。
创建多维列表¶
为了快速初始化一张一维列表， 一般使用诸如 data = [0]*n 这样的语旬来创建具有 n 个 0 的列表。在图 5-7 和图 5-8 中，我们从技术角度做了强调，这种方式创建了一张长度为 n 且所有条目都指向同一个整数实例的列表，但是这种混叠方式并没有取得多么有意义的结 果，因为在 python 中， int 类是固定不变的。
在创建列表的列表时，我们要更加小心。假如想要创建一张相当于有 r 行 c 列的二维整数列表的列表，并把所有值都初始化为 0 , 我们可能会采用如下的错误语句
data = ([0] * c) * r # Warning: this is a mistake
[0] * c) 确实创建了一张有 c 个 0 的列表，但通过将列表乘 r , 只会创建一张长度为 r*c 的一维列表，比如 [2, 4 , 6]*2 创建为 [2, 4 , 6, 2 , 4 , 6] 这样的列表。
还有一种更好一点但仍有问题的做法： 创建一张把包含 n 个 0 的列表作为自己唯一元素的列表，然后把这个列表乘以 r, 即使用如下的语句创建：
data = [ [0] * c ] * r # Warning: still a mistake
这更加接近了，因为我们实际上确实得到了一个正式的列表的列表的结构。问题却是 data 列表的 所有 r 个条目都指向了同一个实例， 该实例即为有 c 个 0 的列表。图 5-23 所示即为这种混叠方式的示例。
这确实是一个问题。赋值一个条目，例如 data[2] [0] = 100 , 将可能使得第二级列表的第一个条目指向新的值 100 。而第二级列表的那个单元也表示 data[0][0] 的值，因为第 data[0] “行” 和 data[2] “行” 指向同一个第二级列表
如图，更改 data[2][0] 的值也会同时改变 data[0][0] 的值，因为这是同一个实例的两个别名
为了能正确实例化二维列表， 我们必须确保原始列表的每个单元都能指向一个独立的第二级列表。通过运用 python 列表推导式语法能够实现实例化
data = [[0] * c for j in range(r)]
该语句产生了一个有效配置， 如图 5-24 所示。使用列表推导式语法，表达式 [0] *c 在 循环的每次执行中都会重新评估。因此，我们得到 r 的不同的第二级列表，这正是我们想要的。（我们注意到语句中的变量 j 是不相关的，仅仅需要将循环迭代 r 次。）
二维数组和位置型游戏¶
许多计算机游戏，例如策略游戏、模拟游戏或第一人称战斗游戏，都是将对象放置于二 维空间中。开发这类位置型游戏需要一种能表示二维＂边界” 的方法，在 python 中，很自然就会选择列表的列表。
三连棋游戏¶
大多数学生都知道，三连棋是在 3X3 的方格里玩的游戏。两个玩家——X 和 O——从 X 开始，轮流将他们各自的标志符号放入方格的某单元内。假如其中的任一玩家将己方符号的任意 3 个连成一行、一列或者成对角线，则该玩家胜出。
这显然不是一个复杂的位置型游戏，甚至都没太大意思，因为一个不错的玩家 O 总能打成平局。三连棋游戏的可取之处在于该游戏能作为一个不错的简单例子来展示二维数组是如何运用于位置型游戏的。开发更复杂的位置型游戏，例如西洋棋、国际象棋或者流行的模拟游戏都是基于相同的方法， 即此处论述的为三连棋游戏使用二维数组
3X3 方格的代表是字符型列表的列表 ，’ X ' 或 ' 0' 表明玩家的走法， ” 表示空位置。例如，方格样例为
内部存储为
[ [ 'O' , 'X' , 'O' ], [ '', 'X' ,'' ], ['' , 'O' , 'X' ] ]
我们编写了一个完整的 python 类，是有两个玩家的三连棋方格。该类追踪了玩家走法并且宣布赢家，但它并不执行任何策略或允许其他人和计算机对弈三连棋。该程序细节虽超出了本章范围，但仍不失为一个好的课题项目（见练习 P-8.68 ) 。
给出该类的实现方法前，在代码段 5-12 中，我们使用一个简单的测试来展示它的公开接口。
game = TicTacToe( )
# X moves: # O moves:
game.mark(1, 1); game.mark(0, 2)
game.mark(2, 2); game.mark(0, 0)
game.mark(0, 1); game.mark(2, 1)
game.mark(1, 2); game.mark(1, 0)
game.mark(2, 0)
print(game)
winner = game.winner()
if winner is None:
print( Tie )
else:
print(winner, wins )
该类的基本操作为： 一个新的游戏实例表示一个空的方格， mark(i , j) 方法为当前玩家 在指定的位置写入标号（用软件掌控轮流次序），该游戏方格能被打印并且由胜利者决定。代码段 5-13 给出了三连棋类的完整代码。mark 方法执行错误检测以确保输入索引合法、位置没有被占用，并且当玩家已赢得比赛后，双方都不可再有进一步的动作
class TicTacToe:
"""Management of a Tic-Tac-Toe game (does not do strategy)."""
def __init__(self):
"""Start a new game."""
self._board = [ [' '] * 3 for j in range(3) ]
self._player = 'X'
def mark(self, i, j):
"""Put an X or O mark at position (i,j) for next player's turn."""
if not (0 <= i <= 2 and 0 <= j <= 2):
raise ValueError('Invalid board position')
if self._board[i][j] != ' ':
raise ValueError('Board position occupied')
if self.winner() is not None:
raise ValueError('Game is already complete')
self._board[i][j] = self._player
if self._player == 'X':
self._player = 'O'
else:
self._player = 'X'
def _is_win(self, mark):
"""Check whether the board configuration is a win for the given player."""
board = self._board # local variable for shorthand
return (mark == board[0][0] == board[0][1] == board[0][2] or # row 0
mark == board[1][0] == board[1][1] == board[1][2] or # row 1
mark == board[2][0] == board[2][1] == board[2][2] or # row 2
mark == board[0][0] == board[1][0] == board[2][0] or # column 0
mark == board[0][1] == board[1][1] == board[2][1] or # column 1
mark == board[0][2] == board[1][2] == board[2][2] or # column 2
mark == board[0][0] == board[1][1] == board[2][2] or # diagonal
mark == board[0][2] == board[1][1] == board[2][0]) # rev diag
def winner(self):
"""Return mark of winning player, or None to indicate a tie."""
for mark in 'XO':
if self._is_win(mark):
return mark
return None
def __str__(self):
"""Return string representation of current game board."""
rows = ['|'.join(self._board[r]) for r in range(3)]
return '\n-----\n'.join(rows)