Python list 底层实现

柔情只为你懂 2022-04-18 00:56 357阅读 0赞

本文将介绍列表在 CPython中的实现，因为毕竟Cpython 又是 Python 最为常用的实现。

Python 中的列表非常强大，看看它的内部实现机制是怎么样的，一定非常有趣。

下面是一段 Python 脚本，在列表中添加几个整数，然后打印列表。

Python

<table> 
 <tbody> 
 <tr> 
 <td> 1 2 3 4 5 6 7 8 9 10 11 12 </td> 
 <td> &gt;&gt;&gt; l = [] &gt;&gt;&gt; l.append(1) &gt;&gt;&gt; l.append(2) &gt;&gt;&gt; l.append(3) &gt;&gt;&gt; l [1, 2, 3] &gt;&gt;&gt; for e in l: ...&nbsp;&nbsp; print e ... 1 2 3 </td> 
 </tr> 
 </tbody> 
</table>

可以发现，列表是一个迭代器。

## 列表对象的 C 语言结构体 ##

Cpython 中的列表实现类似于下面的 C 结构体。ob\_item 是指向列表对象的指针数组。allocated 是申请内存的槽的个数。

Python

<table> 
 <tbody> 
 <tr> 
 <td> 1 2 3 4 5 </td> 
 <td> typedef struct { &nbsp;&nbsp;&nbsp;&nbsp;PyObject_VAR_HEAD &nbsp;&nbsp;&nbsp;&nbsp;PyObject **ob_item; &nbsp;&nbsp;&nbsp;&nbsp;Py_ssize_t allocated; } PyListObject; </td> 
 </tr> 
 </tbody> 
</table>

## 列表初始化 ##

看看初始化一个空列表的时候发生了什么，例如：l = \[\]。

Python

<table> 
 <tbody> 
 <tr> 
 <td> 1 2 3 4 5 6 7 8 9 </td> 
 <td> arguments: size of the list = 0 returns: list object = [] PyListNew: &nbsp;&nbsp;&nbsp;&nbsp;nbytes = size * size of global Python object = 0 &nbsp;&nbsp;&nbsp;&nbsp;allocate new list object &nbsp;&nbsp;&nbsp;&nbsp;allocate list of pointers (ob_item) of size nbytes = 0 &nbsp;&nbsp;&nbsp;&nbsp;clear ob_item &nbsp;&nbsp;&nbsp;&nbsp;set list's allocated var to 0 = 0 slots &nbsp;&nbsp;&nbsp;&nbsp;return list object </td> 
 </tr> 
 </tbody> 
</table>

要分清列表大小和分配的槽大小，这很重要。列表的大小和 len(l) 的大小相同。分配槽的大小是指已经在内存中分配了的槽空间数。通常分配的槽的大小要大于列表大小，这是为了避免每次列表添加元素的时候都调用分配内存的函数。下面会具体介绍。

## Append 操作 ##

向列表添加一个整数：l.append(1) 时发生了什么？调用了底层的 C 函数 app1()。

Python

<table> 
 <tbody> 
 <tr> 
 <td> 1 2 3 4 5 6 7 </td> 
 <td> arguments: list object, new element returns: 0 if OK, -1 if not app1: &nbsp;&nbsp;&nbsp;&nbsp;n = size of list &nbsp;&nbsp;&nbsp;&nbsp;call list_resize() to resize the list to size n+1 = 0 + 1 = 1 &nbsp;&nbsp;&nbsp;&nbsp;list[n] = list[0] = new element &nbsp;&nbsp;&nbsp;&nbsp;return 0 </td> 
 </tr> 
 </tbody> 
</table>

下面是 list\_resize() 函数。它会多申请一些内存，避免频繁调用 list\_resize() 函数。列表的增长模式为：0，4，8，16，25，35，46，58，72，88……

Python

<table> 
 <tbody> 
 <tr> 
 <td> 1 2 3 4 5 6 7 </td> 
 <td> arguments: list object, new size returns: 0 if OK, -1 if not list_resize: &nbsp;&nbsp;&nbsp;&nbsp;new_allocated = (newsize &gt;&gt; 3) + (newsize &lt; 9 ? 3 : 6) = 3 &nbsp;&nbsp;&nbsp;&nbsp;new_allocated += newsize = 3 + 1 = 4 &nbsp;&nbsp;&nbsp;&nbsp;resize ob_item (list of pointers) to size new_allocated &nbsp;&nbsp;&nbsp;&nbsp;return 0 </td> 
 </tr> 
 </tbody> 
</table>

现在分配了 4 个用来装列表元素的槽空间，并且第一个空间中为整数 1。如下图显示 l\[0\] 指向我们新添加的整数对象。虚线的方框表示已经分配但没有使用的槽空间。

列表追加元素操作的平均复杂度为 O(1)。

![61203d71gw1ex3418lleoj204h05twef.jpg][]

继续添加新的元素：l.append(2)。调用 list\_resize 函数，参数为 n+1 = 2， 但是因为已经申请了 4 个槽空间，所以不需要再申请内存空间。再添加两个整数的情况也是一样的：l.append(3)，l.append(4)。下图显示了我们现在的情况。

![61203d71gw1ex3418cf9uj204h07gjrf.jpg][]

## Insert 操作 ##

在列表偏移量 1 的位置插入新元素，整数 5：l.insert(1,5)，内部调用ins1() 函数。

Python

<table> 
 <tbody> 
 <tr> 
 <td> 1 2 3 4 5 6 7 </td> 
 <td> arguments: list object, where, new element returns: 0 if OK, -1 if not ins1: &nbsp;&nbsp;&nbsp;&nbsp;resize list to size n+1 = 5 -&gt; 4 more slots will be allocated &nbsp;&nbsp;&nbsp;&nbsp;starting at the last element up to the offset where, right shift each element &nbsp;&nbsp;&nbsp;&nbsp;set new element at offset where &nbsp;&nbsp;&nbsp;&nbsp;return 0 </td> 
 </tr> 
 </tbody> 
</table>

![61203d71gw1ex34198im9j20ht0ad0tn.jpg][]

虚线的方框依旧表示已经分配但没有使用的槽空间。现在分配了 8 个槽空间，但是列表的大小却只是 5。

列表插入操作的平均复杂度为 O(n)。

## Pop 操作 ##

取出列表最后一个元素 即l.pop()，调用了 listpop() 函数。在 listpop() 函数中会调用 list\_resize 函数，如果取出元素后列表的大小小于分配的槽空间数的一半，将会缩减列表的大小。

Python

<table> 
 <tbody> 
 <tr> 
 <td> 1 2 3 4 5 6 7 8 </td> 
 <td> arguments: list object returns: element popped listpop: &nbsp;&nbsp;&nbsp;&nbsp;if list empty: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return null &nbsp;&nbsp;&nbsp;&nbsp;resize list with size 5 - 1 = 4. 4 is not less than 8/2 so no shrinkage &nbsp;&nbsp;&nbsp;&nbsp;set list object size to 4 &nbsp;&nbsp;&nbsp;&nbsp;return last element </td> 
 </tr> 
 </tbody> 
</table>

列表 pop 操作的平均复杂度为 O(1)。

![61203d71gw1ex3419wrvaj20fg0adwf9.jpg][]

可以看到 pop 操作后槽空间 4 依然指向原先的整数对象，但是最为关键的是现在列表的大小已经变为 4。

继续 pop 一个元素。在 list\_resize() 函数中，size – 1 = 4 – 1 = 3 已经小于所分配的槽空间大小的一半，所以缩减分配的槽空间为 6，同时现在列表的大小为 3。

可以看到槽空间 3 和 4 依然指向原先的整数，但是现在列表的大小已经变为 3。

![61203d71gw1ex3419ln7uj20fc0aa3zb.jpg][]

## Remove 操作 ##

Python 的列表对象有个方法，删除指定的元素： l.remove(5)。底层调用 listremove() 函数。

Python

<table> 
 <tbody> 
 <tr> 
 <td> 1 2 3 4 5 6 7 8 </td> 
 <td> arguments: list object, element to remove returns none if OK, null if not listremove: &nbsp;&nbsp;&nbsp;&nbsp;loop through each list element: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if correct element: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;slice list between element's slot and element's slot + 1 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return none &nbsp;&nbsp;&nbsp;&nbsp;return null </td> 
 </tr> 
 </tbody> 
</table>

为了做列表的切片并且删除元素，调用了 list\_ass\_slice() 函数，它的实现方法比较有趣。我们在删除列表位置 1 的元素 5 的时候，低位的偏移量为 1 同时高位的偏移量为 2.

Python

<table> 
 <tbody> 
 <tr> 
 <td> 1 2 3 4 5 6 7 </td> 
 <td> arguments: list object, low offset, high offset returns: 0 if OK list_ass_slice: &nbsp;&nbsp;&nbsp;&nbsp;copy integer 5 to recycle list to dereference it &nbsp;&nbsp;&nbsp;&nbsp;shift elements from slot 2 to slot 1 &nbsp;&nbsp;&nbsp;&nbsp;resize list to 5 slots &nbsp;&nbsp;&nbsp;&nbsp;return 0 </td> 
 </tr> 
 </tbody> 
</table>

列表 remove 操作的复杂度为 O(n)。

![61203d71gw1ex341ajn3fj20c9096wf2.jpg][]

[61203d71gw1ex3418lleoj204h05twef.jpg]: /images/20220418/ef54d6f6fe614beb85569c2915588480.png
[61203d71gw1ex3418cf9uj204h07gjrf.jpg]: /images/20220418/71bbbf0bae144aaba240c78d434c1c42.png
[61203d71gw1ex34198im9j20ht0ad0tn.jpg]: /images/20220418/b89d15174b3047dfa1eeaf3cf281f7b6.png
[61203d71gw1ex3419wrvaj20fg0adwf9.jpg]: /images/20220418/8a1c2901d1384742a0030d1a41df7e43.png
[61203d71gw1ex3419ln7uj20fc0aa3zb.jpg]: /images/20220418/5877eebfee0c4f949bc68d4896a23c44.png
[61203d71gw1ex341ajn3fj20c9096wf2.jpg]: /images/20220418/b23e792ba61a449b82c35aef24464828.png