Python列表中重复项的索引

Question

有没有人知道我怎么能找到Python列表中重复项的索引位置？我试过这样做，但它总是只给我列表中第一个出现的那个项的索引。

List = ['A', 'B', 'A', 'C', 'E']

我想要它给我：

index 0: A   
index 2: A

Answer 1

我对这里所有建议的解决方案做了一个性能测试，并且还添加了另一种解决方案（在答案的最后部分描述）。

性能测试

首先，关于性能测试。我初始化了一个包含 n 个随机整数的列表，这些整数的范围在 [1, n/2] 之间，然后对所有算法使用 timeit 进行计时。

来自 @Paul McGuire 和 @Ignacio Vazquez-Abrams 的解决方案在处理100个整数时，速度大约是其他方案的两倍：

Testing algorithm on the list of 100 items using 10000 loops
Algorithm: dupl_eat
Timing: 1.46247477189
####################
Algorithm: dupl_utdemir
Timing: 2.93324529055
####################
Algorithm: dupl_lthaulow
Timing: 3.89198786645
####################
Algorithm: dupl_pmcguire
Timing: 0.583058259784
####################
Algorithm: dupl_ivazques_abrams
Timing: 0.645062989076
####################
Algorithm: dupl_rbespal
Timing: 1.06523873786
####################

如果把项目数量改成1000，差距会变得更大（顺便问一下，如果有人能解释一下为什么会这样，我会很高兴）：

Testing algorithm on the list of 1000 items using 1000 loops
Algorithm: dupl_eat
Timing: 5.46171654555
####################
Algorithm: dupl_utdemir
Timing: 25.5582547323
####################
Algorithm: dupl_lthaulow
Timing: 39.284285326
####################
Algorithm: dupl_pmcguire
Timing: 0.56558489513
####################
Algorithm: dupl_ivazques_abrams
Timing: 0.615980005148
####################
Algorithm: dupl_rbespal
Timing: 1.21610942322
####################

在处理更大的列表时，@Paul McGuire 的解决方案依然是最有效的，而我的算法开始出现问题。

Testing algorithm on the list of 1000000 items using 1 loops
Algorithm: dupl_pmcguire
Timing: 1.5019953958
####################
Algorithm: dupl_ivazques_abrams
Timing: 1.70856155898
####################
Algorithm: dupl_rbespal
Timing: 3.95820421595
####################

完整的性能测试代码可以在 这里 找到。

另一种算法

这是我对同一问题的解决方案：

def dupl_rbespal(c):
    alreadyAdded = False
    dupl_c = dict()
    sorted_ind_c = sorted(range(len(c)), key=lambda x: c[x]) # sort incoming list but save the indexes of sorted items

    for i in xrange(len(c) - 1): # loop over indexes of sorted items
        if c[sorted_ind_c[i]] == c[sorted_ind_c[i+1]]: # if two consecutive indexes point to the same value, add it to the duplicates
            if not alreadyAdded:
                dupl_c[c[sorted_ind_c[i]]] = [sorted_ind_c[i], sorted_ind_c[i+1]]
                alreadyAdded = True
            else:
                dupl_c[c[sorted_ind_c[i]]].append( sorted_ind_c[i+1] )
        else:
            alreadyAdded = False
    return dupl_c

虽然它不是最好的，但它让我生成了一个稍微不同的结构，这对我的问题是必要的（我需要类似于同一值索引的链表）。

Answer 2

>>> def indices(lst, item):
...   return [i for i, x in enumerate(lst) if x == item]
... 
>>> indices(List, "A")
[0, 2]

如果你想找出所有重复的项，可以使用下面的方法，不过这个方法效率不是很高。如果效率对你来说很重要，建议你考虑Ignacio的解决方案。

>>> dict((x, indices(List, x)) for x in set(List) if List.count(x) > 1)
{'A': [0, 2]}

至于使用list的index方法来解决这个问题，这个方法有一个可选的第二个参数，可以指定从哪里开始查找。所以你可以在找到一个索引后，再从这个索引加1的位置继续查找。

>>> List.index("A")
0
>>> List.index("A", 1)
2

Answer 3

你想给index函数传一个可选的第二个参数，这个参数是你希望index开始查找的位置。在找到每个匹配项后，把这个参数重置为刚找到的匹配项后面的那个位置。

def list_duplicates_of(seq,item):
    start_at = -1
    locs = []
    while True:
        try:
            loc = seq.index(item,start_at+1)
        except ValueError:
            break
        else:
            locs.append(loc)
            start_at = loc
    return locs

source = "ABABDBAAEDSBQEWBAFLSAFB"
print(list_duplicates_of(source, 'B'))

输出结果：

[1, 3, 5, 11, 15, 22]

你可以通过一次遍历源数据，使用defaultdict来记录每个项目出现过的位置，从而一次性找到所有重复的项，并返回那些出现超过一次的项目。

from collections import defaultdict

def list_duplicates(seq):
    tally = defaultdict(list)
    for i,item in enumerate(seq):
        tally[item].append(i)
    return ((key,locs) for key,locs in tally.items() 
                            if len(locs)>1)

for dup in sorted(list_duplicates(source)):
    print(dup)

输出结果：

('A', [0, 2, 6, 7, 16, 20])
('B', [1, 3, 5, 11, 15, 22])
('D', [4, 9])
('E', [8, 13])
('F', [17, 21])
('S', [10, 19])

如果你想对同一个源数据进行多次测试，使用不同的关键字，可以用functools.partial来创建一个新的函数变量，这个变量使用了“部分完成”的参数列表，也就是说，指定了seq，但省略了要查找的项目：

from functools import partial
dups_in_source = partial(list_duplicates_of, source)

for c in "ABDEFS":
    print(c, dups_in_source(c))

输出结果：

A [0, 2, 6, 7, 16, 20]
B [1, 3, 5, 11, 15, 22]
D [4, 9]
E [8, 13]
F [17, 21]
S [10, 19]