Tri par leurs valeurs propres vecteurs propres (associée tri)

Question

I ont un vecteur de valeurs propres non triés et d'une matrice de vecteurs propres est associée. Je voudrais trier les colonnes de la matrice par rapport à l'ensemble des valeurs propres triées. (Par exemple, si la valeur propre [3] se déplace vers des valeurs propres [2], je veux la colonne 3 de la matrice de vecteur propre de passer à la colonne 2).

Je sais que je peux trier les valeurs propres à O(N log N) via std::sort. Sans rouler mon propre algorithme de tri, comment puis-je assurer que des colonnes (les vecteurs propres associés) suivent ainsi que leurs valeurs propres de la matrice que ceux-ci sont classés?

Answer 1

En général il suffit de créer une structure quelque chose comme ceci:

struct eigen { 
    int value;
    double *vector;

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

Sinon, il suffit de mettre la valeur propre / vecteur propre dans un std::pair -. Bien que je préfère eigen.value et eigen.vector sur something.first et something.second

Answer 2

Je l'ai fait plusieurs fois dans des situations différentes. Plutôt que de trier le tableau, il suffit de créer un nouveau tableau qui a les indices triés en elle.

Par exemple, vous avez un tableau de longueur n (vecteur) evals, et un 2d evects de tableau nxn. Créer un nouvel index de tableau qui contient les valeurs a [0, n-1].

Ensuite, au lieu d'accéder evals comme evals [i], vous y accédez comme evals [index [i]] et au lieu de evects [i] [j], vous accédez evects [index [i]] [j].

Maintenant que vous écrivez votre routine de tri pour trier le tableau d'index plutôt que le tableau evals, donc au lieu de l'indice ressemblant {0, 1, 2, ..., n-1}, la valeur du tableau d'index sera dans l'ordre croissant des valeurs dans le tableau evals.

Ainsi, après le tri, si vous faites ceci:

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

vous obtiendrez une liste triée des evals.

De cette façon vous pouvez trier tout ce qui est associé à ce tableau de evals sans bouger réellement la mémoire autour. Ceci est important lorsque n devient grand, vous ne voulez pas se déplacer autour des colonnes de la matrice de evects.

essentiellement le plus petit i'th eval sera situé à l'index [i] et qui correspond à l'indice [i] e evect.

Edité à ajouter. Voici une fonction de tri que j'ai écrit à travailler avec std :: sort pour faire ce que je viens de dire:

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

La solution repose uniquement sur la façon dont vous stockez votre matrice de vecteurs propres.

Les meilleures performances lors du tri sera réalisé si vous pouvez mettre en œuvre swap(evector1, evector2) afin que les pointeurs ne lie de nouveau et les données réelles reste inchangé.

Cela pourrait se faire en utilisant quelque chose comme double* ou probablement quelque chose de plus compliqué, dépend de votre mise en œuvre de la matrice.

Si fait de cette façon, swap(...) aurait aucune incidence sur les performances de votre opération de tri.

Answer 4

L'idée de conglomérant votre vecteur et de la matrice est probablement la meilleure façon de le faire en C ++. Je pense à ce que je ferais en R et voir si cela peut être traduit en C ++. En R il est très facile, il suffit evec <-evec [, ordre (eval)]. Malheureusement, je ne connais pas construit de façon à effectuer l'opération order () en C ++. Peut-être quelqu'un d'autre, dans ce cas, cela pourrait se faire de la même manière.