如何高效计算两个Eigen矩阵的集合差？性能优化需求

问题背景 #

需要计算两个Eigen矩阵的集合差：找出第一个矩阵中未出现在第二个矩阵中的行，同时记录这些行在原矩阵中的索引。已实现的代码功能可行，但内层双重循环导致性能极差，处理10000条记录时耗时超43秒，需要用更简洁高效的方式替换内层循环，实现性能量级的提升。

原低效实现代码 #

void diffMatrix(
    MatrixXi &M1, // 第一个矩阵
    MatrixXi &M2, // 第二个矩阵
    MatrixXi &M3, // 存储集合差的矩阵
    VectorXi &I3  // 存储集合差行的原索引
)
{
    // 找出M1中不在M2里的行
    assert(M1.cols() == M2.cols());

    M3.resize(M1.rows(), M1.cols());
    I3.resize(M1.rows());

    bool m2r_nonex;
    size_t k = 0;

    // 遍历M1的每一行
    for (size_t i = 0; i < M1.rows(); i++)
    {
        m2r_nonex = true;
        auto m1r = M1.row(i);

        // 【性能瓶颈】内层循环逐行比对
        for (size_t j = 0; j < M2.rows(); j++)
        {
            auto m2r = M2.row(j);
            if (m1r == m2r)
                m2r_nonex = false;
        }

        // 若当前行不在M2中，加入结果集
        if (m2r_nonex)
        {
            M3.row(k) = m1r;
            I3(k) = i;
            k++;
        }
    }

    M3.conservativeResize(k, NoChange);
    I3.conservativeResize(k, NoChange);
}

// 测试示例
MatrixXi M1, M2, M3;
VectorXi I3;

M1.resize(3, 3);
M2.resize(2, 3);

M1 << 0, 0, 0, 1, 1, 1, 2, 2, 2;
M2 << 1, 1, 1, 2, 2, 2;

diffMatrix(M1, M2, M3, I3);

// 输出结果
// ===========================================
// M3 (Rows: 1 Cols: 3)
// ===========================================
// [[0, 0, 0]]

性能测试场景 #

当处理10000行数据时，原方法耗时43.826125秒，优化后仅需0.017632秒，性能提升数个数量级：

MatrixXi M1, M2, M3;
VectorXi I3;
size_t rows = 10000;

M1.resize(rows, 3);
M2.resize(rows, 3);

for (size_t i = 0; i < rows; i++)
{
    M1(i,0) = i;
    M1(i,1) = i; 
    M1(i,2) = i;

    M2(i,0) = i + 1;
    M2(i,1) = i + 1; 
    M2(i,2) = i + 1;
}

优化方案（高效实现） #

核心思路是将矩阵行转换为可哈希的结构，利用哈希表快速查询，彻底避免双重循环：

#include <unordered_set>
#include <Eigen/Dense>

// 自定义哈希函数，适配Eigen行向量
struct RowHash {
    size_t operator()(const Eigen::VectorXi& row) const {
        size_t hash = 0;
        for (int i = 0; i < row.size(); ++i) {
            // 哈希组合算法，可根据需求替换更高效实现
            hash ^= std::hash<int>()(row(i)) + 0x9e3779b9 + (hash << 6) + (hash >> 2);
        }
        return hash;
    }
};

// 自定义行向量相等判断逻辑
struct RowEqual {
    bool operator()(const Eigen::VectorXi& a, const Eigen::VectorXi& b) const {
        return a == b;
    }
};

void diffMatrixFast(
    const Eigen::MatrixXi &M1,
    const Eigen::MatrixXi &M2,
    Eigen::MatrixXi &M3,
    Eigen::VectorXi &I3
) {
    assert(M1.cols() == M2.cols());

    // 将M2的所有行存入哈希集合，O(n)时间复杂度
    std::unordered_set<Eigen::VectorXi, RowHash, RowEqual> m2_rows;
    for (int i = 0; i < M2.rows(); ++i) {
        m2_rows.insert(M2.row(i));
    }

    // 遍历M1筛选目标行，O(m)时间复杂度
    std::vector<Eigen::VectorXi> result_rows;
    std::vector<int> result_indices;
    for (int i = 0; i < M1.rows(); ++i) {
        const auto& row = M1.row(i);
        if (m2_rows.find(row) == m2_rows.end()) {
            result_rows.push_back(row);
            result_indices.push_back(i);
        }
    }

    // 将结果转换为Eigen格式
    M3.resize(result_rows.size(), M1.cols());
    I3.resize(result_indices.size());
    for (int i = 0; i < result_rows.size(); ++i) {
        M3.row(i) = result_rows[i];
        I3(i) = result_indices[i];
    }
}

优化说明 #

• 哈希表查询时间复杂度为O(1)，整体时间复杂度从原O(m*n)降至O(m + n)（m、n分别为M1、M2的行数）
• 自定义RowHash和RowEqual适配Eigen向量的哈希存储与查询
• 若矩阵元素类型不是int，只需调整哈希函数中的对应类型即可

内容的提问来源于stack exchange，提问作者Kabu