有效找到最近的字典键 [英] Efficiently find nearest dictionary key
问题描述
我在一个 SortedDictionary< DateTime，decimal> 中有一堆日期和货币值，对应于未来在合约定义的复合日期计算的贷款余额。有没有找到最接近给定值的日期键的有效方法？ （具体来说，最近的键小于或等于目标的）。要点是在数值改变的时候只存储数据，而是有效地回答x日期的余额是多少的问题。对于范围内的任何日期。
提出了类似的问题（什么.NET字典支持查找最近的键操作？），答案当时是否，至少从响应的人，但是差不多3年前。
问题如何在排序字典中的两个键之间找到点，提供了天真地遍历所有键的明显解决方案。我想知道是否存在任何内置的框架函数，以利用密钥已经在内存中进行索引和排序的事实 - 或者内置的Framework集合类可以更好地适应这种查询。 / p>
由于 SortedDictionary 按键排序，您可以创建一个排序
的键列表var keys = new List< DateTime>（dictionary.Keys）;
然后高效地执行二进制搜索：
var index = keys.BinarySearch（键）;
如文档所述，如果 index 正或零，则键存在;如果是否定的，那么〜index 是索引，其中 key 将被存在。因此，现在更小的现有密钥的索引是〜index - 1 。确保您正确处理键小于任何现有键的边缘情况，并且〜index - 1 == -1
当然，如果键建立一次，然后查询，上述方法真的有意义反复;因为它涉及遍历整个密钥序列，并进行二进制搜索，如果你只想搜索一次就没有任何意义。在这种情况下，即使天真的迭代也会更好。
更新
正如digEmAll正确指出的，你也可以切换到 SortedList< DateTime，decimal> ，以便 键 集合实现 IList< T> （SortedDictionary.Keys没有） 。该界面提供足够的功能来手动执行二进制搜索，因此您可以使用此代码，并使它是 IList< T> 的扩展方法。
您还应该记住， SortedList 在构造期间比 SortedDictionary 执行得更糟糕，如果项目未按已排序的顺序插入，尽管在这种特殊情况下很有可能日期按时间顺序（排序）顺序插入，这将是完美的。
I have a bunch of pairs of dates and monetary values in a SortedDictionary<DateTime, decimal>, corresponding to loan balances calculated into the future at contract-defined compounding dates. Is there an efficient way to find a date key that is nearest to a given value? (Specifically, the nearest key less than or equal to the target). The point is to store only the data at the points when the value changed, but efficiently answer the question "what was the balance on x date?" for any date in range.
A similar question was asked ( What .NET dictionary supports a "find nearest key" operation? ) and the answer was "no" at the time, at least from the people who responded, but that was almost 3 years ago.
The question How to find point between two keys in sorted dictionary presents the obvious solution of naively iterating through all keys. I am wondering if any built-in framework function exists to take advantage of the fact that the keys are already indexed and sorted in memory -- or alternatively a built-in Framework collection class that would lend itself better to this kind of query.
Since SortedDictionary is sorted on the key, you can create a sorted list of keys with
var keys = new List<DateTime>(dictionary.Keys);
and then efficiently perform binary search on it:
var index = keys.BinarySearch(key);
As the documentation says, if index is positive or zero then the key exists; if it is negative, then ~index is the index where key would be found at if it existed. Therefore the index of the "immediately smaller" existing key is ~index - 1. Make sure you handle correctly the edge case where key is smaller than any of the existing keys and ~index - 1 == -1.
Of course the above approach really only makes sense if keys is built up once and then queried repeatedly; since it involves iterating over the whole sequence of keys and doing a binary search on top of that there's no point in trying this if you are only going to search once. In that case even naive iteration would be better.
Update
As digEmAll correctly points out, you could also switch to SortedList<DateTime, decimal> so that the Keys collection implements IList<T> (which SortedDictionary.Keys does not). That interface provides enough functionality to perform a binary search on it manually, so you could take e.g. this code and make it an extension method on IList<T>.
You should also keep in mind that SortedList performs worse than SortedDictionary during construction if the items are not inserted in already-sorted order, although in this particular case it is highly likely that dates are inserted in chronological (sorted) order which would be perfect.
这篇关于有效找到最近的字典键的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
