Orden principal de filas y columnas

En informática, el orden principal de filas y el orden principal de 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 principal de la fila, los elementos consecutivos de una fila residen uno al lado del otro, mientras que lo mismo ocurre con los elementos consecutivos de una columna en el orden principal de la columna. Si bien los términos aluden a las filas y columnas de una matriz bidimensional, es decir, una matriz , los órdenes se pueden generalizar a matrices de cualquier dimensión observando que los términos fila principal y columna principal son equivalentes a órdenes lexicográficos y colexicográficos . respectivamente.

El diseño de los datos es fundamental para pasar correctamente matrices entre programas escritos en diferentes lenguajes de programación. También es importante para el rendimiento al atravesar una matriz porque las CPU modernas procesan datos secuenciales de manera más eficiente que los datos 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 medios, como el almacenamiento de datos en cinta magnética , el acceso secuencial es mucho más rápido que el acceso no secuencial. ^{[ cita necesaria ]}

Explicación y ejemplo.

Los términos fila principal y columna principal provienen de la terminología relacionada con el orden de objetos. Una forma general de ordenar objetos con muchos atributos es primero agruparlos y ordenarlos por un atributo, y luego, dentro de cada grupo, agruparlos y ordenarlos por otro atributo, etc. Si más de un atributo participa en el orden, el primero llamarse mayor y el último menor . Si dos atributos participan en el ordenamiento, basta con nombrar sólo el atributo principal.

En el caso de matrices, los atributos son los índices a lo largo de cada dimensión. Para matrices en notación matemática, el primer índice indica la fila y el segundo indica la columna ; por ejemplo, dada una matriz , la entrada 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] $A$ ${\ Displaystyle a_ {1,2}}$

Aunque la fila está indicada por el primer índice y la columna por el segundo índice, esto no implica ningún orden de agrupación entre las dimensiones. La elección de cómo agrupar y ordenar los índices, ya sea por métodos de fila principal o de columna principal, es, por tanto, 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 principales comienza desde el índice más a la izquierda y la columna principal desde el índice más a la derecha , lo que lleva a los órdenes lexicográfico y colexicográfico (o colex) , respectivamente.

Por ejemplo, la matriz

A=a_{y,x}={\begin{bmatrix}\color {Azul}a_{11}&\color {Azul}a_{12}&\color {Azul}a_{13}\\\ color {Naranja}a_{21}&\color {Naranja}a_{22}&\color {Naranja}a_{23}\end{bmatrix}}

podría almacenarse de dos formas posibles:

Los lenguajes de programación manejan esto de diferentes maneras. En C , las matrices multidimensionales se almacenan en orden de fila principal y los índices de la matriz se escriben en primera fila (orden de acceso lexicográfico):

Por otro lado, en Fortran , las matrices se almacenan en el orden de la columna principal, mientras que los índices de la matriz todavía se escriben primero en la fila (orden de acceso colexicográfico):

Observe cómo el uso de A[i][j]con indexación de varios pasos como en C, a diferencia de una notación neutra como A(i,j)en Fortran, casi inevitablemente implica un orden de fila principal por razones sintácticas, por así decirlo, porque se puede reescribir como (A[i])[j], y la A[i]fila La parte incluso 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 una columna principal simplemente por su notación, e incluso la implicación anterior podría eludirse intencionalmente en un nuevo lenguaje).

Para utilizar el orden de columnas principales en un entorno de filas principales, o viceversa, por cualquier motivo, una solución es asignar roles no convencionales a los índices (usando el primer índice para la columna y el segundo índice para la fila), y otra es evitar la sintaxis del lenguaje calculando explícitamente las posiciones en una matriz unidimensional. Por supuesto, desviarse de la convención probablemente implica un costo que aumenta con el grado de interacción necesaria con las características del lenguaje convencional y otros códigos, no sólo en forma de mayor vulnerabilidad a errores (olvidarse también invertir el orden de multiplicación de matrices, volver a la convención durante el código). mantenimiento, etc.), sino también en la forma de tener que reorganizar activamente los elementos, todos los cuales deben sopesarse frente a cualquier propósito original como aumentar el rendimiento. Se prefiere ejecutar el bucle por filas en lenguajes de filas principales como C y viceversa para lenguajes de columnas principales.

Lenguajes de programación y bibliotecas.

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

El orden de fila principal se utiliza en C / C++ / Objetive-C (para matrices estilo C), PL/I , ^[4] Pascal , ^[5] Speakeasy , ^{[ cita necesaria ]} y SAS . ^[6]

El orden de columna principal se utiliza en Fortran , MATLAB , ^[7] GNU Octave , Julia , ^[8] S , S-PLUS , ^[9] R , ^[10] Scilab , ^[11] Yorick y Rasdaman . ^[12]

Ni fila principal ni columna principal

Una alternativa típica para el almacenamiento de matrices densas es utilizar vectores de Iliffe , que normalmente almacenan punteros a elementos en la misma fila de forma contigua (como el orden de fila principal), pero no las filas en sí. Se utilizan en (ordenados por antigüedad): Java , ^[13] C# / CLI / .Net , Scala , ^[14] y Swift .

Aún menos denso es utilizar listas de listas, por ejemplo, en Python , ^[15] y en Wolfram Language de Wolfram Mathematica . ^[dieciséis]

Un enfoque alternativo utiliza tablas de tablas, por ejemplo, en Lua . ^[17]

Bibliotecas externas

Las bibliotecas externas también pueden proporcionar soporte para matrices multidimensionales, que incluso pueden admitir ordenamientos arbitrarios, donde cada dimensión tiene un valor de paso, y la fila principal o la columna principal son solo dos posibles interpretaciones resultantes.

El orden de las filas principales es el predeterminado en NumPy ^[18] (para Python).

El orden de las columnas principales es el predeterminado en Eigen ^[19] y Armadillo (ambos para C++).

Un caso especial sería OpenGL (y OpenGL ES ) para procesamiento de gráficos. Dado que "los tratamientos matemáticos recientes del álgebra lineal y campos relacionados invariablemente tratan los vectores como columnas", el diseñador Mark Segal decidió sustituir esto por la convención del predecesor IRIS GL , que era escribir vectores como filas; por compatibilidad, las matrices de transformación aún se almacenarían en orden de vector principal (= fila principal) en lugar de orden de coordenadas principal (= columna principal), y luego usó el truco "[para] decir que las matrices en OpenGL se almacenan en orden de columna principal". ^[20] En realidad, esto solo era relevante para la presentación, porque la multiplicación de matrices estaba basada en pilas y aún podía interpretarse como post-multiplicación, pero, peor aún, la realidad se filtraba a través de la API basada en C porque se accedería a los elementos individuales como M[vector][coordinate]o, efectivamente , M[column][row], lo que desafortunadamente confundió la convención que el diseñador buscaba adoptar, y esto incluso se conservó en el lenguaje de sombreado OpenGL que se agregó más tarde (aunque esto también hace posible acceder a las coordenadas por nombre, por ejemplo, M[vector].y). Como resultado, muchos desarrolladores ahora simplemente declararán que tener la columna como primer índice es la definición de columna principal, aunque este claramente no es el caso con un lenguaje de columna principal real como Fortran.

La antorcha (para Lua) cambió del orden predeterminado de columna principal ^[21] a fila principal ^[22] .

Transposición

Como intercambiar los índices de una matriz es la esencia de la transposición de matrices , una matriz almacenada como fila principal pero leída como columna principal (o viceversa) aparecerá transpuesta (siempre que la matriz sea cuadrada). Como en realidad realizar esta reordenación en la memoria suele ser una operación costosa, algunos sistemas brindan opciones para especificar matrices individuales que se almacenan transpuestas. Luego, el programador debe decidir si reorganiza o no los elementos en la memoria, según el uso real (incluido el número de veces que se reutiliza la matriz en un cálculo).

Por ejemplo, a las funciones de subprogramas de álgebra lineal básica se les pasan indicadores que indican qué matrices se transponen. ^[23]

Cálculo de direcciones en general.

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

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

En orden de fila principal, la última dimensión es contigua, de modo que el desplazamiento de memoria de este elemento viene dado por:

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 } \derecha)n_{k}

En el orden de las columnas principales, la primera dimensión es contigua, de modo que el desplazamiento de memoria de este elemento viene dado por:

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}

producto vacío elemento identidad

{\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 sumatorias del lado derecho anteriores.

De manera más general, hay d! órdenes posibles para una matriz dada, una para cada permutación de dimensiones (con el orden de fila principal y el orden de columna solo 2 casos especiales), aunque las listas de valores de zancada no son necesariamente permutaciones entre sí, por ejemplo, en el orden de 2 por En el ejemplo anterior, los pasos son (3,1) para la fila principal y (1,2) para la columna principal.

Ver también

Estructura de datos de matriz
Representación matricial
Vectorización (matemáticas) , el equivalente a convertir una matriz en el vector de columna principal correspondiente
Formato CSR , una técnica para almacenar matrices dispersas en memoria
Orden de Morton , otra forma de asignar datos multidimensionales a un índice unidimensional, útil en estructuras de datos de árbol

Referencias

^ "Memoria caché". Peter Lars Dordal . Consultado el 10 de abril de 2021 .
^ "Matrices y E/S formateadas". Tutorial de FORTRAN . Consultado el 19 de noviembre de 2016 .
^ "Por qué la numeración debería comenzar desde cero". Archivo EW Dijkstra . Consultado el 2 de febrero de 2017 .
^ "Referencia de idioma versión 4 versión 3" (PDF) . IBM . Consultado el 13 de noviembre de 2017 . Los valores iniciales especificados para una matriz se asignan a elementos sucesivos de la matriz en orden de fila principal (el subíndice final varía más rápidamente).
^ "ISO/IEC 7185:1990(E)" (PDF) . Un tipo de matriz que especifica una secuencia de dos o más tipos de índice será una notación abreviada para un tipo de matriz especificado que tenga como tipo de índice el primer tipo de índice de la secuencia y que tenga un tipo de componente que sea un tipo de matriz que especifica la secuencia de tipos de índice sin el primer tipo de índice en la secuencia y que especifica el mismo tipo de componente que la especificación original.
^ "Referencia del lenguaje SAS® 9.4: conceptos, sexta edición" (PDF) . SAS Institute Inc. 6 de septiembre de 2017. p. 573 . Consultado el 18 de noviembre de 2017 . De derecha a izquierda, la dimensión más a la derecha representa columnas; la siguiente dimensión representa filas. [...] SAS coloca variables en una matriz multidimensional llenando todas las filas en orden, comenzando en la esquina superior izquierda de la matriz (conocido como orden de fila principal).
^ Documentación de MATLAB, MATLAB Data Storage (obtenido de Mathworks.co.uk, enero de 2014).
^ "Matrices multidimensionales". Julia . Consultado el 9 de noviembre de 2020 .
^ Spiegelhalter y col. (2003, p. 17): Spiegelhalter, David ; Tomás, Andrés; Mejor, Nicky ; Lunn, Dave (enero de 2003), "Formato de datos: formato S-Plus", Manual de usuario de WinBUGS (PDF) (Versión 1.4 ed.), Cambridge, Reino Unido: Unidad de Bioestadística MRC, Instituto de Salud Pública, archivado desde el original ( PDF) el 2003-05-18
^ Introducción a R , Sección 5.1: Matrices (consultado en marzo de 2010).
^ "FFT con datos multidimensionales". Wiki Scilab . Consultado el 25 de noviembre de 2017 . Debido a que Scilab almacena matrices en formato de columna principal, los elementos de una columna son adyacentes (es decir, una separación de 1) en formato lineal.
^ "Representación de matriz interna en rasdaman". rasdaman.org . Consultado el 29 de mayo de 2022 .
^ "Especificación del lenguaje Java". Oráculo . Consultado el 13 de febrero de 2016 .
^ "matriz de objetos". Biblioteca estándar de Scala . Consultado el 1 de mayo de 2016 .
^ "La biblioteca estándar de Python: 8. Tipos de datos" . Consultado el 18 de noviembre de 2017 .
^ "Vectores y matrices". Wolframio . Consultado el 12 de noviembre de 2017 .
^ "11.2 - Matrices y matrices multidimensionales" . Consultado el 6 de febrero de 2016 .
^ "La matriz N-dimensional (ndarray)". SciPy.org . Consultado el 3 de abril de 2016 .
^ "Eigen: Órdenes de almacenamiento". eigen.tuxfamily.org . Consultado el 23 de noviembre de 2017 . Si no se especifica el orden de almacenamiento, Eigen almacena de forma predeterminada la entrada en la columna principal.
^ "Vectores de columna versus vectores de fila" . Consultado el 12 de noviembre de 2017 .
^ "Tensor" . Consultado el 6 de febrero de 2016 .
^ "Tensor". Manual de referencia del paquete de antorcha . Consultado el 8 de mayo de 2016 .
^ "BLAS (Subprogramas de Álgebra Lineal Básica)" . Consultado el 16 de mayo de 2015 .

Fuentes

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).