Gibt es in C# eine Art SortedList <double>, die schnelle Abfrage (mit LINQ) für den nächsten Wert ermöglicht?

Question

Ich suche nach einer Struktur, die eine sortierte Menge von Doppelwerten enthält. Ich möchte diese Menge abfragen, um den nächstliegenden Wert zu einem angegebenen Referenzwert zu finden.

Ich habe mir die SortedList<double, double> angesehen, und es ist ziemlich gut für mich. Da ich jedoch keine expliziten Schlüssel/Wert-Paare benötige. das scheint mir zuviel zu sein, und ich frage mich, ob ich schneller machen könnte.

Bedingungen:

• Die Struktur nur einmal initialisiert wird, und ändert sich nie (kein Insert/löscht)
• Die Menge der Werte im Bereich von 100k.
• Die Struktur wird oft mit neuen Referenzen abgefragt, die schnell ausführen müssen.
• Für Einfachheit und Geschwindigkeit kann der Wert des Satzes direkt unterhalb der Referenz zurückgegeben werden, nicht tatsächlich der nächste Wert
• Ich möchte LINQ für die Abfrage verwenden, wenn möglich, für die Einfachheit des Codes.
• Ich möchte, wenn möglich, keinen 3rd-Party-Code verwenden. .NET 3.5 ist verfügbar.
• Geschwindigkeit ist mehr als importand Speicherbedarf

ich zur Zeit den folgenden Code verwenden, wo SortedValues die zuvor erwähnte SortedList ist

IEnumerable<double> nearest = from item in SortedValues.Keys 
            where item <= suggestion 
            select item; 
    return nearest.ElementAt(nearest.Count() - 1); 

Kann ich schneller machen?

Auch ich bin nicht 100% sicher, ob dieser Code wirklich sicher ist. IEnumerable, der Rückgabetyp meiner Abfrage ist per Definition nicht mehr sortiert. Ein Unit-Test mit einer großen Testdatenbank hat aber gezeigt, dass es in der Praxis ist, also funktioniert das für mich. Haben Sie Hinweise zu diesem Aspekt?

P.S. Ich weiß, dass es viele ähnliche Fragen gibt, aber keine beantwortet meine spezifischen Bedürfnisse. Vor allem gibt es diese C# Data Structure Like Dictionary But Without A Value, aber der Fragesteller will nur die Existenz nicht finden, nichts zu finden.

Answer 1

Die Art, wie Sie es tun, ist unglaublich langsam, da es vom Anfang der Liste jedes Mal suchen muss, wenn es O (n) Leistung gibt.

Eine bessere Möglichkeit ist, die Elemente in eine Liste und dann sort die Liste zu setzen. Sie sagen, dass Sie den Inhalt nicht mehr ändern müssen, wenn er einmal initialisiert wurde.

Dann können Sie List<T>.BinarySearch verwenden, um Elemente zu finden oder den Einfügepunkt eines Elements zu finden, wenn es nicht bereits in der Liste vorhanden ist.

Aus der Dokumentation:

Rückgabewert

Der nullbasierte Index von Element in der sortierten List<T>, , wenn das Element gefunden wird; andernfalls eine negative Zahl, die das bitweise Komplement des Index des nächsten Elements ist, das größer als Element ist, oder , wenn es kein größeres Element gibt, das bitweise Komplement von Count.

Sobald Sie den Einfügepunkt haben, müssen Sie die Elemente auf jeder Seite überprüfen, um zu sehen, welche am nächsten ist.

Answer 2

Vielleicht nicht nützlich für Sie, aber .Net 4 hat eine SortedSet Klasse in der BCL.

Answer 3

ich denke, es kann mehr elegant sein wie folgt: Wenn Ihr Artikel nicht sortiert:

double nearest = values.OrderBy(x => x.Key).Last(x => x.Key <= requestedValue); 

Falls Ihre Artikel sortiert sind, können Sie die OrderBy Aufruf auslassen ...