提取列表中的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