我有一个未排序的特征值向量和一个相关的特征向量矩阵。我想根据已排序的特征值集对矩阵的列进行排序。(例如,如果特征值 [3] 移动到特征值 [2],我希望特征向量矩阵的第 3 列移动到第 2 列。)
我知道我可以在O(N log N)
via中对特征值进行排序std::sort
。在不滚动我自己的排序算法的情况下,我如何确保矩阵的列(相关的特征向量)跟随它们的特征值,因为后者是排序的?
我有一个未排序的特征值向量和一个相关的特征向量矩阵。我想根据已排序的特征值集对矩阵的列进行排序。(例如,如果特征值 [3] 移动到特征值 [2],我希望特征向量矩阵的第 3 列移动到第 2 列。)
我知道我可以在O(N log N)
via中对特征值进行排序std::sort
。在不滚动我自己的排序算法的情况下,我如何确保矩阵的列(相关的特征向量)跟随它们的特征值,因为后者是排序的?
通常只需创建一个类似这样的结构:
struct eigen {
int value;
double *vector;
bool operator<(eigen const &other) const {
return value < other.value;
}
};
或者,只需将特征值/特征向量放入std::pair
- 尽管我更喜欢eigen.value
and 而eigen.vector
不是something.first
and something.second
。
我已经在不同的情况下多次这样做了。无需对数组进行排序,只需创建一个包含已排序索引的新数组即可。
例如,您有一个长度为 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];
}
};
该解决方案完全依赖于您存储特征向量矩阵的方式。
如果您可以实现排序时的最佳性能swap(evector1, evector2)
,那么它只重新绑定指针并且真实数据保持不变。
这可以使用类似double*
或更复杂的东西来完成,具体取决于您的矩阵实现。
如果这样做,swap(...)
不会影响您的排序操作性能。
合并向量和矩阵的想法可能是在 C++ 中实现它的最佳方式。我正在考虑如何在 R 中执行此操作,并查看是否可以将其转换为 C++。在 R 中这很简单,只需 evec<-evec[,order(eval)]。不幸的是,我不知道在 C++ 中执行 order() 操作的任何内置方法。也许其他人会这样做,在这种情况下,可以以类似的方式完成。