.NET - Efficient sorting of pairs<key, value> by value

Question

So, I'm looking for the most efficient way to sort a bunch of pairs<string, float> by value, because I need to get the 3 highest entries of a high number of pairs.

My natural reaction was to use a sortedList, but apparently it only sorts by key, and I cant use the reversed list solution because I know for a fact that the strings are unique, but the floats might not be.

Any simple and efficient solution I am overlooking?

Answer 1

If you only need to know the top three values, you don't need to sort the whole list - you can just perform one pass, storing the top three values at any one time. That will make it O(n) rather than O(n log n)... but you'll have to implement it yourself.

If you're happy with O(n log n) though, the simplest way would probably be to use LINQ:

var ordered = pairs.OrderBy(pair => pair.Value).Take(3).ToList();

It probably wouldn't be too hard to implement something like:

public static IEnumerable<TSource> TakeTop<TSource, TKey>
    (this IEnumerable<TSource> source,
     Func<TSource, TKey> keySelector,
     int count)

which could have a complexity of O(n * count). If I had a bit more time I'd do it for fun...

Answer 2

You could use linq:

yourDictionary.OrderBy(kv => kv.Value).Take(3);

I don't know about the efficiency, but surely it's short and expressive.

Answer 3

Create your own pairs object and implement the IComparable interface, with the comparison based on your value.

Answer 4

I don't know if it's the most efficient but you can try doing:

List<KeyValuePair<string,float>> myList = new List<KeyValuePair<string,float>>():

... //adding whatever...

myList.Sort(delegate(KeyValuePair<string,float> pair1, KeyValuePair<string,float> pair2) { return pair1.Value.CompareTo(pair2.Value); });

Answer 5

If you want a balanced red-black tree, you can find one in C5:

using Bag = C5.TreeBag<C5.KeyValuePair<string, float>>;
using Comparer = C5.DelegateComparer<C5.KeyValuePair<string, float>>;

...

var bag = new Bag(new Comparer(
  (pair1, pair2) => 
    pair1.Value == pair2.Value ? 
    pair1.Key.CompareTo(pair2.Key) :
    // inverted because you need the highest entries 
    pair2.Value.CompareTo(pair1.Value))); 

...

var topN = bag.Take(N).ToList();

Retrieval (and every other operation) has O(log n) complexity.

Answer 6

following up on Jons extension method here's an implementation

public static IEnumerable<TSource> TakeTop<TSource, TKey>
    (this IEnumerable<TSource> source,
     Func<TSource, TKey> keySelector,
     int count)
{
  var top = source.Take(count).OrderBy(keySelector).ToArray();
  var last = count-1;
  foreach(var item in source.skip(count))
  {
    if(keySelector(top[last]) < keySelector(item))
    {
      top[last] = item;
      //depending on count this might be faster as buble sort
      top = top.OrderBy(keySelector).ToArray();
    }
  }
  return top;
}

considere it a draft I've "implemented" it in the SO textbox :)

Answer 7

An alternative solution to those above - as values are inserted into the map look for high values at as new key/value pairs are added and build the top three as the map is being built (asumming you aren't being handed the map from something external of course)