python - Python 列表、访问和调整运行时的内部结构

Question

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

我 read here在 Python 中，数组访问真的很慢。然而，当我使用字典(Python 的字典应该非常快)和列表编写递归斐波那契过程的记忆化版本时，它们的时间相等。为什么是这样？

Python 元组的访问时间是否比 Python 列表快？

Answer 1

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

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

元组并不比列表快 - 它们只是底层的不可变列表 (*)。

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

---

(*) 这是 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 documentation on Time Complexity for data type operations ]