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

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

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

Источник

4 ответа

Решение

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

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,

Источник

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

Например, у вас есть массив длины 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];
    }
};
Источник

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

Источник

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

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

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

Если сделано так, swap(...) не повлияет на производительность вашей сортировки.

Источник
Другие вопросы по тегам