引言
我们在使用python开发过程中，list属于使用非常广泛的数据结构。不管是自己程序存放数据，还是处理接口返回的数据，我们都更倾向于使用list。因为list用起来不仅方便，而且提供的功能较丰富。在开发中我们都知道不同的业务场景，如果背后使用的数据结构不同，处理的时间也会有本质上的差异。所以我们要剖析下list的各个方法的时间复杂度，以帮助我们在业务开发中对应该怎样用list或者是否该用list做出较优的判断。
背景知识
- 数组是一种线性表结构，其用一块连续的内存空间，来存储一组具有相同类型的数据
- 时间复杂度，也叫做渐进时间复杂度，通常用大O公式书写，表示代码的执行时间随数据规模增长的变化趋势，而非真正的执行时间。因此大O关注的是变化趋势。
上面提到的两个知识点，不熟悉的或者记得不太清楚了，可以通过google认真学习一下。
列表（list）特点
- 底层基于数组实现
我们可以看下github上python list的部分代码实现，如下：
typedef struct {
PyObject_VAR_HEAD
/* Vector of pointers to list elements. list[0] is ob_item[0], etc. */
PyObject **ob_item;
/* ob_item contains space for 'allocated' elements. The number
* currently in use is ob_size.
* Invariants:
* 0 <= ob_size <= allocated
* len(list) == ob_size
* ob_item == NULL implies ob_size == allocated == 0
* list.sort() temporarily sets allocated to -1 to detect mutations.
*
* Items must normally not be NULL, except during construction when
* the list is not yet visible outside the function that builds it.
*/
Py_ssize_t allocated;
} PyListObject;
list_resize(PyListObject *self, Py_ssize_t newsize)
{
PyObject **items;
size_t new_allocated;
Py_ssize_t allocated = self->allocated;
/* Bypass realloc() when a previous overallocation is large enough
to accommodate the newsize. If the newsize falls lower than half
the allocated size, then proceed with the realloc() to shrink the list.
*/
if (allocated >= newsize && newsize >= (allocated >> 1)) {
assert(self->ob_item != NULL || newsize == 0);
Py_SIZE(self) = newsize;
return 0;
}
/* This over-allocates proportional to the list size, making room
* for additional growth. The over-allocation is mild, but is
* enough to give linear-time amortized behavior over a long
* sequence of appends() in the presence of a poorly-performing
* system realloc().
* The growth pattern is: 0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ...
*/
new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6);
...
}
# 截取部分代码
可以看到，python list本质上是一个over-allocate的数组，啥叫over-allocate呢？就是当底层数组容量满了而需要扩充的时候，python依据规则会扩充多个位置出来。比如初始化列表array=[1, 2, 3, 4]，向其中添加元素23，此时array对应的底层数组，扩充后的容量不是5，而是8。这就是over-allocate的意义，即扩充容量的时候会多分配一些存储空间。这样做的优点当然是提高了执行效率，否则每次添加元素，都要对底层数组进行扩充，效率是很低下的。另外，当列表存储的元素在变少时，python也会及时收缩底层的数组，避免造成内存浪费。这里可以通过对列表的实践，验证扩充与收缩的过程（通过 __sizeof__()或sys.getsizeof()查看内存变化，并推算容量值）。
- 属于引用数组
python列表存储的是对象引用，而非对象本身。不管是python文档的说明还是我们开发过程中的实践，均能感知到列表存储的是对象的引用。我们可以验证一下：
>>> a = [1, 2, 3, 4]
>>> a.__sizeof__()
72
>>> b = ['hello', 'world', 'mac']
>>> b.__sizeof__()
64
>>> c = [int('10'), str(8)]
>>> c.__sizeof__()
56
>>> d = 23
>>>
>>> l = []
>>> l.__sizeof__()
40
>>> l.append(a)
>>> l
[[1, 2, 3, 4]]
>>> l.__sizeof__()
72
>>> l.append(b)
>>> l.__sizeof__()
72
>>> l.append(c)
>>> l.__sizeof__()
72
>>> l.append(d)
>>> l.__sizeof__()
72
我们知道，初始列表的底层数组容量是0，第一次会扩充为4个元素的容量，占用32个字节，每个元素占用8个，注意这里就是每个元素占用8个字节，而不是平均的结果为8个字节。如果列表中存放实际的元素，那上面实践中列表l添加完元素列表a之后，其占用的字节就不会是72了。因此列表本质上存储的是对象的引用。
列表各操作时间复杂度分析
分析python list常用操作对应的时间复杂度，这里设定列表data，内部元素个数为n。有些操作可以直接推算出结果，有些则需要通过平均时间复杂度或者是均摊时间复杂度的分析方法计算出结果，因此这些知识点，我们也是要熟悉的。开始不熟悉不用怕，用多了、分析多了自然就熟悉了。
index or index assignment
列表的索引操作，比如data[i]或data[i]=new_item，对应的时间复杂度为O(1)，即常量阶。对于一块连续的存储空间，获取某个位置的地址通过一步计算即可算出。通常的公式是i_addr = start_addr + i * unit_byte，比如一个int类型的数组，想要计算数组下标为2的元素的内存地址，此时就等于数组的起始内存地址（数组下标为0的地址）+ 2 * unit_byte，unit_byte为不同类型对应的字节数，比如int类型占用2个节点，float类型占用4个字节。因为数组存储的是一组具有相同类型的数据，unit_byte固定，因此i位置内存地址较容易算出。python列表可以存储任意类型，为啥也能通过这个公式算计算呢，本质上还是因为列表实际存储的是对象的引用，每个对象的引用占用的字节数固定，因此i_addr = start_addr + i * unit_byte公式可用。append
append(object)：向列表尾部添加元素，最好情况即列表容量足够，添加元素一步完成，对应的时间复杂度为O(1)；最坏情况即列表需要扩容，这时需要对现有元素一一遍历移动位置，此时时间复杂度为O(n)。因此最终的时间复杂度为O(1)。这是均摊计算的结果，大家可以自己推算下。看下append的代码实现：
static int
app1(PyListObject *self, PyObject *v)
{
Py_ssize_t n = PyList_GET_SIZE(self);
assert (v != NULL);
if (n == PY_SSIZE_T_MAX) {
PyErr_SetString(PyExc_OverflowError,
"cannot add more objects to list");
return -1;
}
if (list_resize(self, n+1) == -1)
return -1;
Py_INCREF(v);
PyList_SET_ITEM(self, n, v);
return 0;
}
int
PyList_Append(PyObject *op, PyObject *newitem)
{
if (PyList_Check(op) && (newitem != NULL))
return app1((PyListObject *)op, newitem);
PyErr_BadInternalCall();
return -1;
}
pop
pop([index])：删除并返回特定索引的元素，默认删除最后一个元素。默认的pop操作最好情况是底层不需要收缩数组，一步操作即可，对应的时间复杂度为O(1)；最坏的情况是删除元素后，紧接着python要执行收缩数组的操作，此时时间复杂度为O(n)；因此最终的时间复杂度为O(1)。对于删除指定索引的元素，不管这步操作是否需要收缩数组，该索引以后的数据都要向前移动位置，以确保存储空间的连续性。因此对应的时间复杂度为O(n)。insert
insert(index, object)：在指定索引前插入元素object。在第一个位置插入元素时，列表中原有的所有数据均要向后移动，在最后一个位置插入元素时，这时就不需要移动元素的操作。同时insert伴随着容量扩容的潜在操作，因此最终的时间复杂度为O(n)。del
del通常的操作是del data[i] 或者 del data[i:j]，删除元素后，涉及到i或j之后元素的向前移动的操作，同时还会伴随着数组收缩的潜在操作，因此对应的时间复杂度为O(n)。contains or in
判断一个元素是否在列表内，需要从头遍历列表，最好情况是第一个元素就是，最坏情况是最后一个元素才是，或者元素根本就不在列表中，这两种情况均会完整遍历列表元素。看下contains的实现代码:
static int
list_contains(PyListObject *a, PyObject *el)
{
Py_ssize_t i;
int cmp;
for (i = 0, cmp = 0 ; cmp == 0 && i < Py_SIZE(a); ++i)
cmp = PyObject_RichCompareBool(el, PyList_GET_ITEM(a, i),
Py_EQ);
return cmp;
}
因此，时间复杂度为O(n)。
index
index(value, [start, [stop]])：获取列表中第一次出现value的索引值；最好情况是第一个元素就是value，最坏情况是最后一个元素才是或者列表不包含这个元素，因此时间复杂度为O(n)。iteration
iteration需要遍历列表内的所有元素，因此时间复杂度为O(n)。remove
remove(value)：删除列表中第一次出现的value。首先要从头开始遍历列表，判断是否找到value值，若找到value，则紧接着将其删除，然后后续的元素向前移动。remove实现的代码如下：
static PyObject *
listremove(PyListObject *self, PyObject *v)
{
Py_ssize_t i;
for (i = 0; i < Py_SIZE(self); i++) {
int cmp = PyObject_RichCompareBool(self->ob_item[i], v, Py_EQ);
if (cmp > 0) {
if (list_ass_slice(self, i, i+1,
(PyObject *)NULL) == 0)
Py_RETURN_NONE;
return NULL;
}
else if (cmp < 0)
return NULL;
}
PyErr_SetString(PyExc_ValueError, "list.remove(x): x not in list");
return NULL;
}
如果要删除的元素在列表的第一个位置，删除之后，后续所有的元素均向前移动；若要删除的元素在最后一个位置，删除之后，不存在要移动位置的元素，但需要遍历到最后一个元素。这些操作同时伴随着底层数组收缩的潜在操作，因此最终的时间复杂度为O(n)。
- count
count(value)：获取列表中value出现的次数，这个仅需要完整遍历列表元素即可，不涉及元素移动位置的操作，因此时间复杂度为O(n)。count代码实现为：
static PyObject *
listcount(PyListObject *self, PyObject *v)
{
Py_ssize_t count = 0;
Py_ssize_t i;
for (i = 0; i < Py_SIZE(self); i++) {
int cmp = PyObject_RichCompareBool(self->ob_item[i], v, Py_EQ);
if (cmp > 0)
count++;
else if (cmp < 0)
return NULL;
}
return PyInt_FromSsize_t(count);
}
len
len(list)：获取列表内元素的个数，因为在列表实现中，其内部维护了一个Py_ssize_t类型的变量表示列表内元素的个数，因此时间复杂度为O(1)。reverse
reverse()：反转列表内的所有元素，至少需要遍历一半的元素，因此时间复杂度为O(n)。sort
sort(cmp=None, key=None, reverse=False)：对列表内的元素，依据某种策略进行排序。其时间复杂度为O(nlogn)，这里咱们先记住这个复杂度，等到后续的排序文章中再给大家做具体的分析。
通过分析可以发现，列表不太适合做元素的查找、删除、插入等操作，对应的时间复杂度为O(n)；访问某个索引的元素、尾部添加元素或删除元素这些操作比较适合做，对应的时间复杂度为O(1)。比如我们要在业务开发中，判断一个value是否在一个数据集中，如果数据集用list存储，那此时的判断操作就很耗时，如果我们用hash table（set or dict，后续也会专门写文章分析）来存储，此时的判断就能在O(1)的复杂度下完成，这样我们的程序就会有一定的提高。当然，在开发中如何有效的评估数据量也是非常重要的。
结论
上述对python list常用的操作做了具体的时间复杂度分析，知道某个方法、某个操作具体的时间复杂度之后，有助于我们在开发中合理的选择使用，防止不合理或无知的使用，造成程序运行的低效。这里有几点需要说明一下：
- 文章中python的代码基于2.7版本
- 时间复杂度包含最好、最坏、平均以及均摊情况的复杂度分析，上述分析中分别都会使用到这些方法得出结果
- 列表的每个方法，github上都有具体的实现，上述仅是对一些方法列出了具体的实现
- 对一些方法的分析，结合理论推导与具体的实践结果，分析起来会更加直观一些
好了，就写到这里了。后续在研究过程中，有什么新鲜的想法也会及时更新到这篇文章里，如果您对文章有什么不一样的看法或者是好的想法，欢迎一起交流学习。
引用
- https://github.com/python/cpython/blob/2.7/Include/listobject.h
- https://github.com/python/cpython/blob/2.7/Objects/listobject.c
- https://docs.python.org/2/c-api/list.html?highlight=list
- https://bradfieldcs.com/algos/analysis/performance-of-python-types/
- https://www.monitis.com/blog/python-performance-tips-part-1/
