如何在Python中使用O(1)查找列表元素? [英] How come list element lookup is O(1) in Python?

问题描述

今天在课堂上，我们了解到在Python中从列表中检索元素是O(1).为什么会这样呢?假设我有四个项目的列表，例如:

Today in class, we learned that retrieving an element from a list is O(1) in Python. Why is this the case? Suppose I have a list of four items, for example:

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

这些项目在内存中具有不同的大小.因此，不可能获取li[0]的存储位置并添加每个元素大小的三倍来获得li[3]的存储位置.那么，解释程序如何知道li[3]在哪里而不必遍历列表以检索元素?

These items have different sizes in memory. And so it is not possible to take the memory location of li[0] and add three times the size of each element to get the memory location of li[3]. So how does the interpreter know where li[3] is without having to traverse the list in order to retrieve the element?

推荐答案

Python中的列表被实现为指针 ¹ 的数组.因此，创建列表时实际上发生了什么:

A list in Python is implemented as an array of pointers¹. So, what's really happening when you create the list:

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

实际上是在创建一个指针数组，如下所示:

is that you are actually creating an array of pointers like so:

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

每个指针指向"内存中的各个对象，因此字符串"perry"将存储在地址0xa3d25342中，数字1将存储在0x635423fa中，等等.

Each pointer "points" to the respective objects in memory, so that the string "perry" will be stored at address 0xa3d25342 and the number 1 will be stored at 0x635423fa, etc.

由于所有指针的大小相同，因此解释器可以将元素大小的3倍加到li[0]的地址上，以获取存储在li[3]处的指针.

Since all pointers are the same size, the interpreter can in fact add 3 times the size of an element to the address of li[0] to get to the pointer stored at li[3].

¹ 从以下位置获取更多详细信息:马的嘴(GitHub上的CPython源代码).

¹ Get more details from: the horse's mouth (CPython source code on GitHub).

这篇关于如何在Python中使用O(1)查找列表元素?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！