当前位置：文江博客话题详情

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

发布于 2024-11-06 00:53:47 字数 340 浏览 7 评论 0原文

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

我在这里读到，Python 中的数组访问非常慢。然而，当我使用字典（Python 的字典应该非常快）和列表编写递归斐波那契过程的记忆版本时，它们的时间相等。这是为什么呢？

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

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

十二 2024-11-13 00:53:48

Python 的[] 是作为数组实现的，而不是链表。尽管调整大小的时间复杂度为 O(n)，但追加其大小的时间复杂度为 O(1)，因为调整大小的情况很少发生。如果您不熟悉其工作原理，请阅读有关动态数组的维基百科条目。 Python 的列表不会每次扩展 2 倍，它比这要复杂一点，但扩展仍然旨在使追加摊销 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 文档]

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.

Tuples aren't faster than lists - they're just immutable lists under the hood (*).

Regarding your dictionary test: depending on your exact implementation, caching in a list will be faster than with a dict. However, Python's dicts are highly optimized, and especially for small amounts of keys will perform great.

(*) Here's a list's "get item" C function in Python 2.6:

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];
}

And this is a tuple's:

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];
}

As you can see, they're almost exactly the same. In the end, after some type and bound checking, it's a simple pointer access with an index.

[Reference: Python documentation on Time Complexity for data type operations]

回复收藏 0 原文