提取列表的k个最大元素

Question

假设我有一些类型的集合,例如

IEnumerable<double> values;

现在我需要从该集合中提取k个最高值,对于某些参数k.这是一种非常简单的方法:

values.OrderByDescending(x => x).Take(k)

但是,这(如果我理解正确的话)首先对整个列表进行排序,然后选择前k个元素.但是如果列表非常大,并且k相对较小(小于log n),则效率不高 - 列表以O(n*log n)排序,但我想从列表中选择k个最高值应该更像O(n*k).

那么,有没有人建议更好,更有效的方法来做到这一点？

Answer 1

这会带来一点性能提升.请注意,它是升序而不是降序,但您应该可以重新调整它(请参阅注释):

static IEnumerable<double> TopNSorted(this IEnumerable<double> source, int n)
{
    List<double> top = new List<double>(n + 1);
    using (var e = source.GetEnumerator())
    {
        for (int i = 0; i < n; i++)
        {
            if (e.MoveNext())
                top.Add(e.Current);
            else
                throw new InvalidOperationException("Not enough elements");
        }
        top.Sort();
        while (e.MoveNext())
        {
            double c = e.Current;
            int index = top.BinarySearch(c);
            if (index < 0) index = ~index;
            if (index < n)                    // if (index != 0)
            {
                top.Insert(index, c);
                top.RemoveAt(n);              // top.RemoveAt(0)
            }
        }
    }
    return top;  // return ((IEnumerable<double>)top).Reverse();
}