Python列表、访问和调整运行时大小的内部

Question

Python的[]是列表还是数组？

索引的访问时间是O(1)像数组还是O(n)像列表？

追加/调整O(1)是像列表一样，还是O(n)像数组，或者它是可以管理O(1)来访问和调整大小的混合体？

我read here说在Python语言中数组访问非常慢。但是，当我同时使用字典(Python的字典应该非常快)和列表编写递归fibonacci过程的记忆版本时，它们具有相同的时间。为什么会这样呢？

Python元组的访问速度是否比python列表更快？

Answer 1

Python的[]是作为数组实现的，而不是链表。虽然调整大小是O(n)，但附加到它后面的是摊销的O(1)，因为调整大小的情况很少发生。如果您不熟悉它的工作原理，请阅读此Wikipedia entry on dynamic arrays。Python的列表不会每次都扩展2倍，这要复杂一些，但扩展仍然设计为使追加摊销O(1)。

然而，在中间插入总是低效的O(n)，因为可能必须移动n项。

元组并不比列表快-它们只是隐藏在幕后的不可变的列表(*)。

关于您的字典测试:根据您的具体实现，在列表中缓存将比使用字典更快。然而，Python的字典是高度优化的，特别是对于少量的键将会有很好的性能。

(*)以下是Python 2.6中列表的"get item“C函数：

PyObject *
PyList_GetItem(PyObject *op, Py_ssize_t i)
{
    if (!PyList_Check(op)) {
        PyErr_BadInternalCall();
        return NULL;
    }
    if (i < 0 || i >= Py_SIZE(op)) {
        if (indexerr == NULL)
            indexerr = PyString_FromString(
                "list index out of range");
        PyErr_SetObject(PyExc_IndexError, indexerr);
        return NULL;
    }
    return ((PyListObject *)op) -> ob_item[i];
}

这是一个元组的：

PyObject *
PyTuple_GetItem(register PyObject *op, register Py_ssize_t i)
{
    if (!PyTuple_Check(op)) {
        PyErr_BadInternalCall();
        return NULL;
    }
    if (i < 0 || i >= Py_SIZE(op)) {
        PyErr_SetString(PyExc_IndexError, "tuple index out of range");
        return NULL;
    }
    return ((PyTupleObject *)op) -> ob_item[i];
}

如您所见，它们几乎完全相同。最后，在一些类型和边界检查之后，这只是一个简单的带有索引的指针访问。

[参考：Python documentation on Time Complexity for data type operations]

Answer 2

有一个很棒的列表here，概述了python数据类型的时间复杂性。在您的情况下，项目检索应该是O(1)时间。

Answer 3

Python的列表可以与Java的ArrayList相媲美。用于从列表和元组中获取项的access time应为O(1)。Norvig的文章指出，Python的列表与Java语言中的向量或Lisp中的可调整数组相当，您确实需要更多空间，但访问时间是O(1)。