Python内置列表数据类型通常使用什么底层数据结构实现?
答案:Python的内置列表数据类型通常使用动态数组作为其底层数据结构来实现。
答案:Python的内置列表数据类型通常使用动态数组作为其底层数据结构来实现。
列表对象作为数组实现。它们被优化用于快速的固定长度操作,并且在pop(0)和insert(0, v)操作中产生O(n)的内存移动代价,这些操作会改变底层数据表示的大小和位置。
另请参阅: http://docs.python.org/library/collections.html#collections.deque
顺便说一句,我觉得有趣的是Python数据结构教程推荐使用pop(0)模拟队列,但没有提到O(n)或deque选项。
http://docs.python.org/tutorial/datastructures.html#using-lists-as-queues
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;
somelist = []
somelist.append()
只需写入下一个预留的内存槽,因此大部分时间都是 O(1)
。对于静态数组,通常情况下数组已满(例如,如果有4个字节,则数组大小为4),添加操作总是需要预留一组全新的内存空间(现在可能是5个字节),并将内容复制过去,因此其时间复杂度通常为 O(n)
。