Python内部结构列表,访问和调整运行时大小
收藏

Is Python's [] a list or an array?
Is the access time of an index O(1) like an array or O(n) like a list?
Is appending/resizing O(1) like a list or O(n) like an array, or is it a hybrid that can manage O(1) for accessing and resizing?

我在这里读到数组访问在Python中确实很慢。但是,当我使用字典(假定Python的字典确实非常快)和列表两者来编写递归斐波那契过程的记忆版本时,它们的次数相等。为什么是这样?

Python元组的访问时间比Python列表快吗?

最佳答案

Python's [] is implemented as an array, not a linked list. Although resizing is O(n), appending to it is amortized O(1), because resizes happen very rarely. If you're not familiar with how this works, read this Wikipedia entry on dynamic arrays. Python's list doesn't expand by a factor of 2 each time, it's a bit more complicated than that, but the expansions are still designed to make appending amortized O(1).

Inserting in the middle, however, is always an inefficient O(n), because n items may have to be moved.

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

关于字典测试:根据您的确切实现,列表中的缓存将比字典更快。但是,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文档]

    公众号
    关注公众号订阅更多技术干货!