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

Question

Python []是列表还是数组？
索引O(1)的访问时间是否像数组一样,O(n)是否像列表一样？
是将O(1)像列表一样追加/调整大小,还是像数组一样调整O(n),还是可以管理O(1)来访问和调整大小？

我在这里读到 Python中的数组访问速度非常慢.然而,当我使用字典(Python的字典假设非常快)和列表编写了一个递归的fibonacci过程的memoized版本时,它们有相同的时间.为什么是这样？

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

Answer 1

Python []是作为数组实现的,而不是链表.虽然调整大小是O​​(n),但是附加到它是分摊O(1),因为调整大小很少发生.如果您不熟悉其工作原理,请阅读有关动态数组的Wikipedia条目.Python的列表每次都不会扩展2倍,它比这复杂一点,但扩展仍然设计为追加摊销的O(1).

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

元组并不比列表快 - 它们只是引擎盖下的不可变列表(*).

关于你的字典测试:根据你的确切实现,列表中的缓存比使用字典更快.但是,Python的dicts是高度优化的,特别是对于少量的键,性能会很好.

(*)这是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文档 ]

Answer 2

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