python - 如何避免使用 Index() 方法对大型列表进行缓慢搜索

Question

我有一个包含元组的大列表myList。

我需要删除此列表中的重复项(即具有相同顺序的相同元素的元组)。我还需要在单独的列表 indexList 中跟踪该列表的索引。如果删除重复项，我需要将其在 indexList 中的索引更改为第一个相同值的索引。

为了证明我的意思，如果 myList 看起来像这样:

myList = [(6, 2), (4, 3), (6, 2), (8, 1), (5, 4), (4, 3), (2, 1)]

然后我需要像这样构造indexList:

indexList = (0, 1, 0, 2, 3, 1, 4)

这里第三个值与第一个值相同，因此它(第三个值)的索引为0。随后的值也会获得更新后的索引 2 等等。

以下是我实现这一目标的方法:

unique = set()
i = 0
for v in myList[:]:
    if v not in unique:
        unique.add(v)
        indexList.append(i)
        i = i+1
    else:
        myList.pop(i)
        indexList.append(myList.index(v))

这就是我所需要的。然而，当 myList 包含数十万个元素时，index() 方法会使脚本变得非常慢。据我了解，这是因为它是一个 O(n) 操作。

那么我可以做哪些改变来达到相同的结果，但速度更快呢？

Answer 1

如果您创建一个字典来存储每个值的第一个索引，则可以在 O(1) 而不是 O(n) 中进行查找。因此，在本例中，在 for 循环之前执行 indexes = {}，然后在 if block 中执行 indexes[v] = i > 并在 else block 中使用 indexes[v] 而不是 myList.index(v)。