4

我有一个未排序的特征值向量和一个相关的特征向量矩阵。我想根据已排序的特征值集对矩阵的列进行排序。(例如,如果特征值 [3] 移动到特征值 [2],我希望特征向量矩阵的第 3 列移动到第 2 列。)

我知道我可以在O(N log N)via中对特征值进行排序std::sort。在不滚动我自己的排序算法的情况下,我如何确保矩阵的列(相关的特征向量)跟随它们的特征值,因为后者是排序的?

4

4 回答 4

7

通常只需创建一个类似这样的结构:

struct eigen { 
    int value;
    double *vector;

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

或者,只需将特征值/特征向量放入std::pair- 尽管我更喜欢eigen.valueand 而eigen.vector不是something.firstand something.second

于 2010-04-21T21:15:54.893 回答
2

我已经在不同的情况下多次这样做了。无需对数组进行排序,只需创建一个包含已排序索引的新数组即可。

例如,您有一个长度为 n 的数组(向量)evals 和一个 2d nxn 数组 evects。创建一个包含值 [0, n-1] 的新数组索引。

然后,不是以 evals[i] 的形式访问 eval,而是以 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] 个 evect。

编辑添加。这是我编写的一个排序函数,用于使用 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];
    }
};
于 2010-04-21T22:26:15.530 回答
0

该解决方案完全依赖于您存储特征向量矩阵的方式。

如果您可以实现排序时的最佳性能swap(evector1, evector2),那么它只重新绑定指针并且真实数据保持不变。

这可以使用类似double*或更复杂的东西来完成,具体取决于您的矩阵实现。

如果这样做,swap(...)不会影响您的排序操作性能。

于 2010-04-21T21:49:31.037 回答
0

合并向量和矩阵的想法可能是在 C++ 中实现它的最佳方式。我正在考虑如何在 R 中执行此操作,并查看是否可以将其转换为 C++。在 R 中这很简单,只需 evec<-evec[,order(eval)]。不幸的是,我不知道在 C++ 中执行 order() 操作的任何内置方法。也许其他人会这样做,在这种情况下,可以以类似的方式完成。

于 2010-04-21T22:03:45.400 回答