c# - 从已排序的字典中获取值的范围

Question

我有一个以 DateTime 为键的排序字典:

myDictionary = new SortedDictionary<DateTime, float>();

我想实现以下功能:

data[] GetRange(DateTime From, DateTime To)

最快的方法是找到值中的第一个/最后一个索引，然后从一系列值中获取数据

但要做到这一点，我需要找到如何获取“From”和“To”的索引。

有没有办法做到这一点？或者，是否有更快的方法来实现这一目标？

现在我正在寻找一个数组来存放值，并在数据数组中查找一个字典。

Answer 1

鉴于您对高性能的需求，您可能会考虑一种允许对最小值和最大值进行二进制搜索的数据结构。如果SortedDictionary提供了一个索引器 Item[int] ，您可以使用它，但遗憾的是，它没有。

你可以考虑类似的事情

struct PriceAtTime
{
    public DateTime Timestamp { get; set; }
    public float Price { get; set; } // Or whatever your float represents
}

List<PriceAtTime> myData = GetTheData(); // Assumes the provided data is ordered
                                         // by timestamp.

查找包含最小时间戳或之后的第一个数据点的索引:

• 检查我的数据[myData.Count/2]
• 根据该元素时间戳的值，您要么找到它，要么中间元素比最小值更新，因此检查 myData.Count/4，或者它更高，因此检查 3*myData.Count/4。递归重复，直到找到正确的元素。
• 查找不超过最大值的最后一个元素的索引的类似方法。

SortedList<T>听起来像是一个有前途的类型，但实际上，它behaves much like a sorted dictionary ，尤其是对于键控查找。

请注意，我假设列表中的元素被神奇地排序了。自排序数据结构在实时性能环境中可能相当昂贵。如果您可以从任何位置获取已排序的数据，则可以消除另一个性能问题。