Finden Sie den nächsten Wörterbuchschlüssel effizient

Ich habe eine Reihe von Paaren von Daten und monetären Werte in einem SortedDictionary<DateTime, decimal> entsprechend Darlehensvaluta berechnet in der Zukunft im Vertrag definierten compounding dates. Gibt es eine effiziente Möglichkeit, ein Datum zu finden Schlüssel, der am nächsten ist zu einem bestimmten Wert? (Genauer gesagt, der nächste Schlüssel weniger als oder gleich das Ziel). Der Punkt ist das speichern nur die Daten, die an die Punkte, wenn der Wert geändert, aber effizient die Antwort auf die Frage "was war der Saldo auf x date?" für ein beliebiges Datum in Reichweite.

Eine ähnliche Frage gestellt wurde ( Was .NET-Wörterbuch unterstützt "finde nächstgelegene Taste" Betrieb? ) und die Antwort war "Nein" zu der Zeit, zumindest von den Leuten, die geantwortet haben, aber das war vor fast 3 Jahren.

Die Frage So finden Sie Punkt zwischen zwei Schlüssel im Wörterbuch sortiert präsentiert die offensichtliche Lösung naiv Durchlaufen alle Tasten. Ich Frage mich, ob alle integrierten framework-Funktion vorhanden ist, um die Vorteile der Tatsache, dass die keys sind bereits indiziert und sortiert im Speicher -- oder, alternativ, ein integriertes Framework-Auflistungsklasse, die geeignet wäre, sich selbst besser zu dieser Art der Abfrage.

Kommentar zu dem Problem
Aber die Schlüssel des dictionary sind NICHT geordnet in Erinnerung. Das ist, warum Sie nicht direkt zu tun, ein "get nearest" oder "weniger-als-oder-gleich" auf ein Wörterbuch. Kommentarautor: Jim Mischel
Die verlinkte Frage ist zu erwähnen, , SortedList<K V> - Struktur. Ich gehe mit, dass. Kommentarautor: nawfal

InformationsquelleAutor der Frage Joshua Honig | 2012-09-13

  1. 21

    Seit SortedDictionary ist sortiert nach dem key können Sie erstellen eine sortierte Liste von Schlüsseln mit

    var keys = new List<DateTime>(dictionary.Keys);

    dann effizient durchführen binäre Suche:

    var index = keys.BinarySearch(key);

    Wie die Dokumentation sagt, wenn index ist positiv oder null ist, wird der Schlüssel vorhanden ist; wenn es negativ ist, dann ~index ist der index, wo key gefunden werden würde, wenn er existierte. Daher wird der index der "sofort kleinere" vorhandenen Schlüssel ist ~index - 1. Stellen Sie sicher, Sie behandeln Sie richtig die Kante Fall, wo key ist kleiner als jede der vorhandenen Tasten und der ~index - 1 == -1.

    Natürlich die oben erwähnten Ansatz wirklich nur Sinn macht, wenn keys aufgebaut wird, einmal und dann wiederholt abgefragt; da es sich um das iterieren über die gesamte Sequenz von Tasten und tun, eine binäre Suche auf top von, dass es keinen Sinn zu versuchen dieses wenn Sie nur einmal suchen. In diesem Fall sogar die naiven iteration besser werden würde.

    Update

    Als digEmAll richtig fest, man könnte auch Schalter zu SortedList<DateTime, decimal> so, dass die Keys collection implementiert IList<T> (das SortedDictionary.Tasten nicht). Diese Schnittstelle bietet eine ausreichende Funktionalität zum ausführen einer binären Suche auf manuell, so könnte man z.B. dieser code und machen es eine extension-Methode auf IList<T>.

    Sollten Sie auch im Hinterkopf behalten, dass SortedList führt schlimmer als SortedDictionary während der Bauphase, wenn die Elemente nicht eingefügt in bereits sortierter Reihenfolge, obwohl in diesem speziellen Fall ist es sehr wahrscheinlich, dass Daten eingefügt werden, werden in chronologischer Reihenfolge (sortiert) bestellen, das wäre perfekt.

    InformationsquelleAutor der Antwort Jon

  2. 7

    So, in diesem nicht direkt die Antwort auf Ihre Frage, weil Sie ausdrücklich gebeten, für etwas, das in der .NET framework, aber vor einem ähnlichen problem, fand ich folgende Lösung am besten zu funktionieren, und ich wollte es hier posten für andere Suchende.

    Benutzte ich die TreeDictionary<K V> aus der C5-Sammlungen (GitHub/NuGet), die eine Implementierung eines rot-schwarz-Baum.

    Es hat Predecessor/TryPredecessor und WeakPredessor/TryWeakPredecessor Methoden (sowie ähnliche Methoden für die Nachfolger), einfach den nächsten Artikel auf eine Taste.

    Mehr sinnvoll in deinem Fall, denke ich, ist die RangeFrom/RangeTo/RangeFromTo Methoden, mit denen Sie zum abrufen einer Reihe von Schlüssel-Wert-Paare zwischen den Tasten.

    Beachten Sie, dass alle diese Methoden können auch angewendet werden, um die TreeDictionary<K, V>.Keys Sammlung, mit denen Sie arbeiten nur mit dem Schlüssel als auch.

    Es ist wirklich eine sehr nette Umsetzung, und so etwas wie Sie verdient es, in der BCL.

    InformationsquelleAutor der Antwort Riko

  3. 1

    Ist es nicht möglich, effizient finden Sie die nächste Taste mit SortedList, SortedDictionary oder anderen "built-in" .NET geben, wenn Sie brauchen, um das verschachteln von Abfragen mit Einlagen (es sei denn, eintreffen Ihrer Daten vorsortiert, oder die Sammlung wird immer kleiner).

    Als ich erwähnte, auf der anderen Frage, die Sie verwiesen, ich habe drei Daten-Strukturen in Bezug auf B+ - Bäumen, die bieten find-nearest-key-Funktionalität für jeden zu sortierenden Datentyp: BList<T>, BDictionary<K V> und BMultiMap<K V>. Jede dieser Datenstrukturen bieten FindLowerBound() und FindUpperBound() Methoden wie etwa C++'s lower_bound und upper_bound.

    InformationsquelleAutor der Antwort Qwertie

  4. 0
        public static DateTime RoundDown(DateTime dateTime)
    {
        long remainingTicks = dateTime.Ticks % PeriodLength.Ticks;
        return dateTime - new TimeSpan(remainingTicks);
    }

    InformationsquelleAutor der Antwort ChrisG65

Schreibe einen Kommentar