Python列表的内部结构，访问与调整大小的运行时间

Question

Python中的[]是列表还是数组呢？
访问某个索引的时间是O(1)，就像数组一样，还是O(n)，就像列表那样呢？
添加元素或调整大小的时间是O(1)，就像列表，还是O(n)，就像数组，或者说它是一个混合体，既能做到O(1)的访问，又能在调整大小时也保持O(1)？

我在这里看到，Python中的数组访问速度其实很慢。不过，当我用字典（Python的字典据说非常快）和列表写一个带备忘录的递归斐波那契函数时，它们的运行时间是一样的。这是为什么呢？

Python的元组访问速度比列表快吗？

Answer 1

Python中的列表可以和Java里的ArrayList相提并论。无论是列表还是元组，获取其中一个元素的时间都是O(1)，也就是说，不管列表有多长，取出一个元素的时间都是一样的。Norvig的文章提到，Python的列表也可以和Java的Vector或者Lisp中的可调数组相比，如果你需要更多的空间，列表是个不错的选择，但获取元素的时间依然是O(1)。

Answer 2

这里有一个很棒的列表，可以在这里查看，它列出了Python数据类型的时间复杂度。对于你提到的情况，获取某个项目的时间应该是O(1)，也就是说，不管数据量有多大，取出一个项目的时间都是固定的，非常快。

Answer 3

Python中的[]实际上是用一种叫做数组的东西来实现的，而不是链表。虽然调整大小的时间复杂度是O(n)，但添加新元素的时间复杂度是摊销O(1)，因为调整大小的情况非常少。如果你对这个过程不太了解，可以看看这个维基百科关于动态数组的介绍。Python的列表并不是每次都扩大两倍，实际上比这要复杂一些，但扩展的设计还是为了让添加新元素的时间复杂度保持在摊销O(1)。

不过，在中间插入元素的时间复杂度总是O(n)，因为可能需要移动n个项目。

元组并不比列表快——它们其实就是在底层实现的不可变列表(*)。

关于你的字典测试：根据你具体的实现，使用列表进行缓存可能会比使用字典更快。不过，Python的字典经过高度优化，尤其是在键的数量很少的情况下，性能表现非常好。

---

(*) 这是Python 2.6中列表的“获取项目”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文档关于数据类型操作的时间复杂度]