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

Question

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

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].

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

Answer 2

当你说a = [...],a实际上是指向PyObject包含指向PyObjects 的指针数组的指针.

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

基本上,所有Python对象都是通过引用而不是值来访问的,甚至是整数文字2.指针系统中只有一些技巧可以保持这一切.指针具有已知大小,因此可以方便地存储在C风格的数组中.

Answer 3

简短回答:Python列表是数组.

答案很长:计算机科学术语列表通常表示单链表(在函数式编程中使用)或双向链表(在程序编程中使用).这些数据结构支持在列表的头部(功能上)或不需要搜索的任何位置(程序上)插入O(1).Python"列表"没有这些特征.相反,它支持(分期)O(1)附加在列表的末尾(如C++ std :: vector或Java ArrayList).Python列表实际上是CS术语中可调整大小的数组.

Python文档中的以下注释解释了Python``list''的一些性能特征:

也可以使用列表作为队列,其中添加的第一个元素是检索的第一个元素("先进先出"); 但是,列表不能用于此目的.虽然列表末尾的追加和弹出很快,但是从列表的开头进行插入或弹出是很慢的(因为所有其他元素都必须移动一个).