假设我有一个某种类型的集合，例如：
IEnumerable<double> values;
values.OrderByDescending(x => x).Take(k)
这会带来一些性能提升。请注意它是升序而不是降序，但你应该能够重新利用它（参见注释）：
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();
}
n log k 是正确的，因为您正在将 n 个二进制插入到大小为 k 的组中。） - RawlingO(n*k*logk)，所以它接近于 OP 的要求。 - default locale请考虑以下方法：
static IEnumerable<double> GetTopValues(this IEnumerable<double> values, int count)
{
var maxSet = new List<double>(Enumerable.Repeat(double.MinValue, count));
var currentMin = double.MinValue;
foreach (var t in values)
{
if (t <= currentMin) continue;
maxSet.Remove(currentMin);
maxSet.Add(t);
currentMin = maxSet.Min();
}
return maxSet.OrderByDescending(i => i);
}
测试程序如下：
static void Main()
{
const int SIZE = 1000000;
const int K = 10;
var random = new Random();
var values = new double[SIZE];
for (var i = 0; i < SIZE; i++)
values[i] = random.NextDouble();
// Test values
values[SIZE/2] = 2.0;
values[SIZE/4] = 3.0;
values[SIZE/8] = 4.0;
IEnumerable<double> result;
var stopwatch = new Stopwatch();
stopwatch.Start();
result = values.OrderByDescending(x => x).Take(K).ToArray();
stopwatch.Stop();
Console.WriteLine(stopwatch.ElapsedMilliseconds);
stopwatch.Restart();
result = values.GetTopValues(K).ToArray();
stopwatch.Stop();
Console.WriteLine(stopwatch.ElapsedMilliseconds);
}
在我的电脑上，结果是1002和14。
double.MinValue而不是0来初始化列表，例如：var maxSet = new List<double>(Enumerable.Repeat(double.MinValue, count)); :-) - sloth另一种做法（我已经好几年没接触C#了，所以只能用伪代码，抱歉）是：
highestList = []
lowestValueOfHigh = 0
for every item in the list
if(lowestValueOfHigh > item) {
delete highestList[highestList.length - 1] from list
do insert into list with binarysearch
if(highestList[highestList.length - 1] > lowestValueOfHigh)
lowestValueOfHigh = highestList[highestList.length - 1]
}
没有性能分析，我不会发表任何关于性能的言论。在这个答案中，我将尝试实现O(n*k)一个最大值对应一个枚举的方法。个人认为排序法更加优越。无论如何：
public static IEnumerable<double> GetMaxElements(this IEnumerable<double> source)
{
var usedIndices = new HashSet<int>();
while (true)
{
var enumerator = source.GetEnumerator();
int index = 0;
int maxIndex = 0;
double? maxValue = null;
while(enumerator.MoveNext())
{
if((!maxValue.HasValue||enumerator.Current>maxValue)&&!usedIndices.Contains(index))
{
maxValue = enumerator.Current;
maxIndex = index;
}
index++;
}
usedIndices.Add(maxIndex);
if (!maxValue.HasValue) break;
yield return maxValue.Value;
}
}
使用方法：
var biggestElements = values.GetMaxElements().Take(3);
缺点：
优点：
PriorityQueue<TElement, TPriority> 集合的可枚举序列 Linqy TopN 操作符：/// <summary>
/// Selects the top N elements from the source sequence. The selected elements
/// are returned in descending order.
/// </summary>
public static IEnumerable<T> TopN<T>(this IEnumerable<T> source, int n,
IComparer<T> comparer = default)
{
ArgumentNullException.ThrowIfNull(source);
if (n < 1) throw new ArgumentOutOfRangeException(nameof(n));
PriorityQueue<bool, T> top = new(comparer);
foreach (var item in source)
{
if (top.Count < n)
top.Enqueue(default, item);
else
top.EnqueueDequeue(default, item);
}
List<T> topList = new(top.Count);
while (top.TryDequeue(out _, out var item)) topList.Add(item);
for (int i = topList.Count - 1; i >= 0; i--) yield return topList[i];
}
使用示例：
IEnumerable<double> topValues = values.TopN(k);
topValues 序列包含 values 中前 k 个最大的值，按降序排列。如果在 topValues 中存在重复的值，则相等值的顺序是未定义的（非稳定排序）。
对于基于 SortedSet<T> 的实现，可以查看此答案的 第5版，它可以在 .NET 6 之前的版本上编译。
在编程方面，PartialSort 操作符与 MoreLinq 包中的操作符功能类似。但是它的实现并不是最优的（源代码）。它对于每个项目都执行二进制搜索，而不是将其与 top 列表中的最小项进行比较，导致比必要的更多的比较。
令人惊讶的是，LINQ本身对于OrderByDescending+Take组合进行了良好的优化，从而实现了出色的性能。它只比上面的TopN运算符稍慢一点。这适用于所有版本的.NET Core以及之后的版本（.NET 5和.NET 6）。但在.NET Framework平台上不适用，其复杂度如预期的O(n*log n)。
可以在这里找到一个比较4种不同方法的演示。
values.OrderByDescending(x => x).Take(k)。values.OrderByDescending(x => x).HideIdentity().Take(k)，其中HideIdentity是一个微不足道的LINQ传播器，它隐藏了基础可枚举对象的身份，因此有效地禁用了LINQ优化。values.PartialSort(k, MoreLinq.OrderByDirection.Descending)（MoreLinq）。values.TopN(k)以下是在.NET 6上以发布模式运行时演示的典型输出：
.NET 6.0.0-rtm.21522.10
Extract the 100 maximum elements from 2,000,000 random values, and calculate the sum.
OrderByDescending+Take Duration: 156 msec, Comparisons: 3,129,640, Sum: 99.997344
OrderByDescending+HideIdentity+Take Duration: 1,415 msec, Comparisons: 48,602,298, Sum: 99.997344
MoreLinq.PartialSort Duration: 277 msec, Comparisons: 13,999,582, Sum: 99.997344
TopN Duration: 62 msec, Comparisons: 2,013,207, Sum: 99.997344
OrderBy(...).Take(...)的低效率点个赞。我在这里和其他地方看到的OrderBy(...).First()的次数令人沮丧。如果微软将其纳入LINQ中，并通过对Take、First等进行特殊重载来处理IOrderedEnumerable，那将会很有趣。 - Rawling