Wie die oben mehrere Werte aus einem Array zu finden?

Question

Ich habe ein Array von Float-Werten und will den Wert und was noch wichtiger ist die Position der maximalen vier Werte.

baute ich das System ursprünglich durch das Feld zu gehen und das Max die übliche Art und Weise finden, indem Sie den Wert an der aktuellen Position zu einem aufgezeichneten max-so-weit zu vergleichen und Aktualisieren einer Position variabel, wenn die max-so-weit Änderungen. Dies funktionierte gut, eine O (n) algo, die sehr einfach war. Später erfuhr ich, dass ich nicht nur den Top-Wert zu halten brauchen, aber die ersten drei oder vier. Ich erweiterte das gleiche Verfahren und erschwerte die max-so-weit in eine Reihe von vier Max-so-fars und jetzt der Code ist hässlich.

Es funktioniert immer noch und ist noch ausreichend schnell, weil nur eine triviale Menge an Berechnungen zu dem Verfahren hinzugefügt wurde. es noch geht effektiv das Array über und prüft einmal jeden Wert.

Ich tue dies in MATLAB mit einer Sortierfunktion, die zwei Arrays zurückgibt, der sortierten Liste und der zugehörigen Original-Positionsliste. Mit Blick auf den ersten paar Werte habe ich genau das, was ich brauche. Ich replizieren diese Funktionalität in ein C # .NET 2.0-Programm.

Ich weiß, dass ich etwas ähnliches mit einem List-Objekt tun konnte, und dass das List-Objekt ein eingebaute Sortierroutine hat, aber ich glaube nicht, dass es mir die ursprünglichen Positionen sagen kann, und das ist wirklich das, was ich bin nach .

Es hat gut funktioniert, aber jetzt finde ich mich den fünften Maximalwert zu wollen und sehen, dass der max-so-far-Checker Umschreiben, die derzeit eine hässliche Verwirrung der ist, wenn Aussagen würden nur die Hässlichkeit Verbindung. Es würde gut funktionieren und sein nicht langsamer eine fünfte Ebene hinzuzufügen, aber ich will die Gemeinschaft SO fragen, ob es einen besseren Weg gibt.

Die Sortierung der gesamte Liste nimmt viele mehr Berechnungen als meine aktuelle Methode, aber ich glaube nicht, dass es ein Problem wäre, wie die Liste ist ‚nur‘ ein oder zweitausend Schwimmer; so, wenn es eine Art Routine ist, die die ursprünglichen Positionen zurück geben kann, das wäre ideal.

Als Hintergrund Dieses Array ist das Ergebnis einer Fourier-Transformation an einem Kilobyte von Wellenumwandlungsdatei, so dass die Positionen entsprechen max Werte auf die Spitzenfrequenzen der Abtastdaten. Ich hatte damit begnügt, mit den Top vier, sondern eine Notwendigkeit sehen, um wirklich die Top fünf oder sechs für eine genauere Klassifizierung Probe zu sammeln.

Answer 1

Ich kann einen alternativen Algorithmus vorschlagen, die Sie Code haben werden:)

einen Haufen Größe K verwenden, wobei K die Anzahl der oberen Elemente bezeichnet die Sie speichern möchten. Initialisieren Sie diese auf die ersten K Elemente des ursprünglichen Arrays. Für alle N - K Elemente wandeln das Array, das Einfügen und bei Bedarf

.

proc top_k (array<n>, heap<k>)
heap <- array<1..k-1>
for each (array<k..n-1>) 
  if array[i] > heap.min
     heap.erase(heap.min)
     heap.insert(array[i])
  end if
end for

Answer 2

Sie können noch Ihre Liste Idee verwenden - die Elemente, die Sie in der Liste setzen könnte eine Struktur sein, die sowohl den Index und den Wert speichert; aber sortiere nur auf dem Wert, zum Beispiel:

class IndexAndValue : IComparable<IndexAndValue>
{
    public int index;
    public double value;

    public int CompareTo(IndexAndValue other)
    {
        return value.CompareTo(other.value);
    }
}

Dann können Sie sie in der Liste bleiben, während die Informationen über den Index zu halten. Wenn Sie nur die größten m Elemente in der Liste zu halten, dann sollten Sie Ihre Effizienz sein O (mn).

Answer 3

Ich weiß nicht, welcher Algorithmus Sie derzeit verwenden, aber ich werde eine einfache vorschlagen. Zugegeben, dass Sie eine Reihe von Schwimmern f haben und maximal capacity Zahlen, können Sie Folgendes tun:

int capacity = 4; // number of floats you want to retrieve
float [] f; // your float list
float [] max_so_far = new float[capacity]; // max so far

// say that the first 'capacity' elements are the biggest, for now
for (int i = 0; i < capacity; i++)
  max_so_far[i] = i;

// for each number not processed
for (int i = capacity; i < f.length; i++)
{
  // find out the smallest 'max so far' number
  int m = 0;
  for (int j = 0; j < capacity; j++)
    if (f[max_so_far[j]] < f[max_so_far[m]])
      m = j;

  // if our current number is bigger than the smallest stored, replace it
  if (f[i] > f[max_so_far[m]])
    max_so_far[m] = i;
}

Am Ende des Algorithmus, werden Sie die Indizes der größten Elemente gespeichert in max_so_far.

Sie beachten Sie, dass, wenn der capacity Wert wächst, wird es etwas langsamer als die Alternative, das die Liste ist, während das Sortieren des Überblick über die Ausgangspositionen zu halten. Denken Sie daran, dass Sortierung nimmt O (n log n) Vergleiche, während dieser Algorithmus O nimmt (n Kapazität).

Answer 4

Eine andere Möglichkeit ist, schnell wählen zu verwenden. Quick-Select gibt die Position des k-te Element in einer Liste. Nachdem Sie die Position und den Wert des k-ten Element haben, die Liste durchgehen und jedes Element, dessen Wert nehmen kleiner / größer als die k-te Element.

Ich fand ac # -Implementierung von Quick-Select hier: Link-Text

Vorteile:

1. O (n + k) mittlere Laufzeit.

Nachteile:

1. Die k Elemente zu finden sind nicht sortiert. Wenn Sie sie sortieren die Laufzeit O (n + logk)
2. Ich habe nicht geprüft, aber ich denke, dass für ein sehr kleines k die beste Option k läuft über das Feld zu tun, jedes Mal das nächste kleinste / größte Element zu finden.