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

我有一个已排序字典，其中包含测量数据点作为键/值对。要确定非测量数据点的值，我想使用相应值的线性插值来推断两个已知键之间的值。我知道如何计算非测量数据点，只要我有两个键/值对之间。我不知道的是如何找出它介于哪个键之间。有没有比“for”循环更优雅的方式（我在想功能/ LINQ查询）来找出我的数据点之间的哪两个键？如何在已排序字典中的两个键之间找到点

来源

2011-03-14 Joel B

如果您正在寻找类似linq的解决方案，请尝试http://stackoverflow.com/questions/2768834/how-to-zip-one-ienumerable-with-itself – Douglas 2011-03-14 16:15:54

像这样的工作：

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

这遍历使用，它们是有序的事实，他们键和每个以下全部两个键进行比较其他的顺序 - 因为一旦你找到第一场比赛，LINQ很懒，遍历就会停止。

来源

2011-03-14 16:16:26 BrokenGlass

可能你问下：

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

来源

2011-03-14 16:09:01 Vitaliy

不会是最如果它测试了所有的密钥，可能的有效方法。 – 2011-03-14 16:11:00

定期回路应确定在这里：

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它应该有与参数2一起被称为windowed in F#的方法。它将返回keys集合中相邻对的IEnumerable。 LINQ常规foreach循环应该没问题。

来源

2011-03-14 16:16:46 Snowbear

'Seq.pairwise'对于F＃解决方案就足够了，'Seq.windowed'是那个更通用的版本（任何窗口大小）。 – BrokenGlass 2011-03-14 16:31:56

@BrokenGlass，谢谢，已经从其他答案中得到了答案。 – Snowbear 2011-03-14 16:33:51

我不认为在SortedDictionary上有一个函数可以让你找到你需要的元素比迭代元素更快。（+1到BrokenGlass解决方案）

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

来源

2011-03-14 16:30:10

标准C＃答案都是O（N）复杂度。有时你只需要一个相当大的排序集合中的一个小子集。（所以你没有迭代所有的键）标准的C＃集合不会帮你在这里。解决方案如下： http://www.itu.dk/research/c5/使用C5集合库中的IntervalHeap。这个类支持一个GetRange（）方法，并将查找O（log N）复杂度的startkey，并以O（N）复杂度迭代该范围。如果性能非常关键，那么这对于大数据集来说肯定会有用。例如游戏中的空间分区

来源

2012-10-12 20:50:36 user1190841

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

回答

相关问题