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

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

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

Answer 3

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

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

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

Answer 4

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

Answer 5

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

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 6

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

Answer 7

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

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