Wie finden Sie die oberen verschiedenen Werte von einem Array?

Question

Ich habe ein Array von Float-Werten und möchte den Wert und vor allem die Position der maximal vier Werte.

Ich baute das System ursprünglich, um durch das Array zu gehen und das Maximum auf die übliche Weise zu finden, indem es den Wert an der aktuellen Position mit einer aufgezeichneten Max-so-weit vergleicht und eine Positionsvariable aktualisiert, wenn die max-so- weit Änderungen. Das funktionierte gut, ein O (n) Algo, der sehr einfach war. Ich habe später gelernt, dass ich nicht nur den oberen Wert, sondern die oberen drei oder vier behalten muss. Ich erweiterte das gleiche Verfahren und komplizierte die Max-So-Fern in eine Anordnung von vier Max-So-Fars und jetzt ist der Code hässlich.

Es funktioniert immer noch und ist immer noch ausreichend schnell, da nur eine triviale Menge an Berechnungen zum Verfahren hinzugefügt wurde. Es geht immer noch effektiv über das Array und überprüft jeden Wert einmal.

Ich mache dies in MATLAB mit einer Sortierfunktion, die zwei Arrays zurückgibt, die sortierte Liste und die zugehörige ursprüngliche Positionsliste. Mit Blick auf die ersten paar Werte habe ich genau das, was ich brauche. Ich repliziere diese Funktionalität in einem C# .NET 2.0-Programm.

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

Es hat gut funktioniert, aber jetzt finde ich mich will den fünften Max-Wert und sehe, dass die Max-so-weit-Checker, die derzeit eine hässliche Unordnung ist, wenn Aussagen würden nur die Hässlichkeit zusammen. Es würde gut funktionieren und nicht langsamer sein, ein fünftes Level hinzuzufügen, aber ich möchte die SO-Community fragen, ob es einen besseren Weg gibt.

Das Sortieren der gesamten Liste erfordert viel mehr Berechnungen als meine aktuelle Methode, aber ich denke nicht, dass es ein Problem wäre, da die Liste "nur" ein oder zweitausend Fließkommazahlen enthält; Wenn es also eine Sortierroutine gibt, die die ursprünglichen Positionen zurückgeben kann, wäre das ideal.

Als Hintergrund ist dieses Array das Ergebnis einer Fourier-Transformation auf einer Kilobyte der Wave-Datei, so dass die Positionen der Max-Werte den Spitzenfrequenzen der Sample-Daten entsprechen. Ich war mit den ersten vier zufrieden, sah aber die Notwendigkeit, die Top 5 oder 6 für eine genauere Probenklassifizierung zu sammeln.

Answer 1

kann ich einen alternativen Algorithmus vorschlagen, die Sie Code :)

Verwenden Sie einen Haufen Größe K, wo K speichern möchten Sie die Anzahl der oberen Elemente bezeichnet haben werden. Initialisiere dies auf die ersten K Elemente deines ursprünglichen Arrays. Für alle N - K Elemente durchlaufen Sie das Array und fügen es bei Bedarf ein.

Answer 2

Sie können Ihre Listenidee immer noch verwenden - die Elemente, die Sie in die Liste einfügen, könnten eine Struktur sein, die sowohl den Index als auch den Wert speichert; aber sortiert nur auf den 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 können, während die Informationen über den Index zu halten. Wenn Sie nur die größten m Elemente in der Liste behalten, sollte Ihre Effizienz O (mn) sein.

Answer 3

Ich weiß nicht, welchen Algorithmus Sie gerade verwenden, aber ich schlage einen einfachen vor. zugibt, dass Sie eine Reihe von Schwimmern haben f 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.

Beachten Sie, dass, wenn der capacity Wert wächst, wird es etwas langsamer als die Alternative, die die Liste sortiert, während die Verfolgung der Anfangspositionen. Denken Sie daran, dass die Sortierung O (n log n) Vergleiche erfordert, während dieser Algorithmus O (n Kapazität) benötigt.

Answer 4

Eine weitere Option ist die Schnellauswahl. Schnellauswahl gibt die Position des k-ten Elements in einer Liste zurück. Nachdem Sie die Position und den Wert des k-ten Elements haben, gehen Sie über die Liste und nehmen Sie jedes Element, dessen Wert kleiner/größer als das k-te Element ist.

fand ich eine C# -Implementierung von Quick-Select hier: link text

Pro:

1. O (n + k) durchschnittliche Laufzeit.

Nachteile:

1. Die k Elemente zu finden sind nicht sortiert. Wenn Sie sie sortieren, ist die Laufzeit O (n + logk)
2. Ich habe dies nicht überprüft, aber ich denke, dass für eine sehr kleine k die beste Option ist, k über das Array zu tun, jedes Mal die nächste zu finden kleinstes/größtes Element.