Most efficient way of finding the next element in a tuple

Question

I've got a system in which I often (but not constantly) have to find the next item in a tuple. I'm currently doing this like so:

mytuple = (2,6,4,8,7,9,14,3)
currentelement = 4
def f(mytuple, currentelement):
    return mytuple[mytuple.index(currentelement) + 1]
nextelement = f(mytuple, currentelement)

All elements are unique and I am not stuck with the tuple, I can make it something else earlier in the program if needed.

Since I need to do this a lot, I was wondering whether there is any more efficient way to do this?

Answer 1

Use a dict here, dicts provide O(1) lookup compared to list.index which is an O(N) operation.

And this will work for strings as well.

>>> lis = (2,6,4,8,7,9,14,3)
>>> dic = dict(zip(lis, lis[1:]))
>>> dic[4]
8
>>> dic[7]
9
>>> dic.get(100, 'not found') #dict.get can handle key errors
'not found'

A memory efficient version to create the above dict:

>>> from itertools import izip
>>> lis = (2,6,4,8,7,9,14,3)
>>> it1 = iter(lis)
>>> it2 = iter(lis)
>>> next(it2)
2
>>> dict(izip(it1,it2))
{2: 6, 4: 8, 6: 4, 7: 9, 8: 7, 9: 14, 14: 3}

Answer 2

You might wish to build an index using a dictionary:

# The list
>>> lis = (2,6,4,8,7,9,14,3)

# build the index
>>> index = dict(zip(lis, range(len(lis))))
>>> index
{2: 0, 3: 7, 4: 2, 6: 1, 7: 4, 8: 3, 9: 5, 14: 6}

# Retrieve position by using the index
>>> index[6]
1
>>> lis[index[6]+1]
4

If your list change over time, you will have to rebuild the index. For a more memory efficient solution, you might prefer using izip instead of `zip̀ as suggested in an other answer.