python - How is numpy's fancy indexing implemented?

Question

I was doing a little experimentation with 2D lists and numpy arrays. From this, I've raised 3 questions I'm quite curious to know the answer for.

First, I initialized a 2D python list.

>>> my_list = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]

I then tried indexing the list with a tuple.

>>> my_list[:,]
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: list indices must be integers, not tuple

Since the interpreter throws me a TypeError and not a SyntaxError, I surmised it is actually possible to do this, but python does not natively support it.

I then tried converting the list to a numpy array and doing the same thing.

>>> np.array(my_list)[:,]
array([[1, 2, 3],
       [4, 5, 6],
       [7, 8, 9]])

Of course, no problem. My understanding is that one of the __xx__() methods have been overridden and implemented in the numpy package.

Numpy's indexing supports lists too:

>>> np.array(my_list)[:,[0, 1]]
array([[1, 2],
       [4, 5],
       [7, 8]])

This has raised a couple of questions:

1. Which __xx__ method has numpy overridden/defined to handle fancy indexing?
2. Why don't python lists natively support fancy indexing?

(Bonus question: why do my timings show that slicing in python2 is slower than python3?)

Answer 1

You have three questions:

1. Which __xx__ method has numpy overridden/defined to handle fancy indexing?

The indexing operator [] is overridable using __getitem__, __setitem__, and __delitem__. It can be fun to write a simple subclass that offers some introspection:

>>> class VerboseList(list):
...     def __getitem__(self, key):
...         print(key)
...         return super().__getitem__(key)
...

Let's make an empty one first:

>>> l = VerboseList()

Now fill it with some values. Note that we haven't overridden __setitem__ so nothing interesting happens yet:

>>> l[:] = range(10)

Now let's get an item. At index 0 will be 0:

>>> l[0]
0
0

If we try to use a tuple, we get an error, but we get to see the tuple first!

>>> l[0, 4]
(0, 4)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 4, in __getitem__
TypeError: list indices must be integers or slices, not tuple

We can also find out how python represents slices internally:

>>> l[1:3]
slice(1, 3, None)
[1, 2]

There are lots more fun things you can do with this object -- give it a try!

2. Why don't python lists natively support fancy indexing?

This is hard to answer. One way of thinking about it is historical: because the numpy developers thought of it first.

You youngsters. When I was a kid...

Upon its first public release in 1991, Python had no numpy library, and to make a multi-dimensional list, you had to nest list structures. I assume that the early developers -- in particular, Guido van Rossum (GvR) -- felt that keeping things simple was best, initially. Slice indexing was already pretty powerful.

However, not too long after, interest grew in using Python as a scientific computing language. Between 1995 and 1997, a number of developers collaborated on a library called numeric, an early predecessor of numpy. Though he wasn't a major contributor to numeric or numpy, GvR coordinated with the numeric developers, extending Python's slice syntax in ways that made multidimensional array indexing easier. Later, an alternative to numeric arose called numarray; and in 2006, numpy was created, incorporating the best features of both.

These libraries were powerful, but they required heavy c extensions and so on. Working them into the base Python distribution would have made it bulky. And although GvR did enhance slice syntax a bit, adding fancy indexing to ordinary lists would have changed their API dramatically -- and somewhat redundantly. Given that fancy indexing could be had with an outside library already, the benefit wasn't worth the cost.

Parts of this narrative are speculative, in all honesty.¹ I don't know the developers really! But it's the same decision I would have made. In fact...

It really should be that way.

Although fancy indexing is very powerful, I'm glad it's not part of vanilla Python even today, because it means that you don't have to think very hard when working with ordinary lists. For many tasks you don't need it, and the cognitive load it imposes is significant.

Keep in mind that I'm talking about the load imposed on readers and maintainers. You may be a whiz-bang genius who can do 5-d tensor products in your head, but other people have to read your code. Keeping fancy indexing in numpy means people don't use it unless they honestly need it, which makes code more readable and maintainable in general.

3. Why is numpy's fancy indexing so slow on python2? Is it because I don't have native BLAS support for numpy in this version?

Possibly. It's definitely environment-dependent; I don't see the same difference on my machine.

---

^{1. The parts of the narrative that aren't as speculative are drawn from a brief history told in a special issue of Computing in Science and Engineering (2011 vol. 13).}