En informática, el orden principal por filas y el orden principal por columnas son métodos para almacenar matrices multidimensionales en un 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 de fila principal, los elementos consecutivos de una fila residen uno al lado del otro, mientras que lo mismo es válido para los elementos consecutivos de una columna en el orden de columna principal. 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 los órdenes lexicográfico y colexicográfico , respectivamente. También vale la pena señalar que las matrices, que se representan comúnmente como colecciones de vectores de fila o columna, utilizando este enfoque se almacenan efectivamente como vectores consecutivos o componentes de vectores consecutivos. Estas formas de almacenar datos se conocen como AoS y SoA respectivamente.
La disposición 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 recorrer 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 explota 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 órdenes de magnitud más rápido que el acceso no secuencial. [ cita requerida ]
Los términos fila principal y columna principal provienen de la terminología relacionada con la ordenación de objetos. Una forma general de ordenar objetos con muchos atributos es primero agruparlos y ordenarlos por un atributo y luego, dentro de cada uno de esos grupos, agruparlos y ordenarlos por otro atributo, etc. Si más de un atributo participa en la ordenación, el primero se llamaría principal y el último secundario . Si dos atributos participan en la ordenación, es suficiente nombrar solo el atributo principal.
En el caso de las matrices, 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 , 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]
Aunque la fila se indica mediante el primer índice y la columna mediante 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 mediante métodos de ordenación por filas o por columnas, 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 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
Podría almacenarse de dos maneras 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 primero en fila (orden de acceso lexicográfico):
Por otro lado, en Fortran , las matrices se almacenan en orden de columna principal, mientras que los índices de las matrices todavía se escriben primero en fila (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 oposición a una notación neutral como A(i,j)en Fortran, implica casi inevitablemente un orden de fila principal por razones sintácticas, por así decirlo, porque puede reescribirse como (A[i])[j], y la A[i]parte de fila puede incluso asignarse 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 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 en un entorno de filas, o viceversa, por cualquier razón, una solución alternativa es asignar funciones no convencionales a los índices (utilizando 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 otro código, no solo en forma de mayor vulnerabilidad a errores (olvidar también invertir 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 elementos activamente, 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 con orden de filas como C y viceversa para lenguajes con orden de columnas.
Los lenguajes de programación o sus bibliotecas estándar que admiten matrices multidimensionales generalmente tienen un orden de almacenamiento nativo por fila o por columna para estas matrices.
El orden de filas principales se utiliza en C / C++ / Objective-C (para matrices de estilo C), PL/I , [4] Pascal , [5] Speakeasy , [ cita requerida ] y SAS . [6]
El orden de columna principal se utiliza en Fortran , [7] [8] IDL , [7] MATLAB , [8] GNU Octave , Julia , [9] S , S-PLUS , [10] R , [11] Scilab , [12] Yorick y Rasdaman . [13]
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 , [14] C# / CLI / .Net , Scala , [15] y Swift .
Aún menos denso es utilizar listas de listas, por ejemplo, en Python , [16] y en el lenguaje Wolfram de Wolfram Mathematica . [17]
Un enfoque alternativo utiliza tablas de tablas, por ejemplo, en Lua . [18]
Las bibliotecas externas también pueden brindar 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 filas principales es el predeterminado en NumPy [19] (para Python).
El orden de columnas principales es el predeterminado en Eigen [20] y Armadillo (ambos para C++).
Un caso especial sería OpenGL (y OpenGL ES ) para el 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 en el predecesor IRIS GL , que era escribir los vectores como filas; por compatibilidad, las matrices de transformación todavía se almacenarían en orden de vector principal (=fila principal) en lugar de orden de coordenadas principales (=columna principal), y luego usó el truco "[para] decir que las matrices en OpenGL se almacenan en orden de columna principal". [21] Esto realmente solo era relevante para la presentación, porque la multiplicación de matrices estaba basada en pilas y todavía podía interpretarse como post-multiplicación, pero, peor aún, la realidad se filtró 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 buscó 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 el primer índice es la definición de columna principal, aunque claramente este no es el caso con un lenguaje de columna principal real como Fortran.
La antorcha (para Lua) cambió del orden predeterminado de columna principal [22] a fila principal [23] .
Como el intercambio de los índices de una matriz es la esencia de la transposición de matrices , una matriz almacenada como de fila principal pero leída como de columna principal (o viceversa) aparecerá transpuesta. Como realizar esta reorganización en la memoria suele ser una operación costosa, algunos sistemas proporcionan opciones para especificar matrices individuales como almacenadas transpuestas. El programador debe decidir si reorganiza o no los elementos en la memoria, en función del uso real (incluida la cantidad 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. [24]
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 d índices (basados en cero) .
En orden de fila principal, la última dimensión es contigua, de modo que el desplazamiento de memoria de este elemento viene dado por:
En orden de columna principal, la primera dimensión es contigua, de modo que el desplazamiento de memoria de este elemento está dado por: donde el producto vacío es el elemento identidad multiplicativo , es decir, .
Para un orden dado, el paso en dimensión k está dado por el valor de multiplicación entre paréntesis antes del índice n k en las sumas del lado derecho anteriores.
De manera más general, hay d! órdenes posibles para una matriz dada, uno para cada permutación de dimensiones (siendo el orden de fila principal y el orden de columna solo dos casos especiales), aunque las listas de valores de pasos no son necesariamente permutaciones entre sí, por ejemplo, en el ejemplo 2 por 3 anterior, los pasos son (3,1) para el orden de fila principal y (1,2) para el orden de columna principal.
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).
Un tipo de matriz que especifica una secuencia de dos o más tipos de índices debe ser una notación abreviada para un tipo de matriz especificado para tener como tipo de índice el primer tipo de índice en la secuencia y para tener un tipo de componente que es un tipo de matriz que especifica la secuencia de tipos de índices sin el primer tipo de índice en la secuencia y que especifica el mismo tipo de componente que la especificación original.
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).
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.
Si no se especifica el orden de almacenamiento, Eigen almacena la entrada en la columna principal de forma predeterminada.
![{\displaystyle n_{k}\en [0,N_{k}-1]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5aa8454b8e8f1d95f6d3198688f0d45e9185738f)
