.NET - Эффективная сортировка пар <key, value> по значению

Question

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

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

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

Answer 1

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

Если вы счастливы с O (N журнал 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 interface со сравнением, основанным на вашем значении.

Answer 4

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

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

Если вы хотите сбалансированный red-black tree, вы можете найти один в 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 (и любая другая операция) имеет сложность O (log n).

Answer 6

следующий на метод расширения 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; 
} 

considere это проект Я «реализован» его в текстовое поле SO :)

Answer 7

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