What's the time complexity of indexing a numpy array directly
On the one hand
must be using a hash-table which will give a time complexity close to O(1). Is that right?
is not quite true. Numpy array
s are basically contiguous blocks of homogeneous memory, with some extra info on the side on dimensions and such. Therefore, the access is O(1), and just involves some trivial math to determine the position within the memory.
On the other hand
indexing must be pretty efficient.
is unfortunately not true at all. Asides from bounds checking (which arrays do), everything involving pure python is extremely inefficient (and accesses involve pure-python calls). Numpy array access is no exception. You should try to use vector operations whenever possible.
There is no hash table involved. Numpy arrays are arrays, just like the name implies, and the address is computed like this:
address of nArray[x, y] = base address + A * x + B * y