按值有效地对对<键,值>进行排序

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).如果我有更多的时间,我会为了好玩而做到这一点......