Estrai i k elementi massimi di una lista

Question

diciamo che ho una collezione di qualche tipo, ad es.

IEnumerable<double> values; 

Ora ho bisogno di estrarre i k valori più alti da quella collezione, per un certo parametro k. Questo è un modo molto semplice per farlo:

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

Tuttavia, questo (se ho capito bene) ordina prima l'intero elenco, quindi raccoglie i primi k elementi. Ma se la lista è molto grande, e k è relativamente piccolo (più piccolo di log n), questo non è molto efficiente - la lista è ordinata in O (n * log n), ma immagino di selezionare i k valori più alti da una lista dovrebbe essere più simile a O (n * k).

Quindi, qualcuno ha qualche suggerimento per un modo migliore, più efficiente per farlo?

Answer 1

Questo dà un po 'di un aumento delle prestazioni. Si noti che è ascendente, piuttosto che scendere, ma si dovrebbe essere in grado di riutilizzare (vedi commenti):

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

Un altro modo di fare questo (non sono stati in giro C# per anni, in modo pseudo-codice che è, mi spiace) sarebbe:

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

Si consideri il seguente metodo:

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

E il programma di test:

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

Sui miei risultati macchina sono e .

Answer 4

Non vorrei dire nulla sulle prestazioni senza la creazione di profili. In questa risposta cercherò di implementare l'approccio O(n*k) take-one-enumeration-for-one-max-value. Personalmente ritengo che l'approccio all'ordine sia superiore. Comunque:

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

utilizzati:

var biggestElements = values.GetMaxElements().Take(3); 

Inconvenienti:

1. metodo presuppone che fonte IEnumerable ha un ordine
2. metodo utilizza memoria aggiuntiva/operazioni per salvare indici utilizzati.

Vantaggio:

• Si può essere certi che ci vuole un'enumerazione per ottenere successivo valore max.

See it running