Leistung bei der Überprüfung auf Duplikate

Question

Ich habe an einem Projekt gearbeitet, wo ich durch eine Sammlung von Daten zu durchlaufen muß, und entfernen Sie Einträge, bei denen der „Primärschlüssel“ dupliziert. Ich habe versucht, mit einem

List<int>

und

Dictionary<int, bool>

Mit dem Wörterbuch ich etwas bessere Leistung gefunden, obwohl ich nie brauchen die Boolesche mit jedem Eintrag markiert. Meine Erwartung ist, dass dies, weil eine Liste für einen Index den Zugriff erlaubt und ein Wörterbuch nicht. Was ich tue, ist frage mich, gibt es eine bessere Lösung für dieses Problem. Ich brauche nicht noch einmal die Einträge zuzugreifen, muss ich nur verfolgen, was „Primärschlüssel“ ich gesehen habe, und stellen Sie sicher, dass ich nur zusätzlich die Arbeit an Einträgen durchführen, die einen neuen Primärschlüssel haben. Ich bin mit C # und .NET 2.0. Und ich habe keine Kontrolle über die Eingangsdaten zur Festsetzung der Duplikate aus der Quelle zu entfernen (leider!). Und so können Sie ein Gefühl für die Skalierung haben, insgesamt für Duplikate über 1.000.000 mal in der Anwendung, die ich überprüft, aber in Teilmengen von nicht mehr als etwa 64.000, die eindeutig sein müssen.

Answer 1

Sie haben die HashSet Klasse in .NET 3.5 hinzugefügt. Aber ich denke, es ist auf einer Stufe mit dem Wörterbuch sein wird. Wenn Sie weniger als beispielsweise ein 100-Elemente eine Liste wahrscheinlich besser.

Answer 2

Edit: Nevermind mein Kommentar. Ich dachte, Sie sprechen über C ++. Ich habe keine Ahnung, ob mein Beitrag in der C # Welt relevant ist ..

Eine Hash-Tabelle könnte ein bisschen schneller sein. Binärbäumen (das ist, was im Wörterbuch verwendet) sind in der Regel relativ langsam sein, weil der Art und Weise auf den Speicher zugegriffen wird. Dies gilt insbesondere, wenn Ihr Baum sehr groß wird.

Bevor Sie jedoch Ihre Daten-Struktur ändern, haben Sie versucht, eine benutzerdefinierte Pool Allocator für Ihren Wörterbuch zu benutzen? Ich wette, die Zeit nicht ausgegeben wird, um den Baum selbst durchqueren, aber in den Millionen von Zuweisungen und Freigaben das Wörterbuch für Sie tut.

Sie können einen Faktor 10 Geschwindigkeitsschub sehen nur einen einfachen Pool Allocator in das Wörterbuch Vorlage anschließen. Afaik Auftrieb hat eine Komponente, die direkt verwendet werden können.

Eine andere Möglichkeit: Wenn Sie nur 64.000 Einträge in der ganzen Zahlen kennen existieren Sie können diejenigen, in eine Datei schreiben und eine perfekte Hash-Funktion für sie erstellen. Auf diese Weise können Sie einfach die Hash-Funktion benutzen, um Ihre ganzen Zahlen in den 0-64,000 Bereich und Index ein bisschen-Array abzubilden.

Wahrscheinlich ist der schnellste Weg, aber weniger flexibel. Sie haben Ihre perfekte Hash-Funktion wiederholen jedes Mal Ihre Menge der ganzen Zahlen ändert (kann automatisch erfolgen).

Answer 3

ich nicht wirklich bekommen, was Sie fordern.

Zum einen ist genau das Gegenteil von dem, was Sie sagen. Das Wörterbuch hat Zugriff indiziert (eine Hash-Tabelle), während de-Liste nicht.

Wenn Sie bereits die Daten in einem Wörterbuch haben dann alle Schlüssel eindeutig sind, kann es keine Duplikate sein.

I susspect Sie die Daten in einem anderen Datentyp gespeichert haben und Sie es in das Wörterbuch sind zu speichern. Wenn das der Fall ist werden das Einsetzen der Daten mit zwei Dictionarys arbeiten.

foreach (int key in keys)
{
  if (!MyDataDict.ContainsKey(key))
  {
    if (!MyDuplicatesDict.ContainsKey(key))
      MyDuplicatesDict.Add(key);
  }
  else
    MyDataDict.Add(key); 
}

Answer 4

Wenn Sie auf Eindeutigkeit der ganzen Zahlen sind überprüft, und der Bereich der ganzen Zahlen ist beschränkt genug ist, dann könnte man einfach ein Array verwenden.

Für eine bessere Verpackung können Sie eine Bitmap-Datenstruktur implementieren (im Grunde ein Array, aber jeder int in der Anordnung 32 ints im Schlüsselraum repräsentiert durch Verwendung von 1-Bit-pro-Taste). Auf diese Weise, wenn Sie maximale Anzahl 1.000.000 Sie brauchen nur ~ 30.5KB Speicher für die Datenstruktur.

Führt eine Bitmap wäre O (1) (pro Scheck), die schwer zu schlagen.

Answer 5

Es war eine Frage eine Weile zurück auf Duplikate aus einem Array entfernen. Für die Zwecke der Frage Leistung war nicht viel von einer Überlegung, aber Sie könnten einen Blick auf die Antworten nehmen wollen, wie sie Ihnen ein paar Ideen könnten. Auch könnte ich weg Basis hier sein, aber wenn Sie versuchen, Duplikate entfernen aus dem Array dann einem LINQ Befehl wie LINQ arbeitet auf .NET 2.0 so könnte dies ein Weg sein, eine Untersuchung wert.

Answer 6

Wenn Sie vorhaben, eine Liste zu verwenden, verwenden Sie die Binary:

 // initailize to a size if you know your set size
List<int> FoundKeys = new List<int>( 64000 );
Dictionary<int,int> FoundDuplicates = new Dictionary<int,int>();

foreach ( int Key in MyKeys )
{
   // this is an O(log N) operation
   int index = FoundKeys.BinarySearch( Key );
   if ( index < 0 ) 
   {
       // if the Key is not in our list, 
       // index is the two's compliment of the next value that is in the list
       // i.e. the position it should occupy, and we maintain sorted-ness!
       FoundKeys.Insert( ~index, Key );
   }
   else 
   {
       if ( DuplicateKeys.ContainsKey( Key ) )
       {
           DuplicateKeys[Key]++;
       }
       else
       {
           DuplicateKeys.Add( Key, 1 );
       }
   } 
} 

Sie können dies auch für jede Art verwenden, für die Sie ein IComparer unter Verwendung einer Überlastung definieren: Binary (T Artikel, IComparer );