在C#中,是否有一种SortedList <double>允许快速查询(使用LINQ)最近的值？

Question

我正在寻找一个包含一组有序的双值的结构.我想查询此集合以查找与指定参考值最接近的值.

我看过了SortedList<double, double>,对我来说确实很好.但是,因为我不需要明确的键/值对.这似乎对我来说太过分了,我想知道我能不能做得更快.

条件:

• 结构只初始化一次,永远不会改变(没有插入/删除)
• 值的数量在100k的范围内.
• 通常使用新引用来查询结构,这些引用必须快速执行.
• 为了简单和速度,可以返回低于参考值的集合值,而不是实际上最接近的值
• 我想在可能的情况下使用LINQ进行查询,以简化代码.
• 我想尽可能不使用第三方代码..NET 3.5可用.
• 速度比内存占用更重要

我目前使用以下代码,SortedValues前面提到的SortedList

    IEnumerable<double> nearest = from item in SortedValues.Keys
                                  where item <= suggestion
                                  select item;
    return nearest.ElementAt(nearest.Count() - 1);

我能做得更快吗？

如果这段代码非常安全,我也不是100%肯定的.IEnumerable,我的查询的返回类型不再按定义排序.但是,具有大型测试数据库的单元测试表明它在实践中,所以这对我有用.你有关于这方面的提示吗？

PS我知道有很多类似的问题,但没有一个真正满足我的具体需求.特别是有一个C#数据结构像字典但没有值,但提问者只是想检查存在没找到任何东西.

Answer 1

你这样做的方式非常慢,因为它必须每次从列表的开头搜索O(n)性能.

更好的方法是将元素放入List中,然后对列表进行排序.您说初始化后不需要更改内容,因此排序一次就足够了.

然后,您可以使用List<T>.BinarySearch查找元素或查找元素的插入点(如果该元素尚不存在于列表中).

来自文档:

回报价值

List<T>找到sorted ,if项中从零开始的项索引; 否则,负数是下一个元素的索引的按位补码,大于项,或者,如果没有更大的元素,则为Count的按位补码.

获得插入点后,需要检查两侧的元素以查看哪个最接近.