How to rewrite array from row-order to column-order?

Question

Hi everybody,

I have this double for-loop, where I have both row-order and column-order array indexing, which should be bad for performance.

  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;

    }
  }

Is there an approach/method on how to rewrite from one to the other?

When I try to rewrite the last to column-order, the data becomes skewed. Can't it be rewritten?

Sandra

Answer 1

Isn't this the cause of your data skew? All the negative values are being zeroed out:

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

Answer 2

So you want to switch from something like:

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

to

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

?

Try

for (int i = 0; i < width; ++i)
  for (int j = 0; j < height; ++j)
    array_b[ i * height + j ] = array_a[ j * width + i ];

Answer 3

This is never going to be very fast as you'll probably have a number of cache misses, you'll either have to step to the one matrix with a large pitch or the other, there's no escaping that. The problem here is that a computer likes successive memory accesses to be close together, which in your algorithm is not the case the indexing of array_a skips by height elements at a time due to the col*height term. To fix that you could switch around teh for loops, but then you'd have the same problem with the width*(height-1 -row) term in array_b.

You could rewrite one of the arrays to match the ordering of the other, but then you would have the exact same problem in the code which does the rewrite, so it depends on whether you need to do this kind of thing more than once on the same data, if you do, then it makes sense to first rewrite one of the matrices like Poita_ described, otherwise you'd best leave the algorithm as is.

Answer 4

If swapping the row orrdering is common then write your own array class.

The data does not actually have to move just the interface that accesses the data needs to know how to access the data.

#include <vector>
class Matrix
{
  public:
    Matrix(int width,int height)
        :data(width,std::vector<int>(height))
        ,rowOrder(true)
    {
    }
    int& operator()(int x,int y)
    {
        return at(x,y);
    }
    int const& operator()(int x,int y) const
    {
        return const_cast<Matrix&>(*this).at(x,y);
    }

    void switchRowOrder()
    {
        rowOrder = !rowOrder;
    }

  private:
    int& at(int x,int y)
    {
        int& result = (rowOrder)
                            ?data[x][y]  // row Order Access
                            :data[y][x]; // col Order Access

        // Note there is no code to swap around the content of the data internally.
        return result;
    }

    std::vector<std::vector<int> >  data;
    bool rowOrder;
};

Answer 5

Since the question is tagged C++, I'll contribute an answer that shows how accessing / manipulating column-major matrices can be done using Boost.Multiarray (it may be useful to others who face a similar problem). I consider Boost to be an extension to the C++ standard library. Feel free to ignore this answer if you don't like/use 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);
}

Output:

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

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

As you can see, you can leave the source data in its column-major format, and use boost::multi_array_ref with custom storage specifications to manipulate the data directly (as if it were row-major) using the matrix[row][col] notation.

If the matrix is going to be traversed often in row-major fashion, then it might be better to transpose it to an actual row-major matrix, as shown in the last part of my example.