在Python列表中去除重复项但记住索引

Question

如何在保留列表原始顺序的同时删除重复项，并记住列表中任何项的第一个索引？

例如，从[1, 1, 2, 3]中删除重复项得到[1, 2, 3]，但我需要记住索引[0, 2, 3]。

我正在使用Python 2.7。

- kklw

Answer 1

我会采用不同的方法，使用一个OrderedDict和列表的index方法返回项的最低索引。

>>> from collections import OrderedDict
>>> lst = [1, 1, 2, 3]
>>> d = OrderedDict((x, lst.index(x)) for x in lst)
>>> d
OrderedDict([(1, 0), (2, 2), (3, 3)]

如果您需要分别获取去重后的列表和索引，您可以使用以下命令：

>>> d.keys()
[1, 2, 3]
>>> d.values()
[0, 2, 3]

- timgeb

Answer 2

使用enumerate来跟踪索引，使用集合来跟踪已经出现的元素：

l = [1, 1, 2, 3]
inds = []
seen = set()
for i, ele in enumerate(l):
    if ele not in seen:
        inds.append(i)
    seen.add(ele)

如果您想要两者兼得：

inds = []
seen = set()
for i, ele in enumerate(l):
    if ele not in seen:
        inds.append((i,ele))
    seen.add(ele)

或者如果你想要将它们分别放在不同的列表中：

l = [1, 1, 2, 3]
inds, unq = [],[]
seen = set()
for i, ele in enumerate(l):
    if ele not in seen:
        inds.append(i)
        unq.append(ele)
    seen.add(ele)

使用集合是到目前为止最好的方法：

In [13]: l = [randint(1,10000) for _ in range(10000)]     

In [14]: %%timeit                                         
inds = []
seen = set()
for i, ele in enumerate(l):
    if ele not in seen:
        inds.append((i,ele))
    seen.add(ele)
   ....: 
100 loops, best of 3: 3.08 ms per loop

In [15]: timeit  OrderedDict((x, l.index(x)) for x in l)
1 loops, best of 3: 442 ms per loop

In [16]: l = [randint(1,10000) for _ in range(100000)]      
In [17]: timeit  OrderedDict((x, l.index(x)) for x in l)
1 loops, best of 3: 10.3 s per loop

In [18]: %%timeit                                       
inds = []
seen = set()
for i, ele in enumerate(l):
    if ele not in seen:
        inds.append((i,ele))
    seen.add(ele)
   ....: 
10 loops, best of 3: 22.6 ms per loop

对于100k个元素，使用list.index方法需要10.3秒，而使用创建两个列表的方法只需22.6毫秒。如果你尝试使用任何更大的、重复性较小的数据，例如[randint(1,100000) for _ in range(100000)]，你将有足够的时间看一本书。创建两个列表的速度略慢，但仍然比使用list.index方法快数个数量级。

如果你想逐个获取值，可以使用生成器函数。

def yield_un(l):
    seen = set()
    for i, ele in enumerate(l):
        if ele not in seen:
            yield (i,ele)
        seen.add(ele)

- Padraic Cunningham

---

很棒的解释，附带时间比较...从未想过会有这么大的差别.. :-O - Iron Fist