Python Foundation

《Data Structure and Algorithms in Python》阅读记录。非常好的一本书，适用于有一点Python基础后进行深入学习。

Python预备

Python是一门面向对象的语言。在Python中万物皆对象。在Python中int,bool,float,str,tuple,frozenset都是不可变的类型。

Python创建对象

看一个最简单的例子a = 1。其实它的执行过程可能和你想的有点不同。1是一种实例化的方式（这或许也是一种构造函数），它会创建一个整型对象。=用于执行赋值运算。它将整型对象的地址赋值给变量a。因此a表示的是一个实例化对象，而不是像Java中的那种基本数据类型。再比如a = a + 2，它的执行也涉及到了好多实例化过程。创建整型对象2，然后将a和2相加得到一个新的结果。由于int是不可变的类型，它不能讲这个新的结果覆盖在之前的a=1这样的对象上，而是必须得创建一个新的对象值为3，然后再把这个新的对象的地址赋值给a。之前的1此时已经没有被引用了，后续会被垃圾回收机制回收掉。

a = 1这个例子中不可变的类型是1，而不是a。a用于存储对象的地址，它可以指向任何其他的对象，但是1一经创建，它的值就无法被改变。a = 2可以成功执行是因为a指向了新的对象2。bool，float等类型也是如此。

Python常用序列简介

list是一个可变的类型，因为Python使用一个可扩容的数组来实现list，并且list中的元素是list中需要存储的对象的地址。你可以让list中的元素指向其他的对象，就像a可以指向2。这导致了list是一个可变类型。

tuple是list的不可变版本。它是一个不可变的类型，在Python中，具有自动打包元组和解包元组的机制。

str是一个不可变类型。a='aaa'创建一个对象'aaa'，底层使用连续数组来存储这个对象，然后将这个对象的地址赋值给a。同样a='bbb'是可以执行的，但是a[0]='b'是失败的。通过a[0]你想修改对象'aaa'的第0个元素，这是不被允许的。Python执行使用三个引号来表示长字符串，增加了可读性。

set是一个可变版本，它和数学中的set具有相同的性质。Python中的set也是使用哈希表实现的。只有不可变类型才可以添加到set。frozenset是set的不可变版本。

dict是Python中的一个可变类型，它用于存储键值对映射。底层使用哈希表实现。由于历史的原因，即dict出现的比set早，所以{}默认是创建一个空的dict，而如果要创建一个空的set可以使用set。

推导式。使用列表推导式创建list而不是for循环和append可以避免append时自动扩容带来的开销。

比如计算前n项的平方和，为了避免内存的开销，可以使用生成器语法来进行优化：res = sum(k*k for k in range(1, n+1))生成器语法可以避免存储中间结果带来的开销。

其他的Python基础有：控制语句，函数参数传递机制，默认参数，基本的输入输出，异常处理，迭代器和生成器。

Python中的in关键字

Python对序列类型提供了非常方便的索引的语法，比如a[1]。这种特殊的语法是通过一种特殊的方法__getitem__()实现的。Python中提供了大量的这种以双下划线开始以双下划线结束的特殊方法，这些特殊方法一般用于实现Python提供的特殊语法。__getitem__()方法还有另外一个作用：实现了__getitem__()方法的对象是可迭代的。可以使用for进行顺序迭代。

a in b_obj。in关键字首先会调用b_obj的__contains__()方法，如果没有实现__contains__()方法但实现了__getitem()__方法的话，会根据__getitem__()提供的可迭代的特性进行顺序判断。

Python中的特殊方法

Python中的特殊方法即这种以双下划线开始并以双下划线结束的特殊方法通常都提供了对应的内置函数，使用内置函数通常来说，效率会更好一些。比如：使用len()比__len__()方法性能要好一些。

Python中的序列类型

主要探索list，tuple，str序列类型

list

预备

• 这部分需要了解数组的扩容和缩容

Python使用可扩容的连续数组来实现list。在Python中万物皆对象，像a=[1, 2]这样一个简单的列表，Python会创建两个对象分别存储1,2。然后将这两个对象的地址存储在列表a中。这是Python中list的存储机制。

List支持切片操作。比如a = [1,2,3], b = a[1:]。b并不会直接复制a中的数据，而是会将a中对象的地址复制一份存储到b列表中。这样a和b是共享数据的。但是b[1] = 4操作只会修改b中的值而不会修改a中的值。如果明白了Python创建对象的机制，这看起来是很正常的。对b[1]=4，在右边，首先创建一个值为4的整型对象，然后执行赋值运算，将这个整型对象的地址赋值为b的第1个元素。这样b中的第1个元素的地址被修改了。而不是让b中第1个元素所执行的对象的值为4。

a = [0] * 8是一个常见的创建list的方法。实际上，它会创建一个整型对象0，然后让list中的8个元素都指向这个对象（存储这个对象的地址）。a[1] = 2会创建一个整型对象2，然后让list中的第1个元素指向这个整型对象。

list的效率分析：

常量时间复杂度的操作比较直观。data.count(val)和data.index(val)和val in data需要遍历整个list（平均来说而不是最好的情况）才能获取结果因此时间复杂度是O(n)。data1 + data2中，假设data1,data2的长度分别为n1, n2，这个执行会首先创建一个长度为n1 + n2的列表，然后将data1,data2中对象的地址分别复制到新的列表中。因此时间复杂度为O(n1+n2)。

图标中带a(amortized)的表示是均摊时间复杂度。data.append()操作的均摊时间复杂度为O(1)，最坏时间复杂度为O(n)。由于list的底层实现采用的是数组，在append时的开销主要来自于扩容阶段的数组的复制，在大部分情况下的操作都是常量的，从这个直觉上来理解它的均摊时间复杂度为O(1)。

data.insert()操作的开销主要有两个部分构成：1、对插入位置k后面n-k+1个元素进行后移。2、当数组大小不够的时候需要进行扩容。第一部分的时间复杂度无疑是O(n)的，第二部分的时间复杂度最坏情况为O(n)，最好情况为O(1)，均摊时间复杂度为O(1)。因此这个操作的均摊时间复杂度为O(n)。

data.pop()移除列表中的最后一个元素，直观上来看它的时间复杂度应为该O(1)，但是在移除元素的过程中涉及到数组的缩容。这个过程可以类比append的过程，它的均摊时间复杂度为O(1)，因此pop的均摊时间复杂度为O(1)。不过值得注意的是data.pop(k)的均摊时间复杂度为O(n)，这个过程涉及到将位置k之后的n-k+1个元素向前移动。这个时间复杂度可以类比insert操作。

data.remove()和pop不同，通过pop移除元素的时候使用的是索引，而通过remove移除元素的时候使用的是元素的值。remove操作需要首先找到待移除的值，然后将该值后面的元素依次向前移动，这个过程的时间复杂度为O(n)。和pop同样，当移除的元素过多的时候，就会进行数组的缩容，缩容的均摊时间复杂度为O(1)，因此remove操作的均摊时间复杂度为O(n)，最坏时间复杂度也为O(n)。

data.extend(data2)，这个过程比较复杂。存在以下情况，data中的数组足够容纳这两个list中的元素；data中的数组不足以容纳这两个list中的元素。第一种情况，data中的数组足够容纳这两个list中的元素，这个时候就不需要扩容，直接将data2中的元素复制进来即可，这种情况的时间复杂度为O(n2)。当data中的数组不足以容纳这个两个list中的元素时，这个时候就需要增加到一个足够容纳这两个list的元素的容量。注意，这里只进行一次扩容。然后分别将两个list中的元素复制到扩容的数组中。这种情况的时间复杂度为O(n1)+O(n2)。当需要添加多个元素时，使用extend的效果要好于append，extend只进行一次扩容和一次函数调用。而append有可能会进行多次扩容，并且每添加一个元素都要进行一次函数调用。因此前者避免了多次扩容带来的开销，以及多次函数调用压栈和弹栈的开销（需要明白函数调用的底层原理）。

reverse()和sort()操作没有什么值得可说的，它们的时间复杂度分析起来也非常直观。

列表推导式为什么有效

在利用列表推导式构建list的时候，它可以有效的避免频繁使用append带来的扩容以及函数调用的开销。

str

Python中使用了三种不同长度的编码来表示字符。即一个字符一个字节，一个字符两个字节，一个字符三个字节。Python并没有独自的支持单个字符的类型，而是把单个字符看成是长度为1的字符串(str)。在Python中万物皆对象，Python使用一组连续的存储单元来存储字符串，即Python底层使用字符数组来存储字符串。

str是不可变类型。这意味着不能改变某个字符串的中间某个字符或某个字串。

例子

# 将doc中的字母表字符筛选出来
# 方案0，不可以
letters = ''
for c in doc:
    if c.isalpha():
        letters += c

# 可行的方案1
letters = ''.join([c for c in doc if c.isalpha()])

# 可行的方案2
letters = ''.join(c for c in doc if c.isalpha())

必须理解方案0中的letters的执行过程。letters += c，由于字符串是不可变类型，因此这个代码在执行的时候并不是简单的给letters拼接字符。这个代码等价于letters = letters + c，letters+c是一个新创建的字符串对象，字符串底层使用数组存储，创建一个字符串对象的时间复杂度正比于字符串的长度。因此这个过程的时间复杂度为O(n)而不是O(1)。

可行的方案就是尽可能的避免这种开销，一种可以直接想到的方法就是使用列表。列表append元素的均摊时间复杂度为O(1)，同时可以使用列表推导式进行优化。这就是方案1，由于我们并不关心列表，而是只关心最终拼接的letters。因此，可以使用生成器的语法避免列表推导式创建列表带来的空间开销。这就是方案2。

Stack

Python并没有提供单独的栈类型。在Python中可以直接将list看成是一个栈，也可以通过适配器模式来设计一个新的栈类。所谓适配器模式就是使用已有的抽象数据类型来实现一些新的抽象数据类型。了解了list的细节，自然就了解了栈的细节。

带a的表示均摊时间复杂度。

Queue

预备：

• 环形数组，数组扩容和缩容

Python中同样没有支持单独的Queue类型。在Python中可以直接使用list来实现queue，采用适配器模式可以设计一个新的queue类。了解了list的细节，自然就了解了queue的细节。

实现queue的基本原理是使用环形数组。常量时间复杂度的操作理解起来非常直观。入队和出队操作涉及到数组的扩容和缩容。一般的原则是将数组的容量扩大为原来的2倍，当数组中的元素小于当前容量的1/4时，将容量缩减一半。扩容和缩容操作的时间复杂度是O(n)的，但是在入队和出队操作上的均摊时间复杂度为O(1)。

Deque

预备

• 环形数组，数组扩容和缩容

Python中collections模块提供了双端队列的实现deque。我们可以使用环形数组来实现deque。其实在queue的基础上，增加上在前端和后端添加元素和删除元素的操作即可。添加元素和删除元素的操作其实和单个queue的操作差不多。

append，extend，pop分别表示从右侧的操作，或者说是尾部的操作。

参考文献

[1] M. T. Goodrich, 《Data Structures and Algorithms in Python》, 页 770.

[2] B. Agarwal和B. Baka, Data structures and algorithms with Python, 2nd edition. Birmingham, UK: Packt Publishing, 2018.