Suchen nach Duplikaten in der Liste der Liste

Versuchen wir, die beste Leistung zu erzielen. Wenn n die Anzahl der Listen und m die Länge der Listen ist, können wir O (n m + n logn + n) plus eine gewisse Wahrscheinlichkeit von Hash-Codes für verschiedene Listen erhalten.

Wichtige Schritte:

1. Hash-Codes berechnen *
2. Sortiere sie
3. Gehe über die Liste, um Duplikate zu finden

* Das ist ein wichtiger Schritt. für Simplizität können Sie Hash als = ... ^ (Liste [i] & lt; & lt; i) ^ (Liste [i + 1] & lt; & lt; (i + 1))

Bearbeiten für jene Leute, die denken, dass PLINQ das Ding ankurbeln kann, aber kein guter Algorithmus. PLINQ kann auch hier hinzugefügt werden, da alle Schritte leicht parallelisierbar sind.

Mein Code:

Es sei denn, Sie tun etwas schweres Heben, funktioniert vielleicht der folgende einfache Code für Sie:

Offensichtlich können Sie eine bessere Leistung erzielen, wenn Sie einen Algorithmus manuell anpassen, sodass Sie die Listen nicht bei jeder Iteration durchsuchen müssen, aber es gibt etwas, das für das Schreiben von deklarativem, einfacherem Code gesagt werden kann.

(Und dank der Awesomeness von LINQ®, indem ein .AsParallel () - Aufruf zum obigen Code hinzugefügt wird, läuft der Algorithmus auf mehreren Kernen und läuft damit möglicherweise schneller als die komplexen, von Hand optimierten Lösungen, die hier erwähnt werden Thread.)

So etwas gibt Ihnen die richtigen Ergebnisse:

Sie müssen jeden Index jeder Liste mindestens einmal durchlaufen, aber Sie können den Prozess potenziell beschleunigen, indem Sie eine benutzerdefinierte Hash-Tabelle erstellen, so dass Sie nichtduplizierte Listen schnell ablehnen können, ohne Vergleiche durchführen zu müssen. Artikel.

Algorithmus:

Wenn Sie für Ihre Eingabedaten einen ausreichend starken Hashalgorithmus haben, müssen Sie möglicherweise nicht einmal die Untervergleiche durchführen, da es keine Hash-Kollisionen geben würde.

Ich habe einen Beispielcode. Die fehlenden Bits sind:

• Eine Optimierung, so dass wir die Wörterbuchsuche nur einmal pro Liste durchführen (zum Suchen und Einfügen). Müssen Sie vielleicht Ihre eigene Wörterbuch- / Hashtabellen-Klasse erstellen?
• Ein besserer Hashing-Algorithmus, den Sie finden, indem Sie eine Menge von ihnen gegen Ihre Daten profilieren

Hier ist der Code:

Hier ist eine mögliche Idee (dies setzt voraus, dass die Werte numerisch sind):

Implementieren Sie einen Vergleich, der jedes Mitglied jeder Sammlung mit seinem Index multipliziert und dann das Ganze summiert:

Member CheckSum: 170

Also hat die ganze "Zeile" eine Nummer, die sich mit den Mitgliedern und der Reihenfolge ändert. Schnell zu berechnen und zu vergleichen.

Was ist mit dem Schreiben eines eigenen Listenvergleichs:

und dann einfach:

Wenn sie alle einstellig sind und die gleiche Anzahl von Elementen haben, können Sie sie zusammensetzen, so dass die erste 123456 ist und prüfen, ob die Zahlen gleich sind.

Dann hätten Sie eine Liste {123456, 123456, 142456, 325164}

Das ist einfacher zu prüfen, ob Duplikate vorhanden sind. Wenn die einzelnen Mitglieder mehr als 10 Mitglieder sein können, müsstest Du das ändern.

Bearbeiten: hinzugefügt Beispielcode, kann optimiert werden, nur ein kurzes Beispiel, um zu erklären, was ich meinte.

Es gibt bereits eine Reihe von guten Lösungen, aber ich glaube, dass diese immer am schnellsten laufen werden es sei denn gibt es eine Struktur der Daten, über die Sie uns noch nicht informiert haben.

• Erstellen Sie eine Map aus einem Integer-Schlüssel in List und eine Map aus Schlüssel in List<List<int>>
• Berechnen Sie für jedes List<int> einen Hashwert mit einer einfachen Funktion wie (...((x0)*a + x1)*a + ...)*a + xN) , die Sie rekursiv berechnen können; a sollte etwas wie 1367130559 sein (d. h. eine große Primzahl, die zufällig einer interessanten Potenz von 2 nicht nahe kommt.
• Fügen Sie den Hash und die Liste, aus der er stammt, als Schlüssel / Wert-Paar hinzu, falls er nicht existiert. Wenn es existiert, schauen Sie in die zweite Karte. Wenn die zweite Map diesen Schlüssel enthält, fügen Sie das neue List<int> der akkumulierenden Liste hinzu. Wenn nicht, nimm das List<int> , das du von der ersten Karte und dem List<int> , das du getestet hast, gesucht hast, und füge einen neuen Eintrag in der zweiten Karte hinzu, der eine Liste dieser beiden Elemente enthält.
• Wiederholen Sie den Vorgang, bis Sie Ihre gesamte erste Liste durchlaufen haben. Jetzt haben Sie eine Hashmap mit einer Liste potentieller Kollisionen (die zweite Karte) und eine Hashmap mit einer Liste von Schlüsseln (die erste Karte).
• Iteriere durch die zweite Karte. Nimm für jeden Eintrag das List<List<int>> und sortiere es lexikografisch. Gehen Sie nun einfach durch Gleichheitsvergleiche, um die Anzahl der verschiedenen Blöcke zu zählen.
• Ihre Gesamtanzahl von Elementen entspricht der Länge Ihrer ursprünglichen Liste.
• Ihre Anzahl an unterschiedlichen Elementen entspricht der Größe Ihrer ersten hashmap plus der Summe von (Anzahl der Blöcke - 1) für jeden Eintrag in Ihrer zweiten hashmap.
• Ihre Anzahl der doppelten Einträge ist der Unterschied zwischen diesen beiden Zahlen (und Sie können alle möglichen anderen Dinge herausfinden, wenn Sie möchten).

Wenn Sie N nicht-duplizierte Elemente und M Einträge, die Duplikate aus einer Menge von K-Elementen sind, haben, werden Sie O (N + M + 2K) benötigen, um die ursprünglichen Hash-Maps zu erstellen, im schlimmsten Fall O (M log M), um das Sortieren durchzuführen (und wahrscheinlich mehr wie O (M log (M / K))), und O (M), um den endgültigen Gleichheitstest durchzuführen.

Auschecken C # 3.0: Muss Duplikate zurückgeben Aus einer List & lt; & gt; wird gezeigt, wie Duplikate aus der Liste zurückgegeben werden.

Beispiel von dieser Seite: