2

为什么访问被认为是常量的非同构列表中的元素需要时间，或者在 python 的情况下，非同构列表如何存储在内存中？

在同构列表的情况下，知道类型和位置，可以确定内存位置，但是如果非同构列表如此之快以至于将其视为常数时间的函数，它是如何完成的呢？

浏览此页面Python 是否使用链表作为列表？为什么插入慢？我假设它将元素存储在连续的内存位置。

4

2 回答 2

3

将列表视为对元素的引用数组。所有参考具有相同的大小；通过索引获取引用是常数时间，解除引用也是常数时间。

于 2013-09-24T14:09:42.997 回答
3

元组实际上是指向不同元素的指针数组。索引一个元组归结为索引这个指针数组（O（1））并找到我们抓取的指针指向的内容（O（1））。

您可以在tupleobject.c和中亲自看到这一点tupleobject.h。索引元组的代码是：

PyObject *
PyTuple_GetItem(PyObject *op, 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];
}

您可以看到最后一行索引了底层 C 数组：（ob_item[i]经过一些初步检查）。ob_item实际上是一个PyObject指针数组：

typedef struct {
    PyObject_VAR_HEAD
    PyObject *ob_item[1];

    /* ob_item contains space for 'ob_size' elements.
     * Items must normally not be NULL, except during construction when
     * the tuple is not yet visible outside the function that builds it.
     */
} PyTupleObject;
于 2013-09-24T14:10:34.770 回答