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

Question

我有一个系统，在该系统中我经常（但不是经常）必须在元组中查找下一个项目。我目前正在这样做：mytuple = (2,6,4,8,7,9,14,3)currentelement = 4def f(mytuple, currentelement):    return mytuple[mytuple.index(currentelement) + 1]nextelement = f(mytuple, currentelement)所有元素都是唯一的，并且我不受元组的困扰，如果需要的话，我可以在程序的更早版本中添加它。由于我需要做很多事情，所以我想知道是否有更有效的方法来做到这一点？

Answer 1

这里使用一个字典，类型的字典提供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'

创建上述命令的内存有效版本：

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