按照第一列的升序对Eigen矩阵的列值进行排序

Question

我是一位有用的助手，可以为您进行文本翻译。以下是需要翻译的内容：

我在Eigen中有一个n x 3的矩阵。我想通过按照第一列中的值升序排列来重新排列第二列和第三列的值。 例如，在排序之前：

  1  4  6
 -2  5  2
  3  1  0

按照第一列数值的升序排列后：

 -2 5 2
  1 4 6
  3 1 0

我不知道该如何处理这个问题。我可以将每一列读入一个向量，使用std::sort对第1列向量进行排序，但是我不知道如何保留第1列排序后对应的第2列和第3列的值。如果n的值已知且固定，则可以在某种程度上帮助解决问题。

- user1420

Answer 1

我想到的最佳解决方案是将行复制到一个 std::vector 中，然后对其进行排序：

#include <Eigen/Core>
#include <algorithm>    // std::sort
#include <vector>       // std::vector

bool compare_head(const Eigen::VectorXd& lhs, const Eigen::VectorXd& rhs)
{
    return lhs(0) < rhs(0);
}

Eigen::MatrixXd sorted_rows_by_head(Eigen::MatrixXd A)
{
    std::vector<Eigen::VectorXd> vec;
    for (int64_t i = 0; i < A.rows(); ++i)
        vec.push_back(A.row(i));

    std::sort(vec.begin(), vec.end(), &compare_head);

    for (int64_t i = 0; i < A.rows(); ++i)
        A.row(i) = vec[i];

    return A;
}

- xjcl

---

我以为像这样的排序会在Eigen内部实现... 这个很好用！ 有没有一种方法可以使用移动语义来进行原地排序？并且最好的方法是什么，使得可以提供用于排序的列的顺序（例如，按第2列、第4列、第1列排序。未指定的列按其默认顺序使用） 谢谢！ - Frederik

Answer 2

基于xjcl的第二个选项，我创建了一个基于lambda的选项，可以轻松地包含在头文件中：

#include <Eigen>
#include <algorithm>
#include <vector>

void eigen_sort_rows_by_head(Eigen::MatrixXd& A_nx3)
{
    std::vector<Eigen::VectorXd> vec;
    for (int64_t i = 0; i < A_nx3.rows(); ++i)
        vec.push_back(A_nx3.row(i));

    std::sort(vec.begin(), vec.end(), [](Eigen::VectorXd const& t1, Eigen::VectorXd const& t2){ return t1(0) < t2(0); } );

    for (int64_t i = 0; i < A_nx3.rows(); ++i)
        A_nx3.row(i) = vec[i];
};

该选项还通过引用获取目标矩阵。然而，我认为它可以改进，希望得到帮助：

• 将其就地完成（使用Eigen的 SWAP）
• 允许指定变量数量的列（0到n），按给定顺序在比较中使用。剩余的列按字典顺序用于打破平局。
• 允许传递（可选的）函数/ PRNG来打破任何剩余的平局。

此外，我们不能尽管Eigen中的警告而使用auto进行自动模板推导吗？

- Frederik

Answer 3

这并不美观，依赖于使用它的模板参数拆开矩阵 - 但它可以工作。

#include <Eigen/Core>
#include <algorithm>
#include <vector>

// Simple little templated comparison functor
template <typename MatrixT>
bool compareRows(MatrixT a, MatrixT b) {
    return a(0,0) < b(0,0);
}

// These are the 6 template arguments to every Eigen matrix
template <typename Scalar, int rows, int cols, int options, int maxRows, int maxCols> 
Eigen::Matrix<Scalar, rows, cols, options, maxRows, maxCols> sortMatrix(
    Eigen::Matrix<Scalar, rows, cols, options, maxRows, maxCols> target
) {
    // Manually construct a vector of correctly-typed matrix rows
    std::vector<Eigen::Matrix<Scalar, 1, cols>> matrixRows;
    for (unsigned int i = 0; i < target.rows(); i++) 
            matrixRows.push_back(target.row(i));
    std::sort(
            matrixRows.begin(),
            matrixRows.end(),
            compareRows<Eigen::Matrix<Scalar, 1, cols>>
    );

    Eigen::Matrix<Scalar, rows, cols, options, maxRows, maxCols> sorted;
    for (unsigned int i = 0; i < matrixRows.size(); i++)
            sorted.row(i) = matrixRows[i];
    return sorted;
}

幸运的是，由于模板参数推导，您可以像这样简单地调用此混乱代码：

Eigen::Matrix3f myMatrix;
// Fill in contents here
Eigen::Matrix3f sorted = sortMatrix(myMatrix);

我几乎可以肯定有更优雅的方法来做这件事，但现在想不出来。而且，因为它使用了 std::vector，你需要使用 -std=c++11 或更高版本进行编译。

- Sebastian Lenartowicz

---

你不需要做过于复杂的模板编程；一个简单的 Eigen::MatrixXd 就可以胜任。 - xjcl

Answer 4

使用Eigen 3.4和C++14（或更高版本），您可以直接使用Eigen的迭代器接口。不幸的是，它缺少swap功能的前向引用，因此只需编写一次：

#include <Eigen/Core>

namespace Eigen {
    template<class T>
    void swap(T&& a, T&& b){
        a.swap(b);
    }
}

但之后，您可以直接编写这个一行代码：

std::sort(A.rowwise().begin(), A.rowwise().end(),
     [](auto const& r1, auto const& r2){return r1(0)<r2(0);});

在godbolt上的实际工作示例：https://godbolt.org/z/h9nEGvz4e

- chtz

---

我不得不稍微修改一下，以便只调用 A.rowwise() 一次。否则，我会因为 Eigen 不允许比较来自不同 rowwise 实例的迭代器而导致运行时错误。 - hhergeth

Answer 5

我已经实现了这个函数，你需要：

#include <Eigen/Dense>
#include <Eigen/Core>

这个函数是：

Eigen::MatrixXd sortMatrix(const Eigen::MatrixXd &original_matrix) {

  Eigen::MatrixXd sorted_matrix(original_matrix.rows(), original_matrix.cols());
  Eigen::VectorXd sorted_rows = original_matrix.col(0);
  Eigen::VectorXd::Index min_row;

  for ( int i = 0; i < original_matrix.rows(); i++) {
    sorted_rows.minCoeff(&min_row);
    sorted_matrix.row(i) = original_matrix.row(min_row);
    sorted_rows(min_row) = std::numeric_limits<double>::max();
  }

   return sorted_matrix;
}

该函数在一个新向量中创建了矩阵的第一列的副本以进行排序。它将最小值复制到另一个矩阵中。一旦复制完成，该值就被销毁（在向量中分配最大值，以便不再被识别为最小值），因此它将继续查找和排序最小值，直到所有辅助向量都为空且新矩阵已排序。如果存在两个完全相同的值，则不能保证第二列会被排序，它只关注第一列。

这是一个O(n^2)算法，随着矩阵大小的增长效率会降低。

有关所使用命令的一些信息： Eigen中的块操作（col()，row()） Eigen中的矩阵和向量运算（minCoeff()）

- telmozufi