Efficient multiple, arbitrary index access in Python tuple?

Question

I have a long Python tuple t. I would like to grab the elements at indices i1, i2, ..., iN from t as efficiently as possible. What's the best way?

One approach is:

(1)    result = [t[j] for j in (i1, i2, ..., iN)]

but this would seem to cause N separate lookups into the tuple. Is there a faster way? When Python does slices like this:

(2)    result = t[1:M:3]

I assume that it does not perform M/3 separate lookups. (Maybe it uses a bitmask and does a single copy operation?) Is there some way for me to capitalize on whatever Python does in (2) to make my arbitrary-index slice happen in a single copy?

Thanks.

Answer 1

If you are doing a bunch of identical lookups, it may be worth using an itemgetter

from operator import itemgetter
mygetter = itemgetter(i1, i2, ..., iN)
for tup in lots_of_tuples:
    result = mygetter(tup)

For one off, the overhead of creating the itemgetter is not worthwhile

Quick test in iPython shows:

In [1]: import random

In [2]: from operator import itemgetter

In [3]: t=tuple(range(1000))

In [4]: idxs = tuple(random.randrange(1000) for i in range(20))

In [5]: timeit [t[i] for i in idxs]
100000 loops, best of 3: 2.09 us per loop

In [6]: mygetter = itemgetter(*idxs)

In [7]: timeit mygetter(t)
1000000 loops, best of 3: 596 ns per loop

Obviously the difference will depend on the length of the tuple, the number of indices, etc.

Answer 2

The one you've listed is the most optimal way to get the elements from a tuple. You usually don't care about the performance in such expressions – it's a premature optimisation, and even if you did, such operations are already too slow even with the optimisations, i.e. if you optimise the access the loop itself will still be slow due to reference counting of the temporary variables and etc.

If you already have a performance issue or this is already part of CPU-heavy code you can try several alternatives:

1) numpy arrays:

>>> arr = np.array(xrange(2000))
>>> mask = np.array([True]*2000)
>>> mask = np.array([False]*2000)
>>> mask[3] = True
>>> mask[300] = True
>>> arr[mask]
array([  3, 300])

2) You can use the C API to copy the elements using PyTuple_GET_ITEM which accesses the internal array directly, but be warned that using the C API is not trivial and can introduce a lot of bugs.

3) You can use C arrays with the C API, using e.g. the buffer interface of array.array to glue the data access to Python.

4) You can use Cython with C arrays and a custom Cython type for data access from Python.

5) You can use Cython and numpy together.