38

SortedDictionary<DateTime, decimal>には、契約で定義された複利の日付で将来に計算されたローン残高に対応する、日付と金銭的価値のペアがたくさんあります。特定の値に最も近い日付キーを見つける効率的な方法はありますか？（具体的には、ターゲット以下の最も近いキー）。ポイントは、値が変更された時点のデータのみを保存することですが、「x日の残高はどのくらいでしたか？」という質問に効率的に答えることです。範囲内の任意の日付。

同様の質問があり（「最も近いキーを見つける」操作をサポートする.NET辞書はどれですか？）、少なくとも回答した人からは、その時点で「いいえ」と答えましたが、それはほぼ3年前のことです。

ソートされた辞書で2つのキー間のポイントを見つける方法という質問は、すべてのキーを単純に反復するという明白な解決策を示しています。キーがすでにメモリ内でインデックス付けおよびソートされているという事実を利用するための組み込みフレームワーク関数が存在するかどうか、あるいはこの種のクエリに適した組み込みフレームワークコレクションクラスが存在するかどうか疑問に思っています。

4

4 に答える 4

34

はキーでソートされているためSortedDictionary、次のコマンドでソートされたキーのリストを作成できます。

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

次に、その上で効率的に二分探索を実行します。

var index = keys.BinarySearch(key);

ドキュメントに記載されているように、indexが正またはゼロの場合、キーが存在します。負の場合は、それが存在した場合に検出される~indexインデックスです。keyしたがって、「すぐに小さい」既存のキーのインデックスはです~index - 1。key既存のキーおよびのいずれよりも小さいエッジケースを正しく処理するようにしてください~index - 1 == -1。

もちろん、上記のアプローチは、keys一度構築されてから繰り返し照会された場合にのみ意味があります。キーのシーケンス全体を反復処理し、その上でバイナリ検索を実行する必要があるため、1回だけ検索する場合は、これを試してみても意味がありません。その場合、単純な反復でさえも良いでしょう。

アップデート

digEmAllが正しく指摘してSortedList<DateTime, decimal>いるように、Keysコレクションが実装されるように切り替えることもできますIList<T>（SortedDictionary.Keysは実装しません）。このインターフェイスは、手動でバイナリ検索を実行するのに十分な機能を提供するため、たとえばこのコードを使用して、の拡張メソッドにすることができますIList<T>。

SortedListまた、アイテムがすでに並べ替えられた順序で挿入されていない場合、建設中よりもパフォーマンスが低下することにも注意してくださいSortedDictionary。ただし、この特定のケースでは、日付が時系列（並べ替え）の順序で挿入される可能性が高く、完璧です。

于 2012-09-13T18:56:38.037 に答える
11

.NET Frameworkに組み込まれているものを具体的に要求したため、これはあなたの質問に直接答えることはできませんが、同様の問題に直面して、次の解決策が最適であることがわかりました。他の人のためにここに投稿したいと思います。サーチャー。

赤黒木の実装であるC5コレクション（GitHub / NuGet ）のを使用しTreeDictionary<K, V>ました。

キーに最も近いアイテムを簡単に見つけるためのPredecessor/TryPredecessorおよびWeakPredessor/TryWeakPredecessorメソッド（および後継者用の同様のメソッド）があります。

あなたの場合、私が思うに、より便利なのは、キー間のキーと値のペアの範囲を取得できる//メソッドですRangeFrom。RangeToRangeFromTo

これらのメソッドはすべてTreeDictionary<K, V>.Keysコレクションにも適用できることに注意してください。これにより、キーのみを操作することもできます。

それは本当に非常にきちんとした実装であり、そのようなものはBCLに含まれるに値します。

于 2013-07-23T15:02:58.480 に答える
1

クエリを挿入でインターリーブする必要がある場合（データが事前に並べ替えられて到着するか、コレクションが常に小さい場合を除く）、、またはその他の「組み込み」.NETタイプでSortedList最も近いキーを効率的に見つけることはできません。SortedDictionary

あなたが参照した他の質問で述べたように、私はB +ツリーに関連する3つのデータ構造を作成しました。これらのデータ構造は、並べ替え可能なデータ型に最も近いキーの検索機能を提供BList<T>しBDictionary<K,V>ますBMultiMap<K,V>。これらの各データ構造は、 C++やのように機能するメソッドを提供FindLowerBound()します。FindUpperBound()lower_boundupper_bound

これらはLoyc.CollectionsNuGetパッケージで利用可能であり、BDictionary通常、よりも約44％少ないメモリを使用しますSortedDictionary。

于 2014-12-26T05:12:33.600 に答える
0 
    public static DateTime RoundDown(DateTime dateTime)
    {
        long remainingTicks = dateTime.Ticks % PeriodLength.Ticks;
        return dateTime - new TimeSpan(remainingTicks);
    }
于 2015-10-17T22:11:10.910 に答える