python的list的底层实现

如果你拿python的list实现那几种常见的排序算法，你会发现数据结构书上的一些结论并不成立，这一点与python的list底层实现有关。

现象

python中用list实现排序算法时，会发现shell排序不比插入排序快，有时甚至更慢，对一个已经基本有序的list进行插入排序并不会有明显的速度提升等异常现象。

（本文源自我本科学python时，用python实现几种基本排序算法时观察到的异常，很早之前写在onenote上，现在搬运过来）

原因

搜索之后我找到了这么一篇文章：链接。所以本质我这边算是嚼别人嚼过的东西

因为python的list的底层实现是通过一组”ob_item”指向list中的每个元素，对于ob_item的遍历的时间复杂度为O(N)，而删除、插入元素的的操作仅需要修改指针，时间复杂度为O(1)，如图所示：

为了减少内存的消耗，list是按序申请新内存块的，当ob_item的长度到达分配长度上限后，会增加一定数量的新块，同时为了避免过多的触发增加新块的操作，增加新块的数量也在递增，递增算法如下：

arguments: list object, new size
returns: 0 if OK, -1 if not
list_resize:
    new_allocated = (newsize &gt;&gt; 3) + (newsize < 9 ? 3 : 6) = 3
    new_allocated += newsize = 3 + 1 = 4
    resize ob_item (list of pointers) to size new_allocated
    return 0

即，每次增加的新块大小为： 0, 4, 8, 16, 25, 35, 46, 58, 72, 88, …

另外，当pop和remove使得目前在用的块低于已经申请的块的一半的时候，会触发块回收。

在这种实现下，list的append操作就是直接在ob_item数组后增加一个新的ob_item，然后指向其对应的对象，和标准的array的行为大致上没有区别，但对于insert, pop, remove，其实现分别如下：.

insert的实现

（上图为l.insert(1,5)的示意图）

insert操作分为三步：

• 在ob_item数组中查找到对应位置
• 添加新的ob_item项
• 创建指针指指向被添加进list的新对象

（上图还有新增新块的操作，但与insert操作不直接相关故不计入）

pop的实现

对于默认pop操作（默认删除最后一个元素），时间复杂度为O(1)；对于指定删除位置的pop操作，时间复杂度为O(N)，其中遍历操作时间复杂度为O(N)，删除元素时间复杂度为O(1)。

remove的实现

l.remove(5)的示意图

pop操作的时间复杂度为O(N)，其中遍历操作时间复杂度为O(N)，删除元素时间复杂度为O(1)。且由于其需要访问每个对象进行值比对（而不是只需要访问ob_item数组），时间级会比pop大很多。

对于排序的影响

排序算法本质上是在查找元素和移动元素，两个操作的时间复杂度都是O(N)（在计算机内存中将一个单元写入到另一个单元是有客观的时间消耗的）。如果直接用insert做插入操作实现排序算法，只剩下查找元素的时间复杂度是O(N)，插入元素是直接修改指针，时间复杂度为O(1)。

对于教科书上的插入排序来说，之所以对于已经排序完成的数组进行插入排序省时间是因为比较和移动次数都较小。shell排序同理，其通过分组的操作，使得数据初步有序，从而降减少了移动和比较的次数。

然而这两个优势在list中只剩下了比较的次数较少这一个，同时，因为读内存的速度快于写内存的速度，排序算法消耗的时间，大部分是被移动元素的操作占用了，这就使得剩下的这个优势更小了。

以上的原因导致了在list上实现的插入排序对于基本有序的list的排序没有明显优势，也导致了shell排序对于插入排序没有明显的优势。