LINQ in SortedList

Das Schreiben einer binären Suche kann schwierig sein.

Zum Glück hat Microsoft bereits eine ziemlich robuste geschrieben: Array.BinarySearch<T> . Dies ist in der Tat , die Methode, die SortedList<TKey, TValue>.IndexOfKey intern verwendet . Das einzige Problem ist, dass es ein T[] Argument anstelle von IList<T> (wie SortedList<TKey, TValue>.Keys ) benötigt.

Weißt du was? Es gibt dieses großartige Tool namens Reflektor , mit dem Sie sich den .NET-Quellcode ansehen können ...

Probieren Sie es aus: eine generische BinarySearch Erweiterungsmethode für IList<T> , die direkt aus dem reflektierten Code der Microsoft Array.BinarySearch<T> Implementierung stammt.

Damit können Sie list.Keys.BinarySearch aufrufen und das negative bitweise Komplement des gewünschten Indexes erhalten, falls der gewünschte Schlüssel nicht gefunden wird (das Folgende wird im Wesentlichen direkt aus tzaman's Antwort genommen):

Zuerst wird Ihre Anfrage zweimal ausgewertet (einmal für Any und einmal für Min ). Zweitens erfordert Min , dass es über die gesamte Liste iteriert, obwohl die Tatsache, dass es sortiert ist, bedeutet, dass das erste Element das Minimum ist. Sie sollten dies ändern können:

Dazu:

AKTUALISIEREN

Da Sie einen Werttyp auswählen, gibt FirstOrDefault kein Nullable-Objekt zurück. Ich habe Ihre Abfrage so geändert, dass der ausgewählte Wert stattdessen in int? umgewandelt wird, sodass der resultierende Wert auf null überprüft werden kann. Ich würde dies für die Verwendung von ContainsKey empfehlen, da dies true zurückgeben würde, wenn Ihre Liste einen Wert für 0 enthalten würde. Angenommen, Sie haben die folgenden Werte

0 2 4 6 8

Wenn Sie etwas kleiner oder gleich 8 eingeben, erhalten Sie den richtigen Wert. Wenn Sie jedoch 9 übergeben, erhalten Sie 0 ( default(int) ), das ist in der Liste, aber ist nicht ein gültiges Ergebnis.

Wenn Sie LINQ für SortedList verwenden, profitieren Sie nicht von der Sortierung.

Für optimale Leistung sollten Sie Ihre eigene binäre Suche schreiben.

OK, nur um ein bisschen mehr Sichtbarkeit zu geben - hier ist eine prägnantere Version von Adam Robinsons Antwort:

Die Funktion FirstOrDefault hat eine Überladung, die ein Prädikat akzeptiert, das das erste Element auswählt, das eine Bedingung erfüllt - Sie können das Element direkt verwenden, um das gewünschte Element zu erhalten, oder null , wenn es nicht existiert.

Warum nicht das BinarySearch verwenden, das in der Klasse List eingebaut ist?

Wenn das Suchziel nicht in der Liste ist, gibt BinarySearch das bitweise Komplement des nächsthöheren Elements zurück; wir können das verwenden, um Sie direkt zu bekommen, was Sie wollen, indem Sie das Ergebnis erneut ergänzen, wenn es negativ ist. Wenn es gleich Count wird, war Ihr Suchschlüssel größer als alles in der Liste.

Dies sollte viel schneller sein als ein LINQ where , da es bereits sortiert ist ... Wie die Kommentare gezeigt haben, erzwingt der Aufruf ToList eine Auswertung der gesamten Liste. Dies ist nur von Vorteil, wenn Sie mehrere Suchvorgänge durchführen, ohne die zugrundeliegende SortedList zu ändern, und die keys -Liste getrennt herum behalten.

Wenn Sie OrderedDictionary in PowerCollections verwenden, können Sie einen Enumerator erhalten, der dort beginnt, wo der gesuchte Schlüssel sein sollte ... wenn er nicht vorhanden ist, erhalten Sie den nächsten Knoten und können dann in O vor / zurück navigieren (log N) Zeit pro nav Anruf.

Dies hat den Vorteil, dass Sie nicht Ihre eigene Suche schreiben müssen oder sogar Ihre eigenen Suchen über einer SortedList verwalten müssen.