Эффективная сортировка пар<ключ, значение> по значению

Question

Я ищу наиболее эффективный способ сортировки pairs<string, float> по значению, потому что мне нужно получить 3 самых высоких записи большого количества пар.

Моя естественная реакция состояла в том, чтобы использовать sortedList, но, видимо, он сортирует только по ключам, и я не могу использовать решение с обратным списком, потому что я точно знаю, что строки уникальны, а значения с плавающей запятой могут и не быть.

Любое простое и эффективное решение, которое я пропускаю?

Answer 1

Если вам нужно знать только три верхних значения, вам не нужно сортировать весь список - вы можете просто выполнить один проход, сохраняя три верхних значения одновременно. Это сделает его O(n), а не O(n log n)... но вам придется реализовать это самостоятельно.

Если вы довольны O (n log n), возможно, самый простой способ - использовать LINQ:

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

Вероятно, было бы не так сложно реализовать что-то вроде:

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

который может иметь сложность O(n * count). Если бы у меня было немного больше времени, я бы сделал это для удовольствия...

Answer 2

Вы можете использовать linq:

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

Я не знаю об эффективности, но, конечно, она короткая и выразительная.

Answer 3

Создайте свой собственный объект пар и реализуйте интерфейс IComparable со сравнением, основанным на вашем значении.

Answer 4

Вслед за методом расширения Джонса вот реализация

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;
}

Считайте, что это черновик, я "реализовал" его в текстовом поле SO:)

Answer 5

Я не знаю, является ли это наиболее эффективным, но вы можете попробовать сделать:

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 6

Альтернативное решение вышеперечисленным - когда значения вставляются в карту, ищите высокие значения при добавлении новых пар ключ / значение и создавайте первые три при построении карты (если вы не получили карту от чего-либо внешний конечно)

Answer 7

Если вы хотите сбалансированное красно-черное дерево, вы можете найти его в 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();

Извлечение (и любая другая операция) имеет сложность O(log n).