Ordenando vectores propios por sus valores propios (asociado clasificación)

Question

I tiene un vector sin clasificar de valores propios y una matriz relacionado de vectores propios. Me gustaría ordenar las columnas de la matriz con respecto al conjunto ordenado de valores propios. (Por ejemplo, si autovalor [3] se mueve a valor propio [2], quiero columna 3 de la matriz de vector propio para mover a la columna 2).

Yo sé que puedo ordenar los valores propios en O(N log N) través std::sort. Sin rodar mi propio algoritmo de ordenación, ¿cómo me aseguro de que las columnas de la matriz (los vectores propios asociados) sigue junto con sus valores propios ya que este último se clasifican?

Answer 1

Por lo general basta con crear una estructura algo como esto:

struct eigen { 
    int value;
    double *vector;

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

Como alternativa, sólo hay que poner el valor propio / en un vector propio std::pair -. Aunque yo prefiero eigen.value y eigen.vector sobre something.first y something.second

Answer 2

He hecho este número una de veces en diferentes situaciones. En lugar de la clasificación de la matriz, basta con crear una nueva matriz que tiene los índices ordenados en ella.

Por ejemplo, tiene una matriz de longitud n evals (vector), y un 2d evects matriz nxn. Crear un nuevo índice de matriz que tiene contiene los valores [0, n-1].

A continuación, en lugar de acceder evals como evals [i], se accede a ella como evals [Índice [i]] y en lugar de evects [i] [j], se accede a él evects [Índice [i]] [j].

Ahora que escriba su rutina de ordenación para ordenar la matriz índice en lugar de la matriz evals, por lo que en lugar de índice de aspecto de {0, 1, 2, ..., n-1}, el valor de la matriz índice será en el orden de los valores en aumento en la matriz evals.

Así que después de la clasificación, si usted hace esto:

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

obtendrá una lista ordenada de evals.

De esta manera se puede ordenar cualquier cosa que se asocia con esa matriz evals sin mover realmente la memoria alrededor. Esto es importante cuando n se hace grande, que no quieren que se mueve alrededor de las columnas de la matriz evects.

básicamente el i-ésimo eval más pequeño estará ubicado en el índice [i] y que corresponde al índice [i] º evect.

Editado para agregar. He aquí una función de clasificación que he escrito para trabajar con std :: sort para hacer lo que acabo de decir:

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 solución puramente depende de la forma en que se almacena la matriz de vectores propios.

La mejor rendimiento, mientras que la clasificación se logrará si se puede aplicar swap(evector1, evector2) de modo que sólo vuelve a vincular los indicadores y los datos reales se deja sin cambios.

Esto se podría hacer uso de algo así como double* o probablemente algo más complicado, depende de su aplicación matriz.

Si se hace de esta manera, swap(...) no afectaría el rendimiento de su operación de clasificación.

Answer 4

La idea de conglomerating su vector y la matriz es probablemente la mejor manera de hacerlo en C ++. Estoy pensando en la forma en que lo haría en I y ver si eso se puede traducir a C ++. En R es muy fácil, simplemente evec <-evec [, orden (eval)]. Por desgracia, no sé de cualquier construida en forma de realizar la operación de orden () en C ++. Tal vez alguien más lo hace, en cuyo caso se podría hacer de una manera similar.