如何在排序字典中找到两个键之间的点

Question

我有一个排序字典，其中包含作为键/值对的测量数据点。为了确定非测量数据点的值，我想使用对应值的线性插值来推断两个已知键之间的值。一旦我拥有了位于其之间的两个键/值对，我就了解如何计算非测量数据点。我不知道的是如何找出它位于哪些键之间。有没有比“for”循环（我正在考虑函数/LINQ 查询）更优雅的方法来找出我的数据点位于哪两个键之间？

Answer 1

像这样的东西会起作用：

 dic.Keys.Zip(dic.Keys.Skip(1), 
              (a, b) => new { a, b })
         .Where(x => x.a <= datapoint && x.b >= datapoint)
         .FirstOrDefault();

这会使用它们是有序的这一事实来遍历它们的键，并按顺序比较彼此后面的所有两个键 - 因为 LINQ 是惰性的，一旦找到第一个匹配项，遍历就会停止。

Answer 2

标准 C# 答案的复杂度都是 O(N)。
有时您只需要相当大的排序集合中的一个小子集。 （所以你没有迭代所有的键）
标准 C# 集合在这里无法为您提供帮助。并且解决方案如下：
http://www.itu.dk/research/c5/ 在 C5 中使用 IntervalHeap馆藏图书馆。此类支持 GetRange() 方法，并且将以 O(log N) 复杂度查找起始键，并以 O(N) 复杂度迭代范围。如果性能至关重要的话，这对于大数据集绝对有用。例如游戏中的空间分区

Answer 3

您可能会问以下问题：

myDictionary.Keys.Where(w => w > start && w < end)

Answer 4

常规循环在这里应该没问题：

IEnumerable<double> keys = ...; //ordered sequence of keys
double interpolatedKey = ...;

// I'm considering here that keys collection doesn't contain interpolatedKey

double? lowerFoundKey = null;
double? upperFoundKey = null;

foreach (double key in keys)
{
    if (key > interpolatedKey)
    {
        upperFoundKey = key;
        break;
    }
    else
        lowerFoundKey = key;
}

您可以使用更短但效率较低的代码在 C# 中使用 LINQ 来完成此操作：

double lowerFoundKey = key.LastOrDefault(k => k < interpolatedKey);
double upperFoundKey = key.FirstOrDefault(k => k > interpolatedKey);

为了有效地使用 LINQ，它应该有一个名为 在 F# 中使用参数 2 进行窗口化。它将返回 keys< 中相邻对的 IEnumerable /代码> 集合。虽然 LINQ 中缺少此函数，但常规 foreach 循环应该没问题。

Answer 5

我认为 SortedDictionary 上没有一个函数可以让您比迭代元素更快地找到所需元素周围的元素。 （+1 到 BrokenGlass 解决方案）

为了能够更快地找到物品，您需要切换到其他结构。即 SortedList 提供类似的功能，但允许索引其 Key 集合，因此您可以使用二进制搜索来查找范围。