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

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;

    }
  }

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

当我尝试将最后一个重写为列顺序时,数据会变得歪斜.不能改写吗？

桑德拉

Answer 1

由于问题标记为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]表示法直接操作数据(就像它是行主要数据一样).

如果矩阵通常以行主方式遍历,那么将它转换为实际的行主矩阵可能会更好,如我的示例的最后一部分所示.

Answer 2

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

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