Sortiereigenvektoren durch ihre Eigenwerte (assoziiertes Sortierung)

Question

ich einen unsortierten Vektor von Eigenwerten und eine damit verbundene Matrix aus Eigenvektoren. Ich mag die Spalten der Matrix in Bezug auf den sortierten Satz von Eigenwerten sortieren. (Z.B. wenn Eigenwert [3] bewegt sich zu Eigenwert [2], möchte ich Spalte 3 der Eigenvektormatrix zu bewegen, über Spalte 2).

Ich weiß, dass ich die Eigenwerte in O(N log N) über std::sort sortieren. Ohne meine eigenen Sortieralgorithmus zu rollen, wie ich sicherstellen, dass die Spalten der Matrix (die zugehörigen Eigenvektoren) folgen zusammen mit ihren Eigenwerte wie diese sortiert werden?

Answer 1

Normalerweise erstellen Sie einfach eine Struktur etwas wie folgt aus:

struct eigen { 
    int value;
    double *vector;

    bool operator<(eigen const &other) const { 
        return value < other.value;
    }
};

Alternativ einfach setzen Eigenwert / Eigenvektor in eine std::pair -. Obwohl ich eigen.value und eigen.vector über something.first und something.second lieber

Answer 2

Ich habe dies einige Male in verschiedenen Situationen getan. Anstatt die Array Sortierung, erzeugt nur eine neue Array, das die sortierten Indizes in ihm hat.

Zum Beispiel haben Sie eine Länge n Array (Vektor) evals und eine 2D-nxn-Matrix evects. Erstelle ein neues Array-Index, der die Werte enthält, hat [0, N-1].

Dann anstatt evals als evals Zugriff auf [i], greifen Sie es als evals [Index [i]] und statt evects [i] [j], greifen Sie es evects [Index [i]] [j].

Jetzt schreiben Sie Ihre Sortierroutine den Index-Array zu sortieren, anstatt das Array evals, so dass anstelle von Index wie die Suche {0, 1, 2, ..., n-1}, wird der Wert in dem Index-Array sein in aufsteigender Reihenfolge der Werte in der evals Array.

So nach dem Sortieren, wenn Sie dies tun:

for (int i=0;i<n;++i)
{
  cout << evals[index[i]] << endl;
}

Sie eine sortierte Liste von evals erhalten.

So kann man alles sortieren, die tatsächlich mit dem evals Array zugeordnet ist, ohne um Speicher zu bewegen. Dies ist wichtig, wenn n groß wird, Sie wollen werden nicht die Spalten der Matrix evects bewegen.

im Grunde die i-te kleinste eval wird im Index befindet [i] und das entspricht den Index [i] ten evect.

Edited hinzuzufügen. Hier ist eine Sortierfunktion, dass ich die Arbeit mit std :: sort geschrieben habe zu tun, was ich gerade gesagt habe:

template <class DataType, class IndexType>
class SortIndicesInc
{
protected:
    DataType* mData;
public:
    SortIndicesInc(DataType* Data) : mData(Data) {}
    Bool operator()(const IndexType& i, const IndexType& j) const
    {
        return mData[i]<mData[j];
    }
};

Answer 3

Die Lösung beruht rein auf dem Weg Sie Ihre Eigenvektor Matrix speichern.

Die beste Leistung beim Sortieren erreicht werden, wenn Sie swap(evector1, evector2) implementieren können, so dass es nur die Zeiger erneut bindet und die realen Daten unverändert gelassen.

Dies getan werden könnte, so etwas wie double* mit oder wahrscheinlich mehr komplizierte etwas, hängt von Ihrer Matrix-Implementierung.

Wenn diese Weise getan, swap(...) würde Ihre Sortiervorgang Leistung nicht beeinträchtigen.

Answer 4

Die Idee Ihre Vektor und Matrix von conglomerating ist wahrscheinlich der beste Weg, um es in C ++ zu tun. Ich denke darüber nach, wie ich es in R tun würde, und zu sehen, ob das zu C ++ übersetzt werden kann. In R ist es sehr einfach, einfach evec <-evec [, Ordnung (eval)]. Leider weiß ich nicht irgend in Art und Weise gebaut, um die Reihenfolge () Betrieb in C ++ auszuführen. Vielleicht hat jemand anderes tut, in welchem ??Fall dies in ähnlicher Weise durchgeführt werden können.