list 对象,容量自适应的数组式容器

不积跬步,无以至千里;不积小流,无以成江海。

—— 战国·荀子·《劝学》

笔者经常在面试中与候选人探讨 Python 内置容器对象, list 作为最常用容器中的一员,肯定少不了它:

  • 你用过 list 对象吗?
  • list 对象都支持哪些操作?时间复杂度、空间复杂度分别是多少?
  • 试分析 appendinsert 这两个方法的时间复杂度?
  • 头部追加性能较差,如何解决?

list 对象的基本用法和技术原理,每个 Python 开发工程师都必须掌握,但不少候选人对此却只是一知半解。本节,我们一起查缺补漏,力求彻底掌握 list 对象,完美解答面试官针对 list 对象的灵魂之问。

基本用法

我们先来回顾一下 list 对象的基本操作:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
# 新建一个列表
>>> l = [1, 2, 3]
>>> l
[1, 2, 3]

# 向尾部追加元素,列表对象视情况自动扩容
>>> l.append(4)
>>> l
[1, 2, 3, 4]

# 从尾部弹出元素,列表对象视情况自动缩容
>>> l.pop()
4
>>> l
[1, 2, 3]

# 向头部插入元素,该操作需要挪动后面的元素,谨慎使用!
>>> l.insert(0, 4)
>>> l
[4, 1, 2, 3]

# 从头部弹出元素,该操作需要挪动后面的元素,谨慎使用!
>>> l.pop(0)
4
>>> l
[1, 2, 3]

# 查找元素第一次出现位置的下标
>>> l.index(2)
1

# 用一个可迭代对象扩展列表——元素逐一追加到尾部
>>> l.extend([1, 2])
>>> l
[1, 2, 3, 1, 2]

# 计算元素出现的个数
>>> l.count(1)
2
>>> l.count(3)
1

# 将列表反转
>>> l.reverse()
>>> l
[2, 1, 3, 2, 1]

# 将列表清空
>>> l.clear()
>>> l
[]

一个合格的 Python 开发工程师,除了必须熟练掌握 list 对象的基本操作,还需要对每个操作的 实现原理 及对应的 时间复杂度 、 空间复杂度 有准确的认识。列表操作总体比较简单,但有个操作特别容易被误用:

  • insert 方法向头部追加元素时需要挪动整个列表,时间复杂度是 $O(n)$ ,性能极差,需谨慎使用;
  • append 方法向尾部追加元素时,无需挪动任何元素,时间复杂度是 $O(1)$ ;
  • pop 方法从头部弹出元素时也需要挪动整个列表,时间复杂度是 $O(n)$ ,同样需谨慎使用;
  • pop 方法从尾部弹出元素时,无需挪动任何元素,时间复杂度是 $O(1)$ ;

由此可见,对列表头部和尾部进行操作,性能有天壤之别。后续我们将一起探索 list 对象内部结构,从中寻找造成这种现象的原因。此外, list 对象还可根据元素个数 自动扩缩容 ,其中秘密也将一一揭晓。

内部结构

list 对象在 Python 内部,由 PyListObject 结构体表示,定义于头文件 Include/listobject.h 中:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
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 对象是一种 变长对象 ,因此包含变长对象公共头部。除了公共头部, list 内部维护了一个动态数组,而数组则依次保存元素对象的指针:

  • ob_item ,指向动态数组的指针,动态数组保存元素对象的指针;
  • allocated ,动态数组长度,即列表 容量 ;
  • ob_size ,动态数组当前保存元素个数,即列表 长度 ;

尾部操作

在列表对象尾部增删元素,可快速完成,无须挪动其他元素。

假设列表元素 l 内部数组长度为 5 ,以及保存 3 个元素,分别是: 1 、 2 、 3 。当我们调用 append 方法向尾部追加元素时,由于内部数组还有未用满,只需将新元素保存于数组下一可用位置并更新 ob_size 字段:

因此,大多数情况下, append 方法性能都足够好,时间复杂度是 $O(1)$ 。

list 对象除了尾部操作外,还有 动态扩容头部操作元素 以及 浅拷贝 等常用方法,这些你又掌握了多少呢?点击 阅读原文,获取更多细节!

【Python源码剖析】系列文章首发于公众号【小菜学编程】,敬请关注:

【Python源码剖析】系列文章首发于公众号【小菜学编程】,敬请关注: