python - 松散类型的语言如何为数组提供恒定的查找时间？

Question

如果我在 C 中有一个长度为 10 的整数数组“arr”，要查找 arr[5]，程序只需将 20 添加到当前指针位置并检索我的值(常数时间)。

但是如果数组是松散类型的(python/javascript 列表)，指针如何在常数时间内知道元素在哪里？因为它不能再假定每个元素都是固定字节。

Answer 1

您可以查看 Python 的源代码 - listobject.h :

typedef struct {
    PyObject_VAR_HEAD
    /* Vector of pointers to list elements.  list[0] is ob_item[0], etc. */
    PyObject **ob_item;

    /* ob_item contains space for 'allocated' elements.  The number
     * currently in use is ob_size.
     * Invariants:
     *     0 <= ob_size <= allocated
     *     len(list) == ob_size
     *     ob_item == NULL implies ob_size == allocated == 0
     * list.sort() temporarily sets allocated to -1 to detect mutations.
     *
     * Items must normally not be NULL, except during construction when
     * the list is not yet visible outside the function that builds it.
     */
    Py_ssize_t allocated;
} PyListObject;

我们在这里可以看到，Python 的list 只是一个指向PyObject 的指针数组。因此，要访问第 5 个元素，我们只需要采用 ob_item[5]，它只会将指针 ob_item 的值加 20 (40)。

您可以在 listobject.c 中查看实际代码:

static PyObject *
list_item(PyListObject *a, Py_ssize_t i)
{
    ...
    Py_INCREF(a->ob_item[i]);
    return a->ob_item[i];
}