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

Answer 2

这样做的另一种方式（没有被周围的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] 
    } 

Answer 3

考虑以下方法：

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); 
} 

在我的机器上，结果是和。

Answer 4

我不会在没有性能分析的情况下声明任何性能。在这个答案中，我将尝试实施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. 方法使用附加的存储器/操作，以保存用于索引的顺序。

优势：

• 你可以肯定，它需要一个枚举得到下一个最大值。

See it running