Python中为什么列表元素查找是O(1)的？

Question

今天在课上，我们学习了在Python中从列表中检索一个元素的时间复杂度是O(1)。为什么会这样呢？假设我有一个包含四个元素的列表，例如：

li = ["perry", 1, 23.5, "s"]

这些项目在内存中具有不同的大小。因此，无法通过获取li[0]的内存位置并加上每个元素大小的三倍来获取li[3]的内存位置。那么解释器如何知道li[3]在哪里，而无需遍历列表以检索元素？

- Teererai Marange

---

你觉得数组是线性分配的还是一个指针列表。- [我对你的个人介绍感到困惑] - Morrison Chang

不要混淆项的“访问（access）”，它是“O(1)”的，与项的“查找/搜索（lookup / search）”不同，后者是“O(n)” 的。 - Mike Scotty

相关阅读材料：Python列表的实现，Python列表是如何实现的？，Python列表的底层数据结构是什么？。 - Warren Weckesser

在两个不同的 SE 网站上询问同一个问题（当答案将在相同的上下文中）是不好的。 - rus9384

已在计算机科学交叉发布（在我看来，这是不相关的）。请不要在多个Stack Exchange网站上发布相同的问题。这会分散答案并浪费人们的时间，因为他们会花费精力回答已经在其他地方有答案的问题。 - David Richerby

Answer 1

在Python中，列表被实现为指针数组¹。因此，在创建列表时实际发生的情况是什么：

["perry", 1, 23.5, "s"]

这意味着您实际上正在创建一个指针数组，如下所示：

[0xa3d25342, 0x635423fa, 0xff243546, 0x2545fade]

每个指针“指向”内存中的相应对象，因此字符串"perry"将存储在地址0xa3d25342处，而数字1将存储在0x635423fa等位置。

由于所有指针都具有相同的大小，因此解释器实际上可以将一个元素的大小加三次到li[0]的地址上，以到达存储在li[3]中的指针。

---

¹ 从CPython源代码（GitHub）获取更多详细信息。

- DJG

---

@DmitryVerhoturov 说得对，但这对于这个回答没有实际影响。引用是引用计数的，参考 https://docs.python.org/3/c-api/structures.html#c.PyVarObject - pipe

在我所了解的每种语言中，引用都是以指针形式实现的。虽然语义可能略有不同（例如内存管理差异或C++中的引用是不可变的），但最终它们仍然是指针。 - Frax

@TLW 我以前没有见过这些。你在哪里找到它们的？ - Cort Ammon

@Brian 啊，这样说起来就有道理了。如果我可以进一步解释一下，对于像我一样好奇的人来说，这些数字对于在芯片内部进行组合逻辑的固件设计师非常有用。大O分析总是针对某个抽象机器进行的，而当你在做固件时，将时间建模为“门深度”或“线距离”是合理的。对于任何做软件开发的人（尤其是Python和其他解释型语言），基于一个访问内存需要固定周期数的抽象机器进行大O分析更有用，因此得到了O(1)。 - Cort Ammon

简洁对于那些永远不会涉及到操作超出 Exabyte 级别的工作集，并且在简化计算模型方面 O(n) 和 O(n log n) 算法之间存在重大性能差异的开发人员来说是很重要的。简化的模型可以很好地聚焦于算法最重要的方面。 - Cort Ammon

Answer 2

当你使用a = [...]时，a实际上是一个指向包含指向PyObject的指针数组的PyObject的指针。

当你要求a[2]时，解释器首先跟随指向列表的PyObject的指针，然后将2添加到其中的数组地址，然后返回该指针。如果你请求a[0]或a[9999]也会发生同样的情况。

基本上，所有Python对象都是通过引用而不是值访问的，即使是像2这样的整数字面量也是如此。只是在指针系统中有一些技巧，以保持效率。并且指针具有已知的大小，因此可以方便地存储在C风格的数组中。

- Draconis

---

“Terp”是一个俚语词汇，它意味着“翻译员”，特别是在口语和方言中使用。 - hkBst

@hkBst 我推断它是“解释器”的缩写。 - Mario Carneiro

Answer 3

简短回答：Python列表是数组。

长篇回答：计算机科学中的术语“列表”通常指单向链表（用于函数式编程）或双向链表（用于过程式编程）。这些数据结构支持在列表头部（函数式地）或不需要搜索的任何位置（过程性地）进行O(1)插入。 Python“list”没有这些特征。相反，它支持在列表末尾进行（平摊后的）O(1)添加（类似于C++ std::vector或Java ArrayList）。从计算机科学的角度来看，Python列表实际上是可调整大小的数组。

下面的评论来自Python文档解释了Python“lists”的一些性能特点：

还可以将列表用作队列，其中添加的第一个元素是检索到的第一个元素（“先进先出”）；但是，列表对于此目的并不高效。虽然从列表末尾进行的附加和弹出很快，但从列表开头进行插入或弹出很慢（因为所有其他元素都必须向前移动一个）。

- hkBst

---

我从未听说过单向链表与函数式编程有特定的关联，或双向链表与过程式编程有特定的关联。这两种类型的链表都是有效的，并且在编程范式（以及其他编程范式）中都有它们的用例。你能支持这个说法吗？我觉得这相当可疑。 - KRyan

@KRyan 我相信Lisp、Haskell和Ocaml通常都使用单向链表，特别是在语言中更方便的原语。特别是Lisp有很多简写，比如car/cdr用于获取列表元素的各个部分。 当然它们也被广泛应用于其他地方，但是Lisp和函数式编程公司经常更加重视它们。例如，C++的list是一个双向链表，只有最近才有了一个单向链表(forward_list)。 - violet_white

这是一个很好的回答，但我同意关于函数式语言和过程式语言中列表实现的说法似乎太笼统了。在高级语言中，抽象列表数据类型是作为数组还是链表实现并不是语言规范的一部分，对吧？我想可能可以制作一个Lisp运行时，在其中将列表实现为数组，就像在cpython中一样？ - Håken Lid

@HåkenLid：性能特征通常是数据类型规范的一部分，尤其是对于更注重性能的语言。例如参见有关C++的此问答。我不知道Python是否有这样一个明确的列表，但您可以从标准“list”类型公开的接口中获得提示：有append和extend，但没有prepend/cons。 - hkBst

@HåkenLid：当文档没有提及时，CPython实现通常被视为Python的事实标准，尽管显然也会讨论其他列表实现。 (https://www.python.org/dev/peps/pep-3128/) - hkBst