How does a freely typed language have a constant search time for an array?

Question

If I have an integer array “arr” of length 10 in C to look at arr [5], the program can simply add 20 to the current location of the pointer and get my value (constant time).

But if the array is weakly typed (python / javascript list), how can the pointer know in constant time where the element is? Since he can no longer assume that each element is a fixed byte.

Answer 1

You can check the Python source code - 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; 

We see here that the Python list is just an array of pointers to PyObject . Therefore, to access the 5th element, we just need to take ob_item[5] , which simply adds 20 (40) to the value of the ob_item pointer.

You can see the actual code in listobject.c :

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