C＃ - 重複を見つけるためにコレクションを比較する最速の方法

Question

public class TestObject 
{ 
    string TestValue { get; set; } 
    bool IsDuplicate { get; set; } 
} 

List<TestObject> testList = new List<TestObject> 
{ 
    new TestObject { TestValue = "Matt" }, 
    new TestObject { TestValue = "Bob" }, 
    new TestObject { TestValue = "Alice" }, 
    new TestObject { TestValue = "Matt" }, 
    new TestObject { TestValue = "Claire" }, 
    new TestObject { TestValue = "Matt" } 
}; 

testListは実際に何百万ものオブジェクトが長いと想像してください。

TestObjectsとTestValueの3つのうち2つがIsDuplicateに設定されていることを確認する最速の方法は何ですか？与えられた値のインスタンスがどのように存在しても、IsDuplicateがfalseのプロセスから出てくるのは1つだけです。

スレッドを使用してこれを行うのは嫌です。また、別のコレクション型に変換する方がリストが高速である場合でも、コレクションはリストである必要はありません。

私は重複したものを保持し、それらをマークしてコレクションから削除しないでください。

これを展開するには、はるかに複雑な問題の簡単な表現を想像してみてください。問題のオブジェクトには、既に注文する順序があります。

正確な文字列の等価性で最初の複製をマッチングした後、私はコレクションをもう一度戻って、ファジーマッチングロジックを使用して残りの部分を再試行する必要があります。このプロセスの開始時に存在するコレクションは、重複排除中またはその後では変更されません。

最終的に元のコレクションがファイルに書き出され、おそらく重複がフラグされます。

Answer 1

ここで言及したように、正しいアプローチはHashSetクラスを使用することです。

var hashSet = new HashSet<string>(); 

foreach (var obj in testList) 
{ 
    if (!hashSet.Add(obj.TestValue)) 
    { 
     obj.IsDuplicate = true; 
    } 
} 

あなたがHashSetのに値を初めて追加すると、それが正常に追加され、アイテムに変更を加えないようにHashSet.Add()メソッドはtrueを返します。もう一度追加しようとすると、HashSet.Add()はfalseを返し、アイテムを重複としてマークします。

リストは、当社のマーキング重複の方法を実行し終えた後、次の状態があります：

Matt 
Bob 
Alice 
Claire 
Matt DUPLICATE 

Answer 2

おそらく私は数百万に2回のループを避けるためにここでtestValueのコレクションを構築しながら、重複をチェックするために行くだろう要素。このシナリオが可能である場合は、問題では許可されてきたように、私はより高速インデクサーを作るために、私はリストの代わりに配列することtestListを変更したい、Dictionary<string, List<TestValue>>

Dictionary<string, List<TestValue>> myList = new Dictionary<string, List<TestValue>>(); 
while(NotEndOfData()) 
{ 
    TestValue obj = GetTestValue(); 
    if(myList.ContainsKey(obj.Name)) 
    { 
     obj.IsDuplicate = true; 
     myList[obj.Name].Add(obj); 
    } 
    else 
    { 
     obj.IsDuplicate = false; 
     myList.Add(obj.Name, new List<TestValue>() { obj}; 
    } 
} 

Answer 3

SortedSet<string> sorted = new SortedSet<string>(); 
for (int i = 0; i < testList.Count; i++) 
    testList[i].IsDuplicate = !sorted.Add(testList[i].TestValue); 

を使用します。

Answer 4

あなたは、アイテムの序数を保持するプロパティがあることを示しています。アイテムを重複としてマークした後、そのプロパティを使用して並べ替え順序を元に戻すことができます。

以下のコードは自己説明的です。しかし、それ以上の説明が必要な場合に備えて、私に知らせてください。

私は、プロパティ名がSortOrderであると仮定しています。それに応じてコードを変更します。

void MarkDuplicates() 
{ 
    testList = testList.OrderBy(f => f.TestValue).ThenBy(f => f.SortOrder).ToList(); 
    for (int i = 1; i < testList.Count; i++) 
    { 
     if (testList[i].TestValue == testList[i - 1].TestValue) testList[i].IsDuplicate = true; 
    } 
    testList = testList.OrderBy(f => f.SortOrder).ToList(); 
} 

私はパフォーマンスエキスパートではありません。しかし、ここで提供されるさまざまなソリューションを試してみて、パフォーマンスを自分で確認できます。

Answer 5

これはおそらく非常にパフォーマンスである：

foreach (var dupe in testList.GroupBy(x => x.TestValue).SelectMany(g => g.Skip(1))) 
    dupe.IsDuplicate = true; 

[EDIT]この方法は、1つを使用しなければならないように、上記受け入れ答えの速度の約3分の1であることが判明しました。この答えは単なる学問的興味のものです。