如何在已排序字典中的兩個鍵之間找到點

我有一個已排序字典，其中包含測量數據點作爲鍵/值對。要確定非測量數據點的值，我想使用相應值的線性插值來推斷兩個已知鍵之間的值。我知道如何計算非測量數據點，只要我有兩個鍵/值對之間。我不知道的是如何找出它介於哪個鍵之間。有沒有比「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

如何在已排序字典中的兩個鍵之間找到點

回答

相關問題