2013-06-18 183 views
6

我有一個系統,我經常(但不是經常)必須找到元組中的下一個元素。目前我在做這個,像這樣:查找元組中下一個元素的最有效方法

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) 

所有的元素都是獨一無二的,我不堅持的元組,如果需要,我可以做別的東西早些時候程序。

因爲我需要這樣做很多,我想知道是否有更有效的方法來做到這一點?

+0

所有數字都是唯一的嗎? –

+0

如果你堅持使用數據結構(即一個元組),那麼沒有。線性搜索是你所能做的。 –

+0

是的,所有元素都是唯一的,但實際上,它並不是我的程序中的數字,而是字符串。爲了簡化示例,我只是在這裏將它編號.. – kramer65

回答

7

這裏使用的字典,類型的字典相比list.index這是一個O(N)操作提供O(1)查找。

這也適用於字符串。

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

內存效率的版本,以創建上述字典:

>>> 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} 
+0

您先生,是輝煌的和一個全能的人。謝謝! – kramer65

1

您可能希望使用字典來建立一個指數

# 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。

相關問題