我在a中有一堆日期和货币值SortedDictionary<DateTime, decimal>,对应于在合约定义的复利日期计算到未来的贷款余额.有没有一种有效的方法来查找最接近给定值的日期键？(具体而言,最接近的键小于或等于目标).关键是在值改变时仅存储数据,但有效地回答"x日期的余额是什么？"的问题.对于范围内的任何日期.
一个类似的问题被问到(.NET字典支持"查找最近的密钥"操作？)当时答案是"不",至少来自响应的人,但那是差不多3年前的事.
如何在排序字典中找到两个键之间的点的问题提出了天真地遍历所有键的明显解决方案.我想知道是否存在任何内置框架函数来利用密钥已经在内存中索引和排序的事实 - 或者内置的Framework集合类,它将更好地适应这种类型的查询.
是否有下限功能SortedList<K ,V>？该函数应返回等于或大于指定键的第一个元素.还有其他类支持这个吗？
伙计们 - 请再次阅读这个问题.如果它存在,我不需要返回键的函数.当没有确切的密钥匹配时,我对场景感兴趣.
我对O(log n)时间感兴趣.这意味着我没有foreach循环的问题,而是希望有一个有效的方法来做到这一点.
我对此做了一些测试.
Linq语句既不是编译器也不是运行时机器优化的,因此它们遍历所有集合元素并且速度慢O(n).根据Mehrdad Afshari的回答,这里是一个二进制搜索,它在Keys集合的O(log n)中工作:
public static int FindFirstIndexGreaterThanOrEqualTo<T>(
this IList<T> sortedCollection, T key
) where T : IComparable<T> {
int begin = 0;
int end = sortedCollection.Count;
while (end > begin) {
int index = (begin + end) / 2;
T el = sortedCollection[index];
if (el.CompareTo(key) >= 0)
end = index;
else
begin = index + 1;
}
return end;
}