4

我对 c++ 相当陌生，并且正在尝试编写 strassen 算法来乘以矩阵。算法的一部分要求我将矩阵划分为四个部分，例如

4 5 6 7
6 7 8 9
1 2 3 4
2 3 5 6

分区：

4 5   6 7
6 7   8 9

1 2   3 4
2 3   5 6

（然后每个部分再次递归使用和分区）。我想在不循环和复制原始矩阵中的数据的情况下对矩阵进行分区（因为这将花费更多时间）。我正在阅读的书说矩阵使用'索引计算进行分区，通过原始矩阵的一系列行索引和一系列列索引来识别子矩阵。我不确定这是什么意思。

另外，我不确定我是否应该使用二维数组或向量？我见过很多人推荐向量，但到目前为止我已经在二维数组中编写了所有内容，所以我希望二维数组可以实现我想要的。

ps 可以假设矩阵的维度总是2的幂并且是nxn（正方形）。另外，我看到了很多与此类似的问题，但实际上没有一个问题有我正在寻找的解决方案。

谢谢

4

1 回答 1

1

您可以创建一个矩阵类，直接支持子矩阵作为视图：

template<typename T>
struct Matrix {
    int rows, cols, stride;
    std::vector<T> data; // Possibly empty for a view
    T *ptr;

    // A fresh matrix (owning its data)
    Matrix(int rows, int cols)
        : rows(rows), cols(cols), stride(cols),
          data(rows*cols),
          ptr(&data[0])
    {
    }

    // A view of a sub-matrix (pointing to the original data!)
    Matrix(Matrix& m, int row0, int col0, int rows, int cols)
        : rows(rows), cols(cols), stride(m.stride),
          ptr[&m(row0, col0)]
    {
    }

    T& operator()(int row, int col) {
        return ptr[row*stride + col];
    }

    ...
};

当然，您需要确保视图不会超过拥有矩阵，并且如果不禁止该操作，您需要注意复制视图对象的含义。

添加诸如将视图转换为拥有矩阵之类的显式操作可能很有用（如果复制构造函数不打算这样做）。

于 2015-11-15T18:21:36.720 回答