6

I have a SortedDictionary 

 SortedDictionary<int, CPUOptimizationObject> myDict;

Now I want to find the first value above X. I can do something like this 

foreach (var iKey in MyDict.Keys)
{
   if (iKey >= thresholdKey)
   {
       foundKey = iKey;
       break;
   }
}

but this isn't good performance wise.
Any better suggestion?
(is there a method for that in the collections something like Binary search for SortedDictionary ?)

Bick
  • 17,833
  • 52
  • 146
  • 251
  • Using a double as key is not a good idea. What are you storing there and why are you using a SortedDictionary if you are looking for the nearest match? What's the actual problem you are trying to solve? – Panagiotis Kanavos Dec 09 '13 at 16:01
  • You could call ToList() and then do BinarySearch or LINQ. But not sure if thats faster. Maybe you can improve your engineering for a better key or other listtype like Panagiotis already said. – Koryu Dec 09 '13 at 16:07
  • you are correct about the double. fixed to int. – Bick Dec 09 '13 at 16:09
  • the double is in an historical piece of code and is translated from 3 characters string. changed it in the question but question remains – Bick Dec 09 '13 at 16:10
  • You cannot use a `BinarySearch` since the [`KeyCollection`-class](http://msdn.microsoft.com/en-us/library/ms132259(v=vs.110).aspx) does not implement `IList`(as an array or list) so it does not allow random access. So i doubt that you can improve it easily. – Tim Schmelter Dec 09 '13 at 16:22
  • See this [similar question](https://stackoverflow.com/questions/12412869/efficiently-find-nearest-dictionary-key) – John Cummings Nov 15 '19 at 17:24

4 Answers4

7

While, in theory, finding the smallest item that is larger than a given value is an operation that can be performed efficiently on a Binary Search Tree (which is what a SortedDictionary is implemented as) SortedDictionary does not expose the means for you to perform such a search on that data type.

You would need to use a different implementation of a Binary Search Tree in order to efficiently perform such a search, while still using the same type of data structure. There are no suitable .NET types; you would need to use a 3rd party implementation (of which there are quite a few out there).

Servy
  • 202,030
  • 26
  • 332
  • 449
0

You could try if this is faster. But I guess it will be faster only if you are performing the search multiple times.

var keys = new List<int>(myDict.Keys);
int index = keys.BinarySearch(thresholdKey);
nawfal
  • 70,104
  • 56
  • 326
  • 368
Koryu
  • 1,371
  • 1
  • 11
  • 21
  • 1
    This will most certainly be slower, without question, unless you're performing multiple searches. – Servy Dec 09 '13 at 16:41
0

create a temp list n using a .toList() on your Sorteddictionary Now since that results a List n you could do 

  n.Find(item =>item >20)

to retrieve the first key in return that matches,

Peter
  • 2,043
  • 1
  • 21
  • 45
-1

I don't know if this has better performance than the foreach, but this should work:

var foo = myDict.FirstOrDefault(i => i.Key > thresholdKey);
Alexandre Machado
  • 579
  • 5
  • 16