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

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

  • 你用过 list 对象吗?

  • list 对象都支持哪些操作?时间复杂度、空间复杂度分别是多少?

  • 试分析 appendinsert 这两个方法的时间复杂度?

  • 头部追加性能较差,如何解决?

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

基本用法

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

# 新建一个列表
>>> 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 中:

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 ,动态数组当前保存元素个数,即列表 长度 ;

../../_images/f6cb9818029326644741c913f7be0a33.svg

尾部操作

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

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

../../_images/36b5d1f8582bd6f6ba0f3574b2adc4bd.svg

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

点击 更多章节,获取更多细节!

更多章节

洞悉 Python 虚拟机运行机制,探索高效程序设计之道!

到底如何才能提升我的 Python 开发水平,向更高一级的岗位迈进? 如果你有这些问题或者疑惑,请订阅我们的专栏,阅读更多章节:

https://cdn.fasionchan.com/python-source-course-qrcode.png

附录

订阅更新,获取更多学习资料,请关注我们的 微信公众号

微信搜索:小菜学编程

创作不易,如果觉得我们写得还行,就请我们喝杯咖啡吧😋

微信搜索:小菜学编程