查找元组中下一个元素的最有效方法

我有一个系统，我经常（但不是经常）必须找到元组中的下一个元素。目前我在做这个，像这样：查找元组中下一个元素的最有效方法

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)

所有的元素都是独一无二的，我不坚持的元组，如果需要，我可以做别的东西早些时候程序。

因为我需要这样做很多，我想知道是否有更有效的方法来做到这一点？

来源

2013-06-18 kramer65

所有数字都是唯一的吗？ –

如果你坚持使用数据结构（即一个元组），那么没有。线性搜索是你所能做的。 –

是的，所有元素都是唯一的，但实际上，它并不是我的程序中的数字，而是字符串。为了简化示例，我只是在这里将它编号.. – kramer65

这里使用的字典，类型的字典相比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}

来源

2013-06-18 09:25:31

您先生，是辉煌的和一个全能的人。谢谢！ – kramer65

您可能希望使用字典来建立一个指数：

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

来源

2013-06-18 10:05:45

查找元组中下一个元素的最有效方法

回答

相关问题