Orden por filas y columnas

En informática, el orden por filas y el orden por columnas son métodos para almacenar matrices multidimensionales en almacenamiento lineal, como la memoria de acceso aleatorio .

La diferencia entre los órdenes radica en qué elementos de una matriz son contiguos en la memoria. En el orden por filas, los elementos consecutivos de una fila se encuentran uno al lado del otro, mientras que lo mismo ocurre con los elementos consecutivos de una columna en el orden por columnas. Si bien los términos aluden a las filas y columnas de una matriz bidimensional, los órdenes pueden generalizarse a matrices de cualquier dimensión, teniendo en cuenta que los términos "por filas" y "por columnas" son equivalentes a los órdenes lexicográfico y colexicográfico , respectivamente. Las matrices, que comúnmente se representan como colecciones de vectores fila o columna, se almacenan efectivamente como vectores consecutivos o componentes de vectores consecutivos mediante este enfoque. Estas formas de almacenar datos se denominan AoS y SoA, respectivamente.

La disposición de los datos es fundamental para transferir correctamente matrices entre programas escritos en distintos lenguajes de programación. También es importante para el rendimiento al recorrer una matriz, ya que las CPU modernas procesan los datos secuenciales de forma más eficiente que los no secuenciales. Esto se debe principalmente al almacenamiento en caché de la CPU , que aprovecha la localidad espacial de referencia . ^{[ 1 ]} Además, el acceso contiguo permite utilizar instrucciones SIMD que operan sobre vectores de datos. En algunos soportes, como el almacenamiento de datos en cinta magnética , el acceso secuencial es mucho más rápido que el acceso no secuencial.

Los términos ordenación por filas y por columnas provienen de la terminología relacionada con la ordenación de objetos. Una forma general de ordenar objetos con muchos atributos es agruparlos y ordenarlos primero por un atributo y luego, dentro de cada grupo, agruparlos y ordenarlos por otro atributo, y así sucesivamente. Si interviene más de un atributo en la ordenación, el primero se denomina principal y el último secundario . Si intervienen dos atributos, basta con nombrar solo el principal.

En el caso de los arreglos, los atributos son los índices a lo largo de cada dimensión. Para las matrices en notación matemática, el primer índice indica la fila y el segundo indica la columna , por ejemplo, dada una matriz${\displaystyle A}$, la entrada${\displaystyle a_{1,2}}$está en su primera fila y segunda columna. Esta convención se traslada a la sintaxis de los lenguajes de programación, ^{[ 2 ]} aunque a menudo con índices que comienzan en 0 en lugar de 1. ^{[ 3 ]}

Aunque la fila se indica con el primer índice y la columna con el segundo , esto no implica ningún orden de agrupación entre las dimensiones. Por lo tanto, la elección de cómo agrupar y ordenar los índices, ya sea por filas o por columnas, es una cuestión de convención. La misma terminología se puede aplicar a matrices de dimensiones aún mayores. La agrupación por filas comienza desde el índice más a la izquierda y la agrupación por columnas desde el índice más a la derecha , lo que da lugar a órdenes lexicográficos y colexicográficos (o colex) , respectivamente.

Por ejemplo, la matriz

${\displaystyle A=a_{y,x}={\begin{bmatrix}\color {Blue}a_{11}&\color {Blue}a_{12}&\color {Blue}a_{13}\\\color {Orange}a_{21}&\color {Orange}a_{22}&\color {Orange}a_{23}\end{bmatrix}}}$

podría almacenarse de dos maneras posibles:

Los lenguajes de programación manejan esto de diferentes maneras. En C , los arreglos multidimensionales se almacenan en orden de filas principales, y los índices del arreglo se escriben en orden de filas primero (orden de acceso lexicográfico):

Por otro lado, en Fortran , los arreglos se almacenan en orden de columnas, mientras que los índices de los arreglos todavía se escriben en orden de filas (orden de acceso colexicográfico):

Nótese cómo el uso de A[i][j]con indexación de varios pasos como en C, en contraposición a una notación neutral como A(i,j)como en Fortran, implica casi inevitablemente un orden por filas por razones sintácticas, por así decirlo, porque se puede reescribir como (A[i])[j], e A[i]incluso la parte de la fila se puede asignar a una variable intermedia que luego se indexa en una expresión separada. (No se deben asumir otras implicaciones; por ejemplo, Fortran no es de orden por columnas simplemente por su notación, e incluso la implicación anterior podría eludirse intencionalmente en un nuevo lenguaje).

Para usar el orden de columnas en un entorno de filas, o viceversa, por cualquier motivo, una solución consiste en asignar roles no convencionales a los índices (usando el primer índice para la columna y el segundo para la fila), y otra en eludir la sintaxis del lenguaje calculando explícitamente las posiciones en una matriz unidimensional. Por supuesto, desviarse de la convención probablemente conlleva un coste que aumenta con el grado de interacción necesaria con las características convencionales del lenguaje y otro código, no solo en forma de mayor vulnerabilidad a errores (olvidar invertir también el orden de multiplicación de matrices, volver a la convención durante el mantenimiento del código, etc.), sino también en forma de tener que reorganizar activamente los elementos, todo lo cual debe sopesarse frente a cualquier propósito original, como aumentar el rendimiento. Se prefiere ejecutar el bucle fila por fila en lenguajes de filas como C y viceversa para lenguajes de columnas.

Los lenguajes de programación o sus bibliotecas estándar que admiten matrices multidimensionales suelen tener un orden de almacenamiento nativo por filas o por columnas para estas matrices.

El orden de filas se utiliza en C / C++ / Objective-C (para matrices de estilo C), PL/I , ^{[ 4 ]} Pascal , ^{[ 5 ]} Speakeasy , ^{[ 6 ]} y SAS . ^{[ 7 ]}

El orden de columnas principales se utiliza en Fortran , ^{[ 8 ] [ 9 ]} IDL , ^{[ 8 ]} MATLAB , ^{[ 9 ]} GNU Octave , Julia , ^{[ 10 ]} S , S-PLUS , ^{[ 11 ]} R , ^{[ 12 ]} Scilab , ^{[ 13 ]} Yorick y Rasdaman . ^{[ 14 ]}

Dado que la transposición de matrices consiste en intercambiar los índices de una matriz , una matriz almacenada en orden de filas pero leída en orden de columnas (o viceversa) aparecerá transpuesta. Como realizar esta reorganización en memoria suele ser una operación costosa, algunos sistemas ofrecen opciones para especificar que las matrices individuales se almacenen transpuestas. El programador debe entonces decidir si reorganizar o no los elementos en memoria, en función de su uso real (incluida la cantidad de veces que la matriz se reutiliza en un cálculo).

Por ejemplo, a las funciones de los subprogramas básicos de álgebra lineal se les pasan indicadores que señalan qué matrices se transponen. ^{[ 25 ]}

El concepto se generaliza a matrices con más de dos dimensiones.

Para un d -dimensional${\displaystyle N_{1}\times N_{2}\times \cdots \times N_{d}}$matriz con dimensiones N _k ( k =1... d ), un elemento dado de esta matriz se especifica mediante una tupla${\displaystyle (n_{1},n_{2},\ldots ,n_{d})}$de índices d (basados ​​en cero)${\displaystyle n_{k}\in [0,N_{k}-1]}$.

En orden de filas, la última dimensión es contigua, por lo que el desplazamiento de memoria de este elemento viene dado por: $${\displaystyle n_{d}+N_{d}\cdot (n_{d-1}+N_{d-1}\cdot (n_{d-2}+N_{d-2}\cdot (\cdots +N_{2}n_{1})\cdots ))=\sum _{k=1}^{d}\left(\prod _{\ell =k+1}^{d}N_{\ell }\right)n_{k}}$$

En orden de columnas, la primera dimensión es contigua, por lo que el desplazamiento de memoria de este elemento viene dado por: $${\displaystyle n_{1}+N_{1}\cdot (n_{2}+N_{2}\cdot (n_{3}+N_{3}\cdot (\cdots +N_{d-1}n_{d})\cdots ))=\sum _{k=1}^{d}\left(\prod _{\ell =1}^{k-1}N_{\ell }\right)n_{k}}$$ donde el producto vacío es el elemento identidad multiplicativo , es decir,${\textstyle \prod _{\ell =1}^{0}N_{\ell }=\prod _{\ell =d+1}^{d}N_{\ell }=1}$.

Para un orden dado, el paso en la dimensión k viene dado por el valor de multiplicación entre paréntesis antes del índice n _k en las sumas del lado derecho anteriores.

En términos más generales, hay d! posibles órdenes para una matriz dada, una para cada permutación de dimensiones (siendo el orden por filas y el orden por columnas solo 2 casos especiales), aunque las listas de valores de paso no son necesariamente permutaciones entre sí, por ejemplo, en el ejemplo de 2 por 3 anterior, los pasos son (3,1) para el orden por filas y (1,2) para el orden por columnas.

• Matriz (estructura de datos)
• Comparación de lenguajes de programación (array)
• Origen del índice , otra diferencia entre los tipos de matrices en los distintos lenguajes de programación.
• Representación matricial
• El orden de Morton , otra forma de mapear datos multidimensionales a un índice unidimensional, resulta útil en estructuras de datos de árbol.
• Formato CSR , una técnica para almacenar matrices dispersas en memoria.
• Vectorización (matemáticas) , el equivalente a convertir una matriz en el vector columna principal correspondiente.

• Donald E. Knuth, El arte de la programación informática Volumen 1: Algoritmos fundamentales , tercera edición, sección 2.2.6 (Addison-Wesley: Nueva York, 1997).