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

Question

今天在类里面，我们了解到从列表中检索元素在 Python 中是 O(1)。为什么会这样？假设我有一个包含四个项目的列表，例如:

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

这些项目在内存中有不同的大小。因此，不可能将 li[0] 的内存位置加上每个元素大小的三倍以获得 li[3] 的内存位置。那么解释器如何知道 li[3] 在哪里，而不必遍历列表以检索元素？

Answer 1

Python 中的列表是作为指针数组¹ 实现的。那么，当您创建列表时真正发生了什么:

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

您实际上是在像这样创建一个指针数组:

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

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

由于所有指针的大小都相同，解释器可以实际上将元素大小的 3 倍添加到 li[0] 的地址以到达指针存储在 li[3]。

---

¹ 从以下位置获取更多详细信息:the horse's mouth (CPython source code on GitHub) .