python 列表的实现探析
知其然也要知其所以然，python中的容器对象真的不多，平常我们会很心安理得的根据需求来使用对应的容器，不定长数据用 list，想去重用 set，想快速进行匹配用 dict，字符处理用 str，可为何能实现这个效果呢？比如我们用 list的时候，知道这玩意可以随意存储各种格式，存整型、浮点、字符串、甚至还可以嵌套 list等其他容器，这底层的原理到底是用数组实现的，还是用链表？比如我们的字典，底层是用数组还是其他？如果是其他如哈希表，那又怎么实现输入数据的顺序排列？这次不妨一层层剖析，推演一番。贪多嚼不烂，本次就先对 list进行分析简述
这个名字很容易和其它语言（C++、Java等）标准库中的链表混淆，不过事实上在 CPython的列表根本不是列表（这话有点绕，可能换成英文理解起来容易些：python中的list不是我们所学习的list），在CPython中，列表被实现为长度可变的数组。
从细节上看，Python中的列表是由对其它对象的引用组成的连续数组，指向这个数组的指针及其长度被保存在一个列表头结构中。这意味着，每次添加或删除一个元素时，由引用组成的数组需要该标大小（重新分配）。在实现过程中，Python在创建这些数组时采用了指数分配的方式，其结果导致每次操作不都需要改变数组的大小，但是也因为这个原因添加或取出元素的平均复杂度较低。
这个方式带来的后果是在普通链表上“代价很小”的其它一些操作在Python中计算复杂度相对过高。
[*]利用 list.insert(i,item) 方法在任意位置插入一个元素——复杂度O(N)
[*]利用 list.pop(i) 或 list.remove(value) 删除一个元素——复杂度O(N)
源码解析
让我们先看下list实现的源码，源汁源味，细细品评。我们先发现list多重继承自 MutableSequence 和 Generic。之后我们可以读到，list的相关内嵌函数的实现，如append、pop、extend、insert等其实都是通过继承来实现的，那么我们就不得不去找一下 MutableSequence 和 Generic这两个类的实现底层，也只有解答了这两个类之后，我们才能回答为何list可以实现动态添加数据，而且删除和插入的复杂度还不是那么优秀。
class list(MutableSequence, Generic):
@overload
def __init__(self) -> None: ...
@overload
def __init__(self, iterable: Iterable) -> None: ...
if sys.version_info >= (3,):
def clear(self) -> None: ...
def copy(self) -> List: ...
def append(self, object: _T) -> None: ...
def extend(self, iterable: Iterable) -> None: ...
def pop(self, index: int = ...) -> _T: ...
def index(self, object: _T, start: int = ..., stop: int = ...) -> int: ...
def count(self, object: _T) -> int: ...
def insert(self, index: int, object: _T) -> None: ...
def remove(self, object: _T) -> None: ...
def reverse(self) -> None: ...
if sys.version_info >= (3,):
def sort(self, *, key: Optional, Any]] = ..., reverse: bool = ...) -> None: ...
else:
def sort(self, cmp: Callable[, Any] = ..., key: Callable[, Any] = ..., reverse: bool = ...) -> None: ...
def __len__(self) -> int: ...
def __iter__(self) -> Iterator: ...
def __str__(self) -> str: ...
__hash__: None# type: ignore
@overload
def __getitem__(self, i: int) -> _T: ...
@overload
def __getitem__(self, s: slice) -> List: ...
@overload
def __setitem__(self, i: int, o: _T) -> None: ...
@overload
def __setitem__(self, s: slice, o: Iterable) -> None: ...
def __delitem__(self, i: Union) -> None: ...
if sys.version_info < (3,):
def __getslice__(self, start: int, stop: int) -> List: ...
def __setslice__(self, start: int, stop: int, o: Sequence) -> None: ...
def __delslice__(self, start: int, stop: int) -> None: ...
def __add__(self, x: List) -> List: ...
def __iadd__(self: _S, x: Iterable) -> _S: ...
def __mul__(self, n: int) -> List: ...
def __rmul__(self, n: int) -> List: ...
if sys.version_info >= (3,):
def __imul__(self: _S, n: int) -> _S: ...
def __contains__(self, o: object) -> bool: ...
def __reversed__(self) -> Iterator: ...
def __gt__(self, x: List) -> bool: ...
def __ge__(self, x: List) -> bool: ...
def __lt__(self, x: List) -> bool: ...
def __le__(self, x: List) -> bool: ...
MutableSequence
这个类其实是来自于 collections.abc.MutableSequence，其实也就是所谓的抽象基础类里面的可变序列的方法。
Python的序列有两种，可变序列和不可变序列并为其提供了两个基类 Sequence和 MutableSequence，这两个基类存在于内置模块 collections.abc中，与其他常见的类如 int、 list等不同，这两个基类都是抽象基类。这里涉及到一个新的概念抽象基类，什么是抽象基类呢？
对于抽象基类，目前可以不用关注太多，只需知道抽象基类是指不能实例化产生实例对象的类，后面有机会我们再专门来讨论抽象基类。
Sequence和 MutableSequence是两个抽象基类，因此这两个类都是不能实例化产生实例对象，那要 Sequence和 MutableSequence两个抽象基类还有什么作用呢？ 其实抽象基类的作用并不是实例化产生实例对象的，它的作用更多的像是定义一种规则，或者官方的说法叫做协议，这样以后我们希望创建这种类型的对象时，要求遵循这种规则或者协议。现在我们需要了解序列类型都有哪些协议，这需要学习abc模块中的 Sequence和 MutableSequence两个类。
Sequence和MutableSequence两个类的继承关系如下：
是否是通过链表结构实现的呢? 毕竟链表支持动态的调整，借助于指针可以引用不同类型的数据，比如下面的图示中的链表结构。但是这样的话使用下标索引数据的时候，需要依赖于遍历的方式查找，O(n)的时间复杂度访问效率实在是太低。
不过对于链表的使用，系统开销也较大，毕竟每个数据项除了维护本地数据指针外，还要维护一个 next指针，因此还要额外分配8字节数据，同时链表分散性使其无法像数组一样利用CPU的缓存来高效的执行数据读写。
实现的细节可以从其Python的源码中找到， 定义如下：
typedef struct {
PyObject_VAR_HEAD
PyObject **ob_item;
Py_ssize_t allocated;
} PyListObject; 内部list的实现的是一个C结构体，该结构体中的 ob_item是一个指针数组，存储了所有对象的指针数据， allocated是已分配内存的数量,PyObject_VAR_HEAD是一个宏扩展包含了更多扩展属性用于管理数组，比如引用计数以及数组大小等内容。
动态数组
既然是一个动态数组，则必然会面临一个问题，即如何进行容量的管理，大部分的程序语言对于此类结构使用动态调整策略，也就是当存储容量达到一定阈值的时候，扩展容量，当存储容量低于一定的阈值的时候，缩减容量。道理很简单，不过实施起来可没那么容易，什么时候扩容，扩多少，什么时候执行回收，每次又要回收多少空闲容量，这些都是在实现过程中需要明确的问题。
对于Python中list的动态调整规则程序中定义如下：当追加数据容量已满的时候，通过下面的方式计算再次分配的空间大小，创建新的数组，并将所有数据复制到新的数组中。这是一种相对数据增速较慢的策略，回收的时候则当容量空闲一半的时候执行策略，获取新的缩减后容量大小。其实这个方式就很像TCP的滑动窗口的机制
new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6);
new_allocated += newsize
//0, 4, 8, 16, 25, 35, 46, 58, 72, 88, … 假如我们使用一种最简单的策略：超出容量加倍，低于一半容量减倍。这种策略会有什么问题呢？设想一下当我们在容量已满的时候进行一次插入，随即删除该元素，交替执行多次，那数组数据岂不是会不断的被整体复制和回收，已经无性能可言了。
append
接下来，我们来看下list数据结构的几个常见操作。首先是在list上执行append的操作， 该函数将元素添加到list的尾部。注意这里是指针数据被追加到尾部，而不是实际元素。
test = list()
test.append("hello yerik") 向列表添加字符串：test.append("hello yerik") 时发生了什么？实际上是调用了底层的 C 函数 app1()。
arguments: list object, new element
returns: 0 if OK, -1 if not
app1:
n = size of list
call list_resize() to resize the list to size n+1 = 0 + 1 = 1
list = list = new element
return 0 对于一个空的list，此时数组的大小为0，为了能够插入元素，我们需要对数组进行扩容，按照上面的计算公式进行调整大小。比如这时候只有一个元素，那么newsize = 1, 计算的new\_allocated = 3 + 1 = 4 ， 成功插入元素后，直到插入第五元素之前我们都不需要重新分配新的空间，从而避免频繁调用 list_resize() 函数，提升程序性能。
insert
在列表偏移量 2 的位置插入新元素，整数 5：test.insert(1,2.33333333)，内部调用ins1() 函数。
arguments: list object, where, new element
returns: 0 if OK, -1 if not
ins1:
resize list to size n+1 = 5 -> 4 more slots will be allocated
starting at the last element up to the offset where, right shift each element
set new element at offset where
return 0 python实现的insert函数接收两个参数，第一个是指定插入的位置，第二个为元素对象。中间插入会导致该位置后面的元素进行移位操作，由于是存储的指针因此实际的元素不需要进行位移，只需要位移其指针即可。
>>> test.insert(2,2.33333333)
>>> test
['hello yerik', 520, 2.33333333, {}, [], 'abc']
pop的操作也是需要进行检查缩小，因此也是导致复杂度为O(n)
Remove
remove函数会指定删除的元素，而该元素可以在列表中的任意位置。因此每次执行remove都必须先依次遍历数据项，进行匹配，直到找到对应的元素位置。执行删除可能会导致部分元素的迁移。Remove操作的整体时间复杂度为O(n)。
页:
[1]