Why is time taken to access an element in a non-homogeneous list considered as constant

Question

Why is time taken to access an element in a non-homogeneous list considered as constant or How is a non-homogeneous list stored in memory in case of python?

In case of a homogeneous list, knowing the type and position, the memory location can be determined but how is it done in case of a non homogeneous list so fast as to consider it as a function of constant time?

Going through this page Does Python use linked lists for lists? Why is inserting slow? I assume it stores elements in contiguous memory locations.

Each object in Python has overhead. This describes information necessary to make use of the object. The actual "data" of that doesn't need to be stored in that "header". So, a list contains just a list of references... — Jon Clements, Sep 24 '13 at 14:10
@DavidHeffernan: small note: Python `list`s are implemented as _dynamic_ arrays — inspectorG4dget, Sep 24 '13 at 14:18
@inspectorG4dget They are arrays in the CS sense. Random access, integer indices, contiguous indices. — David Heffernan, Sep 24 '13 at 14:20
@DavidHeffernan: fair enough. I didn't know you meant "in the CS sense" — inspectorG4dget, Sep 24 '13 at 14:21

score 3 · Answer 1 · answered Sep 24 '13 at 14:09

3

Think of a list as an array of references to elements. All references have the same size; getting the reference by index is constant time, and dereferencing it is also constant time.

answered Sep 24 '13 at 14:09

NPE

486,780
108
951
1,012

Thanks, can I ask what is 'dereferencing'? – aste123 Sep 24 '13 at 14:13
@aste123: Following the reference to get to the actual object. – NPE Sep 24 '13 at 14:14

arshajii · Answer 2 · 2013-09-24T14:26:07.783

A tuple is really an array of pointers to the different elements. What indexing a tuple comes down to is indexing this array of pointers (O(1)) and finding what the pointer we grab points to (O(1)).

You can see this for yourself in tupleobject.c and tupleobject.h. The code for indexing a tuple is:

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

You can see that the last line indexes the underlying C array: ob_item[i] (after some preliminary checks). ob_item is really an array of PyObject pointers:

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;

Why is time taken to access an element in a non-homogeneous list considered as constant

2 Answers2