有效识别大列表中的重复项（500000+）

Question

我有一个很大的DOI列表，我需要最有效的方法来识别重复的DOI（例如，打印出索引和重复值的DOI）。DOI的数组可以包含500000多个DOI。我目前的方法是（inspired by this answer）：

from collections import defaultdict
D = defaultdict(list)
for i,item in enumerate(doiList):
    D[item].append(i)
D = {k:v for k,v in D.items() if len(v)>1}
print (D)

有没有更高效的处理方法？在

DOI列表示例：

^{pr2}$

Answer 1

下面是一个完整的解决方案，它返回与示例相同的数据集，只是速度快了两倍多（以牺牲一些内存为代价）：

def identify_duplicates(data):
    lookup = {}  # store our quick lookup here
    result = {}  # store for our final result
    for i, v in enumerate(data):
        if v in lookup:  # if already in the lookup table it's a duplicate
            if v not in result:  # add it to the result set
                result[v] = lookup[v]
            lookup[v][1] += 1  # increase duplicate count
        else:
            lookup[v] = [i, 0]  # default state for non-duplicates
    return result

print(identify_duplicates(doiList))
# prints: {'10.1016/j.ijnurstu.2017.05.011 [doi]': [0, 1]}

存储的索引是第一次出现已找到的重复项，如您的示例所示。如果要存储所有重复的索引，可以在lookup[v][1] += 1行后添加lookup[v].append(i)，但这样数据可能看起来很奇怪（结构应该是[first_index, number_of_occurrences, second_index, third_index...]）

相反，只需在lookup[v]修改-lookup[v] = [0, i]而不是lookup[v] = [i, 0]和{}而不是{}中翻转存储的参数，然后lookup[v].append(i)将以：[number_of_occurrences, first_index, second_index, third_index...]的形式给出一个很好的结果。在

Answer 2

尝试将它们存储在^{}中。可以将重复项附加到单个列表中，这可能会加快速度：

seen = set()
dupes = []

for i, doi in enumerate(doiList):
    if doi not in seen:
        seen.add(doi)
    else:
        dupes.append(i)

此时，seen包含所有不同的doi值，而dupes包含重复值的所有第二、第三等索引。您可以在doiList中查找它们，以确定哪个索引对应于哪个值。在

要获得更好的性能，可以缓存以下方法：

^{pr2}$