如何将数组从行顺序重写为列顺序？

Question

我有这个双 for 循环，其中我有行顺序和列顺序数组索引，这应该不利于性能。

   for (int row = 0; row < height; row++) {
    for (int col = 0; col < width; col++) {

      /* Column-major order */
      d = array_a[col*height +row];

      if (d < 0) { d = 0; }

      /* Row-major order */
      /* Map from x=0,y=0 at buttom left corner to
         0,0 at top left corner */
      array_b[width*(height-1 -row) + col] = d;

    }
  }

是否有关于如何从一个重写到另一个的方法/方法？

当我尝试将最后一个重写为列顺序时，数据变得倾斜。不能改写吗？

桑德拉

原文由 Sandra Schlichting 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

这永远不会很快，因为您可能会有许多缓存未命中，您要么必须步入一个间距较大的矩阵，要么进入另一个矩阵，这是无法逃脱的。这里的问题是计算机喜欢连续的内存访问靠近在一起，在您的算法中，由于 col*height 术语，array_a 的索引一次跳过高度元素的索引并非如此。要解决这个问题，您可以切换 for 循环，但是您会遇到与 — 中的 array_b width*(height-1 -row) 术语相同的问题。

您可以重写其中一个数组以匹配另一个数组的顺序，但是在进行重写的代码中您会遇到完全相同的问题，因此这取决于您是否需要在相同的数据，如果你这样做，那么首先重写一个像 Poita_ 描述的矩阵是有意义的，否则你最好让算法保持原样。

原文由 wich 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 2

由于问题被标记为 C++，我将提供一个答案，说明如何使用 Boost.Multiarray 访问/操作列主矩阵（它可能对面临类似问题的其他人有用）。我认为 Boost 是对 C++ 标准库的扩展。如果您不喜欢/使用 Boost，请随意忽略此答案。 :-)

 #include <algorithm>
#include <iostream>
#include <boost/multi_array.hpp>

// Prints the contents of a matrix to standard output
template <class M> void printMatrix(const M& matrix)
{
    int height = matrix.shape()[0];
    int width = matrix.shape()[1];
    for (int row=0; row<height; ++row)
    {
        for (int col=0; col<width; ++col)
        {
            std::cout << matrix[row][col] << " ";
        }
        std::cout << "\n";
    }
}

int main()
{
    // Source matrix data is in column-major format in memory,
    // with data starting at bottom-left corner.
    double data[] =
    {
        3, 7, 11,
        2, 6, 10,
        1, 5, 9,
        0, 4, 8
    };
    int width=4, height=3;

    // Store rows, then columns (column-major)
    int ordering[] = {0,1};

    // Store rows in descending order (flips Y axis)
    bool ascending[] = {true,false};

    // Create a multi_array that references the existing data,
    // with custom storage specifications.
    typedef boost::multi_array_ref<double, 2> Matrix;
    typedef boost::general_storage_order<2> Storage;
    Matrix matrix(
        data,
        boost::extents[height][width],
        Storage(ordering, ascending)
    );

    // Access source data as if it's row major
    printMatrix(matrix);
    std::cout << "\n";

    // Transpose source data to an actual row-major matrix
    // boost::multi_array is row-major by default
    boost::multi_array<double, 2> matrix2(boost::extents[height][width]);
    std::copy(matrix.begin(), matrix.end(), matrix2.begin());
    printMatrix(matrix2);
}

输出：

 0 1 2 3
4 5 6 7
8 9 10 11

0 1 2 3
4 5 6 7
8 9 10 11

如您所见，您可以将源数据保留为其列主要格式，并使用 boost::multi_array_ref 和自定义存储规范来直接操作数据（就好像它是行主要的）使用 matrix[row][col] 符号。

如果要经常以行优先方式遍历矩阵，那么最好将其转置为实际的行优先矩阵，如我示例的最后一部分所示。

原文由 Emile Cormier 发布，翻译遵循 CC BY-SA 2.5 许可协议