Was ist der performanteste Weg, um mit einer Sammlung von ganzen Zahlen auf Existenz zu prüfen?

Question

Ich habe eine große Liste von Ganzzahlen, die an meinen Webservice gesendet werden. Laut unseren Geschäftsregeln müssen diese Werte eindeutig sein. Was ist der performanteste Weg herauszufinden, ob es Dubletten gibt? Ich muss die Werte nicht kennen, ich muss nur wissen, ob 2 der Werte gleich sind.

Zuerst dachte ich über die Verwendung einer generischen Liste von Ganzzahlen und der list.Exists() -Methode, aber das ist von O (n);

Dann dachte ich über die Verwendung eines Dictionary und der ContainsKey-Methode nach. Aber ich brauche nur die Schlüssel, ich brauche die Werte nicht. Und ich denke, das ist auch eine lineare Suche.

Gibt es einen besseren Datentyp, um die Eindeutigkeit innerhalb einer Liste zu finden? Oder stehe ich mit einer linearen Suche fest?

Answer 1

Verwenden Sie ein HashSet<T>:

Die HashSet-Klasse bietet hohe Performance Set-Operationen. Ein Satz ist eine Sammlung, die keine doppelten Elemente enthält, und deren Elemente in keiner besonderen Reihenfolge sind

HashSet<T> sogar a constructor that accepts an IEnumerable<T> aussetzt. Wenn Sie Ihren List<T> an den HashSet<T>'s Konstruktor übergeben, erhalten Sie einen Verweis auf einen neuen HashSet<T>, der eine eindeutige Sequenz von Elementen aus Ihrem ursprünglichen List<T> enthält.

Answer 2

Klingt wie ein Job für einen Hashset ...

Answer 3

Wenn Sie Rahmen verwenden 3.5 Sie die HashSet Sammlung verwenden können.

Ansonsten ist die beste Option die Dictionary. Der Wert jedes Artikels wird verschwendet, aber das wird Ihnen die beste Leistung bringen.

Wenn Sie nach Duplikaten suchen, während Sie die Elemente zum HashSet/Dictionary hinzufügen, anstatt sie anschließend zu zählen, erhalten Sie eine bessere Leistung als O (n), wenn Duplikate vorhanden sind, da Sie nicht weiter aufpassen müssen das erste Duplikat finden.

Answer 4

Wenn die Menge der Zahlen spärlich ist, dann verwenden Sie wie andere ein HashSet.

Aber wenn die Menge der Zahlen meist in Folge mit gelegentlichen Lücken ist, wäre es viel besser, wenn Sie die Anzahl als sortierte Array oder Binärbaum von Anfang, Ende Paare gespeichert. Dann könnten Sie suchen, um das Paar mit dem größten Anfangswert zu finden, der kleiner als Ihr Suchschlüssel war, und mit dem Endwert dieses Paares vergleichen, um zu sehen, ob es in der Menge existiert.

Answer 5

Was ist zu tun:

list.Distinct().Count() != list.Count() 

Ich frage mich über die Leistung dieser. Ich denke, es wäre so gut wie O (n), aber mit weniger Code und immer noch gut lesbar.