38

我在 a 中有一对日期和货币值SortedDictionary<DateTime, decimal>,对应于在合同定义的复利日期计算到未来的贷款余额。有没有一种有效的方法来找到最接近给定值的日期键?(具体来说,最近的键小于或等于目标)。关键是仅存储值更改时的数据,但有效地回答“x日期的余额是多少?”这个问题。对于范围内的任何日期。

有人问了一个类似的问题(什么 .NET 字典支持“查找最近的键”操作?),当时的答案是“不”,至少来自回答的人,但那是差不多 3 年前的事了。

How to find point between two keys in sorted dictionary提出了天真地遍历所有键的明显解决方案。我想知道是否存在任何内置的框架函数来利用键已经在内存中索引和排序的事实 - 或者是一个内置的框架集合类,它更适合这种查询。

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当然,上述方法只有在构建一次然后重复查询时才有意义;因为它涉及迭代整个键序列并在此之上进行二进制搜索,如果您只搜索一次,那么尝试这个是没有意义的。在那种情况下,即使是简单的迭代也会更好。

更新

正如 digEmAll 正确指出的那样,您还可以切换到SortedList<DateTime, decimal>以便Keys集合实现IList<T>(SortedDictionary.Keys 没有)。该接口提供了足够的功能来手动对其执行二进制搜索,因此您可以使用例如此代码并将其作为IList<T>.

您还应该记住,如果项目未按已排序的顺序插入,则其SortedList性能比SortedDictionary构建期间更差,尽管在这种特殊情况下,日期很可能按时间(排序)顺序插入,这将是完美的。

于 2012-09-13T18:56:38.037 回答
11

因此,这并不能直接回答您的问题,因为您专门要求 .NET 框架内置的东西,但面临类似的问题,我发现以下解决方案效果最好,我想在这里发布它以供其他人使用搜索者。

我使用了TreeDictionary<K, V>来自C5 Collections ( GitHub / NuGet ) 的,它是一个红黑树的实现。

它有Predecessor/TryPredecessorWeakPredessor/TryWeakPredecessor方法(以及类似的后继方法)可以轻松找到离键最近的项目。

我认为,在您的情况下更有用的是RangeFrom//允许您检索键之间的一系列键值对的方法。RangeToRangeFromTo

请注意,所有这些方法也可以应用于TreeDictionary<K, V>.Keys集合,这样您也可以只使用键。

它确实是一个非常简洁的实现,并且应该在 BCL 中包含类似的东西。

于 2013-07-23T15:02:58.480 回答
1

如果您需要将查询与插入相交错(除非您的数据是预先排序的,或者集合总是很小),那么就不可能有效地找到最近的键SortedListSortedDictionary或者任何其他“内置”.NET 类型。

正如我在您引用的另一个问题中提到的那样,我创建了三个与 B+ 树相关的数据结构,它们为任何可排序的数据类型提供查找最近键功能BList<T>BDictionary<K,V>BMultiMap<K,V>. 这些数据结构中的每一个都提供FindLowerBound()FindUpperBound()C++lower_boundupper_bound.

这些在 Loyc.Collections NuGet 包中可用,BDictionary通常使用的内存比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 回答