Сортировка собственных векторов по их собственным значениям (ассоциированная сортировка)

Question

У меня есть несортированный вектор собственных значений и соответствующая матрица собственных векторов. Я хотел бы отсортировать столбцы матрицы по отсортированному набору собственных значений. (например, если собственное значение [3] переместится в собственное значение [2], я хочу, чтобы столбец 3 матрицы собственных векторов переместился в столбец 2.)

Я знаю, что могу отсортировать собственные значения в O(N log N) через std::sort. Без использования моего собственного алгоритма сортировки, как мне убедиться, что столбцы матрицы (связанные собственные векторы) следуют вместе со своими собственными значениями при сортировке последних?

Answer 1

Обычно просто создайте структуру примерно так:

struct eigen { 
    int value;
    double *vector;

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

В качестве альтернативы просто поместите собственное значение / собственный вектор в std::pair - хотя я бы предпочел eigen.value и eigen.vector над something.first и something.second.

Answer 2

Я делал это несколько раз в разных ситуациях. Вместо того, чтобы сортировать массив, просто создайте новый массив, в котором есть отсортированные индексы.

Например, у вас есть массив длины n (вектор), и 2d массив nxn выдвигается. Создайте новый индекс массива, который содержит значения [0, n-1].

Тогда вместо того, чтобы обращаться к evals как evals [i], вы получаете доступ к нему как evals [index [i]], а вместо evects [i] [j] вы получаете доступ к evects [index [i]] [j].

Теперь вы пишете свою процедуру сортировки для сортировки массива индекса, а не массива evals, поэтому вместо индекса в виде {0, 1, 2, ..., n-1} значение в массиве индекса будет в порядке возрастания значений в массиве evals.

Итак, после сортировки, если вы сделаете это:

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

вы получите отсортированный список уловок.

таким образом, вы можете сортировать все, что связано с этим массивом evals, без реального перемещения памяти. Это важно, когда n становится большим, вы не хотите перемещаться по столбцам матрицы evects.

в основном i-й наименьший eval будет расположен в index [i], и это соответствует index [i] thvect.

Отредактировано, чтобы добавить. Вот функция сортировки, которую я написал для работы с std :: sort, чтобы сделать то, что я только что сказал:

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

Идея конгломерации вашего вектора и матрицы, вероятно, лучший способ сделать это в C ++. Я думаю о том, как бы это сделать в R и посмотреть, можно ли это перевести на C ++. В R это очень просто, просто evec <-evec [, order (eval)]. К сожалению, я не знаю ни одного встроенного способа выполнения операции order () в C ++. Возможно, это делает кто-то другой, и в этом случае это можно сделать аналогичным образом. </p>

Answer 4

Решение основано исключительно на том, как вы храните матрицу собственных векторов.

Наилучшая производительность при сортировке будет достигнута, если вы сможете реализовать swap(evector1, evector2), чтобы он только связывал указатели и реальные данные оставались без изменений.

Это можно сделать, используя что-то вроде double* или, возможно, что-то более сложное, зависит от вашей реализации матрицы.

Если сделать это таким образом, swap(...) не повлияет на производительность операции сортировки.