Самый эффективный способ поиска следующего элемента в кортеже

Question

У меня есть система, в которой я часто (но не постоянно) должен найти следующий элемент в кортеже. В настоящее время я делаю это так:

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) 

Все элементы уникальны, и я не застрял с кортежем, я могу сделать что-то еще раньше в программе, если это необходимо.

Поскольку мне нужно это сделать много, мне было интересно, есть ли более эффективный способ сделать это?

Answer 1

Использование dict здесь, dicts обеспечивает O(1) поиск по сравнению с list.index который является операцией O(N).

И это будет работать и для струн.

>>> 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' 

Память эффективная версия для создания выше 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

Вы могли бы хотели построить индекс с использованием словаря:

# 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 

Если список изменений с течением времени , вам придется перестроить индекс. Для более эффективного решения памяти вы можете использовать izip вместо `zip, как было предложено в другом ответе.