用来实现Python内置列表数据类型的典型底层数据结构是什么?
发布于 2009-05-27 06:29:29
CPython:
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;
从下面的代码行可以看到,该列表被声明为指向PyObjects
的指针数组。
PyObject **ob_item;
发布于 2009-05-27 06:35:04
在Jython implementation中,它是一个ArrayList<PyObject>
。
发布于 2020-07-19 02:02:34
尽管这可能很明显,但值得一提的是,Python列表是Dynamic
数组(与Static
数组相对)。这是在求职面试问题/学术界中出现的一个重要区别。
因为数组是动态的,所以Python在声明时保留一定数量的内存,例如:
somelist = []
因为已经预留了额外的内存,所以执行somelist.append()
只会写入下一个保留的内存槽,因此大部分时间都是O(1)
。对于静态数组,通常数组已满(即如果有4个字节,则数组大小为4),并且追加将始终为O(n)
,因为它们需要保留一组全新的内存(现在可能为5个字节)并复制内容。
https://stackoverflow.com/questions/914233
复制相似问题