提取列表的最大k个元素

本文关键字：元素 列表 提取 | 更新日期: 2023-09-27 18:01:05

假设我有某种类型的集合，例如

IEnumerable<double> values;

现在，我需要从该集合中提取k个最高值，用于一些参数k。这是一种非常简单的方法：

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

然而，这(如果我理解正确的话(首先对整个列表进行排序，然后选择前k个元素。但是，如果列表很大，而k相对较小(小于logn(，这就不是很有效了-列表按O(nlogn(排序，但我认为从列表中选择k个最高值应该更像O(nk(。

那么，有人对更好、更有效的方法有什么建议吗？

提取列表的最大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();
}

考虑以下方法：

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。

实现这一点的另一种方法(多年来没有使用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);

不利因素：

  1. 方法假定源IEnumerable具有顺序
  2. 方法使用额外的内存/操作来保存已使用的索引

优势：

  • 您可以确定，需要一个枚举才能获得下一个最大值

看到它运行

这是一个基于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中存在重复值，则相等值的顺序是未定义的(非稳定排序(。

对于在.NET 6之前的.NET版本上编译的基于SortedSet<T>的实现，您可以查看此答案的第5次修订版。

MoreLinq软件包中存在具有类似功能的运算符PartialSort。但它并没有以最佳方式实现(源代码(。它总是对每个项目执行二进制搜索，而不是将其与top列表中最小的项目进行比较，从而导致比必要的比较多得多的比较。

令人惊讶的是，LINQ本身针对OrderByDescending+Take组合进行了良好的优化，从而获得了优异的性能。它只比上面的TopN操作符稍微慢一点。这适用于.NET Core及更高版本(.NET 5和.NET 6(的所有版本。它不适用于.NET Framework平台，该平台的复杂性如预期的那样为O(n*logn(。

在这里可以找到一个比较4种不同方法的演示。相比之下：

  1. values.OrderByDescending(x => x).Take(k)
  2. values.OrderByDescending(x => x).HideIdentity().Take(k)，其中HideIdentity是一个微不足道的LINQ传播器，它隐藏了底层可枚举对象的身份，因此它有效地禁用了LINQ优化
  3. values.PartialSort(k, MoreLinq.OrderByDirection.Descending)(MoreLinq(
  4. values.TopN(k)

以下是演示的典型输出，在.NET6:上以发布模式运行

.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
相关文章：