有效地找到最近的字典键 [英] Efficiently find nearest dictionary key

问题描述

我有一堆的日期对和货币价值的 SortedDictionary＆LT;日期时间，小数＆GT; ，对应于合同定义的复利日期计算到未来贷款余额。有找到一个日期键最接近给定的值的有效方法？ （具体地，小于或等于最接近的键的 的目标）。问题的关键是，当值改为只有数据在储存点，但有效地回答什么x上日期的平衡？对范围内的任何日期。

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.

有一个类似的问题被问（<一个href=\"http://stackoverflow.com/questions/1690929/what-net-dictionary-supports-a-find-nearest-key-operation\">What .NET词典支持＆QUOT;找到最近的钥匙＆QUOT;操作），答案是不的时候，至少从谁回答，但是这几乎是3年前的人们。

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.

问题<一href=\"http://stackoverflow.com/questions/5301164/how-to-find-point-between-two-keys-in-sorted-dictionary\">How找到分类字典 presents两个键通按键都天真地迭代显而易见的解决方案之间的点。我想知道如果任何内置框架功能的存在而采取的事实项已编制索引，并在内存中进行排序的优势 - 或可选内置框架的集合类，更好地适合以这种查询

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.

推荐答案

由于 SortedDictionary 是在关键的排序，你可以创建密钥的排序列表以

Since SortedDictionary is sorted on the key, you can create a sorted list of keys with

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

，然后有效地执行二进制搜索就可以了：

var index = keys.BinarySearch(key);

由于文档说，如果首页为正或零，则主要存在;如果是负数，那么〜指数是键将在如果它存在找到了索引。因此，小即现有密钥的指数〜指数 - 1 。确保你正确处理边缘的情况下键比现有的任何按键较小，〜指数 - 1 == -1 。

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.

由于digEmAll正确地指出，你也可以切换到排序列表＆LT;日期时间，小数＆GT; 这样的 键 集合实现的IList＆LT; T＆GT; （这SortedDictionary.Keys不）。该接口提供了足够的功能就可以了手动执行二进制搜索，所以你可以采取例如<一href=\"http://stackoverflow.com/questions/594518/is-there-a-lower-bound-function-in-c-sharp-on-a-sortedlist\">this code 并使其对的扩展方法IList＆LT; T＆GT;

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>.

您也应该记住，排序列表如果项目没有在插入施工过程中的性能比 SortedDictionary 更糟已经排序顺序，但在这个特殊的情况下，极有可能日期插入时间顺序（排序）为了这将是完美的。

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屋！