对对的有效分类 按价值

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

跟进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

上面那些的替代解决方案 - 当插入到地图中的值时会添加新值，因为新的键/值对会被添加，并在构建地图时构建前三个（asumming你没有从某个地方传递地图外部当然）

Answer 7

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