.NET - 有效的對排序<key, value>按值

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

檢索（和其他所有操作）具有O（log n）複雜性。

Answer 6

這裏容斯的擴展方法跟進是一個實現

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

的替代解決方案上面 - 作爲值插入到地圖中尋找高值，因爲添加了新的鍵/值對，並在構建地圖時構建前三名（當然，您並沒有將地圖從當然外部遞交給地圖）