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

所以，我正在寻找最有效的方法来按值排序一堆pairs<string, float>，因为我需要获得大量对的3个最高的条目。我的自然反应是使用sortedList，但显然它只按键进行排序，我不能使用反转列表解决方案，因为我知道字符串是唯一的，但浮点数可能不是。.NET - 有效的对排序<key, value>按值

我忽略了任何简单而有效的解决方案吗？

来源

2010-02-05 brokencoding

为什么不用你使用sortedList自定义比较器进行排序吗？ – anthares 2010-02-05 17:48:33

您使用的是什么C＃版本？ – 2010-02-05 17:50:03

我使用.NET框架3.5 – brokencoding 2010-02-05 17:54:13

如果您只需要知道前三个值，则不需要对整个列表进行排序 - 只需执行一次通过，即可在任意时间存储前三个值。这将使它成为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）的复杂性。如果我有一点更多的时间我会做的乐趣...

来源

2010-02-05 17:48:22

O（1）或胸围！ – 2010-02-05 19:03:58

为什么不是O（0）？ :) – LBushkin 2010-02-05 19:18:33

要获得更多乐趣，请尝试执行O（n +（count-1）* log n）算法。 – 2010-02-05 20:24:52

你可以使用LINQ：

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

我不知道的效率做的，但肯定是短期和表现力。

来源

2010-02-05 17:48:57

创建您自己的对象并实现IComparable interface，并根据您的值进行比较。

来源

2010-02-05 17:49:34

我不知道这是否是最有效的，但你可以尝试做：

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

来源

2010-02-05 17:52:47 McAden

如果你想有一个平衡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）复杂性。

来源

2010-02-05 18:35:38

这里容斯的扩展方法跟进是一个实现

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文本:)“实施”它

来源

2010-02-05 18:58:02

的替代解决方案上面 - 作为值插入到地图中寻找高值，因为添加了新的键/值对，并在构建地图时构建前三名（当然，您并没有将地图从当然外部递交给地图）

来源

2010-02-05 19:30:37 Paolo

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

回答

相关问题