¿Cómo reescribir la matriz desde el orden de fila hasta el orden de columna?

Question

Tengo este doble for-loop, donde tengo indización de ordenamiento de fila y ordenación de columna, lo que debería ser malo para el rendimiento.

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; 

    } 
    } 

¿Existe un enfoque/método sobre cómo reescribir de uno a otro?

Cuando intento volver a escribir el último orden de columnas, los datos se vuelven asimétricos. ¿No puede ser reescrito?

Sandra

Answer 1

Esto nunca va a ser muy rápido ya que es probable que tenga una serie de fallos de caché, ya sea que usted tiene que caminar a la matriz con un gran tono o la otra , no hay escapatoria. El problema aquí es que a una computadora le gustan los accesos sucesivos a la memoria para estar juntos, lo que en su algoritmo no es el caso de la indexación de array_a salta por elementos de altura a la vez debido al término de altura col . Para solucionarlo, puede cambiar los bucles pero, con el ancho (height-1 -row) de array_b, tiene el mismo problema.

Puede reescribir una de las matrices para que coincida con el orden de la otra, pero entonces tendría exactamente el mismo problema en el código que la reescribe, por lo que depende de si necesita hacer este tipo de cosas más más de una vez en los mismos datos, si lo hace, entonces tiene sentido reescribir primero una de las matrices como Poita_ describe, de lo contrario será mejor que deje el algoritmo tal como está.

Answer 2

No es esta la causa de sus datos sesgar? Todos los valores negativos están siendo llevados a cero:

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

Answer 3

Así que quieres cambiar de algo como:

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

a

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

?

Trate

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 4

Si es común intercambiar la fila orrdering, escriba su propia clase de matriz.

Los datos en realidad no tienen que moverse solo la interfaz que accede a los datos necesita saber cómo acceder a los datos.

#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

Dado que la cuestión está etiquetada C++, voy a contribuir una respuesta que muestra cómo acceder a/manipulación de matrices columna-principal se puede hacer usando Boost.Multiarray (que pueden ser útiles a los demás que se enfrentan a un problema similar). Considero que Boost es una extensión de la biblioteca estándar de C++. No dude en ignorar esta respuesta si no le gusta/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); 
} 

Salida:

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

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

Como se puede ver, puede dejar los datos de origen en su formato de columna principal, y utilizar boost::multi_array_ref con las especificaciones de almacenamiento personalizados para manipular los datos directamente (como si fuera fila mayor) usando la notación matrix[row][col].

Si la matriz va a ser atravesada a menudo en forma de hileras principales, entonces podría ser mejor transponerla a una matriz real principal de filas, como se muestra en la última parte de mi ejemplo.