C# - schnellste Möglichkeit, eine Sammlung mit sich selbst zu vergleichen, um Duplikate zu finden

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" } 
}; 

Stellen Sie sich vor, testList ist eigentlich Millionen von Objekten lang.

Was ist der schnellste Weg, um sicherzustellen, dass zwei dieser drei TestObjects mit TestValue von Matt seine IsDuplicate auf wahr gesetzt wird? Unabhängig davon, wie viele Instanzen eines bestimmten Werts vorhanden sind, sollte nur einer mit IsDuplicate von false aus dem Prozess herauskommen.

Ich bin nicht abgeneigt, dies über Threading zu tun. Und die Sammlung muss keine Liste sein, wenn die Konvertierung in einen anderen Sammlertyp schneller ist.

Ich muss Duplikate aufbewahren und sie als solche markieren, nicht aus der Sammlung entfernen.

Um zu erweitern, ist dies (wie Sie sich vorstellen können) ein einfacher Ausdruck eines viel komplexeren Problems. Die betreffenden Objekte haben bereits eine Ordnungszahl, mit der ich sie ordnen kann.

Nachdem ich die ursprünglichen Duplikate auf die exakte String-Gleichheit abgeglichen habe, muss ich erneut durch die Sammlung gehen und den Rest mit einer Fuzzy-Matching-Logik wiederholen. Die zu Beginn dieses Prozesses vorhandene Sammlung wird während der Deduplizierung oder danach nicht geändert.

Schließlich wird die ursprüngliche Sammlung in eine Datei geschrieben werden, mit wahrscheinlich gekennzeichneten Duplikaten.

Answer 1

Wie andere erwähnten, wäre der korrekte Ansatz hier die Verwendung der HashSet-Klasse.

var hashSet = new HashSet<string>(); 

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

Wenn Sie einen Wert erstmals der HashSet hinzufügen, fügt sie erfolgreich und HashSet.Add() Methode gibt true zurück, so dass Sie auf das Element keine Änderungen vornehmen. Wenn Sie versuchen, es ein zweites Mal hinzuzufügen, gibt HashSet.Add() false zurück und Sie markieren Ihr Element als ein Duplikat.

Die Liste wird den folgenden Zustand nach Abschluss hat unsere Markierungs Dubletten Methode ausgeführt wird:

Matt 
Bob 
Alice 
Claire 
Matt DUPLICATE 

Answer 2

Wahrscheinlich für die Duplikate Ich würde zu überprüfen, während der Aufbau die Sammlung des Testvalue zu vermeiden Looping zweimal auf Millionen Elemente. Wenn dieses Szenario möglich ist, dann würde ich ein 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); 

verwenden, wie Sie in der Frage erlaubt haben, würde ich testList ändere ein Array statt einer Liste zu sein, Indexer schneller zu machen.

Answer 4

Da Sie angegeben haben, dass Sie über eine Eigenschaft verfügen, die die Ordnungszahl Ihrer Artikel enthält. Wir können diese Eigenschaft verwenden, um die Sortierreihenfolge auf das Original zurückzusetzen, nachdem wir unsere Artikel als Duplikate gekennzeichnet haben.

Der folgende Code ist selbsterklärend. Aber lassen Sie es mich wissen, falls Sie weitere Erläuterungen benötigen.

Ich habe angenommen, dass der Name der Eigenschaft SortOrder ist. Ändern Sie den Code entsprechend.

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(); 
} 

Ich bin kein Leistungsexperte.Aber Sie können die verschiedenen Lösungen, die hier zur Verfügung gestellt werden, zeitlich einstellen und die Leistung selbst überprüfen.

Answer 5

Dies ist wahrscheinlich recht performant:

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

[EDIT] Diese Methode etwa ein Drittel der Geschwindigkeit der akzeptierten Antwort oben zu sein, stellt sich heraus, so dass man verwendet werden soll. Diese Antwort ist nur von akademischem Interesse.