大きいリスト（500,000+）で重複を効率的に特定する

Question

私はDOIの大きなリストを持っており、繰り返されるDOIを識別する最も効率的な方法が必要です。 ）DOIの配列は500,000 + DOIで構成されています。

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) 

これを行うには、より多くの処理効率的な方法があります：私の現在のアプローチは、この（inspired by this answer）はありますか？

サンプルDOI一覧：

doiList = ['10.1016/j.ijnurstu.2017.05.011 [doi]','10.1016/j.ijnurstu.2017.05.011 [doi]' ,'10.1167/iovs.16-20421 [doi]', '10.1093/cid/cix478 [doi]', '10.1038/bjc.2017.133 [doi]', '10.3892/or.2017.5646 [doi]', '10.1177/0961203317711009 [doi]', '10.2217/bmm-2017-0087 [doi]', '10.1007/s12016-017-8611-x [doi]', '10.1007/s10753-017-0594-5 [doi]', '10.1186/s13601-017-0150-2 [doi]', '10.3389/fimmu.2017.00515 [doi]', '10.2147/JAA.S131506 [doi]', '10.2147/JAA.S128431 [doi]', '10.1038/s41598-017-02293-z [doi]', '10.18632/oncotarget.17729 [doi]', '10.1073/pnas.1703683114 [doi]', '10.1096/fj.201600857RRR [doi]', '10.1128/AAC.00020-17 [doi]', '10.1016/j.jpain.2017.04.011 [doi]', '10.1016/j.jaip.2017.04.029 [doi]', '10.1016/j.anai.2017.04.021 [doi]', '10.1016/j.alit.2017.05.001 [doi]'] 

Answer 1

ではなくsetに格納してください。 dupesはすべて第二、第三、など重複する値のインデックスが含まれていながら、seenはすべて個別のDOI値が含まれ、この時点で

seen = set() 
dupes = [] 

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

：あなたは最高のものをスピードかもしれない単一のリストに重複を追加することができます。 doiListで検索して、どのインデックスがどの値に対応しているかを調べることができます。

このうちいくつかのより多くのパフォーマンスを得るには、メソッドキャッシュすることができます。

seen = set() 
seen_add = seen.add 
dupes = [] 
dupes_append = dupes.append 

for i, doi in enumerate(doiList): 
    if doi not in seen: 
     seen_add(doi) 
    else: 
     dupes_append(i) 

Answer 2

をここにあなたの例と同じデータセットを返す完全な解決策は、二倍速く（の犠牲によりちょうどより多くのですいくつかのメモリ）：

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][0] += 1の代わりにlookup[v][1] += 1を入力した場合は、[number_of_occurrences, first_index, second_index, third_index...]の形式で良い結果が得られた後にlookup[v].append(i)となります。