Ordem principal de linha e de coluna

Na computação, ordem principal de linha e ordem principal de coluna são métodos para armazenar arranjos multidimensionais em armazenamento linear, como no caso da memória de acesso aleatório.

Ilustração da diferença entre a ordem principal de linha e de coluna

A diferença entre as ordens reside em quais elementos de um arranjo são contíguos na memória. Na ordem principal de linha, os elementos consecutivos de uma linha residem um ao lado do outro, enquanto o mesmo se aplica a elementos consecutivos de uma coluna na ordem principal de coluna. Enquanto os termos aludem à linhas e colunas de um arranjo bidimensional, ou seja, uma matriz, as ordens podem ser generalizadas para arranjos de qualquer dimensão, observando que os termos pricipal de linha e principal de coluna são equivalentes, respectivamente, a ordens lexicográficas e colexicográficas.

O layout de dados é crítico para a transmissão correta de arranjos entre programas escritos em diferentes linguagens de programação. Ele também é importante para o desempenho ao percorrer um arranjo, porque as CPUs modernas processam dados sequenciais com mais eficiência do que dados não sequenciais. ​Isso se deve principalmente ao armazenamento em cache da CPU, que explora a localidade espacial de referência. Além disso, o acesso contíguo possibilita o uso de instruções SIMD que operam sobre vetores de dados. Em algumas mídias, como fitas ou memórias flash NAND, o acesso sequencial é mais rápido, em ordens de magnitude, do que o acesso não sequencial.^{[carece de fontes]}

Explicação e exemplo

Os termos principal de linha e principal de coluna derivam da terminologia relacionada à ordenação de objetos. Uma maneira geral de ordenar objetos com muitos atributos é primeiro agrupá-los e ordená-los por um atributo e, em seguida, dentro de cada grupo, agrupá-los e ordená-los por outro atributo, etc. Se mais de um atributo participa do pedido, o primeiro seria denominado principal e o último secundário. Se dois atributos participam do pedido, é suficiente nomear apenas o atributo principal.

No caso de arranjos, os índices ao longo de cada dimensão são os atributos. Para matrizes em notação matemática, o primeiro índice indica a linha, e o segundo indica a coluna. Por exemplo, dada uma matriz $A$, $a_{1,2}$ está em sua primeira linha e segunda coluna. Esta convenção é transportada para a sintaxe em linguagens de programação, embora, frequentemente, com índices começando em 0 (em vez de 1).

Mesmo que a linha seja indicada no primeiro e a coluna no segundo (do índice), nenhuma ordem de agrupamento entre as dimensões está implícita nisso. A escolha de como agrupar e ordenar os índices, seja pelos métodos principais de linha ou de coluna, é, portanto, uma questão de convenção. A mesma terminologia pode ser aplicada a arranjos dimensionais ainda mais altos. O agrupamento principal de linha começa no índice "mais à esquerda" e o principal de coluna "mais à direita", levando, respectivamente, à ordens lexicográficas e colexicográficas (ou colex).

Por exemplo, o arranjo

$A={\begin{bmatrix}a_{11}&a_{12}&a_{13}\\a_{21}&a_{22}&a_{23}\end{bmatrix}}$

pode ser armazenado de duas maneiras possíveis:

Endereço	Ordem principal de linha	Ordem principal de coluna
0	$a_{11}$	$a_{11}$
1	$a_{12}$	$a_{21}$
2	$a_{13}$	$a_{12}$
3	$a_{21}$	$a_{22}$
4	$a_{22}$	$a_{13}$
5	$a_{23}$	$a_{23}$

Diferentes linguagens de programação lidam com isso de maneiras diferentes. Em C, os arranjos multidimensionais são armazenados na ordem principal de linha e os índices do arranjo são escritos primeiro em linha (ordem de acesso lexicográfico):

C: ordem principal de linha (ordem de acesso lexicográfico), indexação baseada em zero

Endereço	Acesso	Valor
0	A[0][0]	$a_{11}$
1	A[0][1]	$a_{12}$
2	A[0][2]	$a_{13}$
3	A[1][0]	$a_{21}$
4	A[1][1]	$a_{22}$
5	A[1][2]	$a_{23}$

Por outro lado, em Fortran, os arranjos são armazenados na ordem principal de coluna, enquanto os índices do arranjo ainda são escritos, primeiro, em linha (ordem de acesso colexicográfico):

Fortran: ordem principal de coluna (ordem de acesso colexicográfico), indexação baseada em um

Endereço	Acesso	Valor
1	A(1,1)	$a_{11}$
2	A(2,1)	$a_{21}$
3	A(1,2)	$a_{12}$
4	A(2,2)	$a_{22}$
5	A(1,3)	$a_{13}$
6	A(2,3)	$a_{23}$

Observe como o uso de A[i][j] com indexação de várias etapas (como em C) em vez de uma notação neutra como A(i,j) (como em Fortran), quase que inevitavelmente, implica em ordem principal de linha por razões sintáticas, por assim dizer, porque pode ser reescrito como (A[i])[j],e a parte da linha, A[i], pode até mesmo ser atribuída à uma variável intermediária que é, então, indexada em uma expressão separada. Nenhuma outra implicação deve ser assumida. Por exemplo, Fortran não é principal de coluna simplesmente "por causa" de sua notação e mesmo a implicação acima poderia ser intencionalmente contornada em uma nova linguagem.

Para usar a ordem principal de coluna em um ambiente de ordem principal de linha (ou vice-versa), por qualquer motivo, uma solução alternativa é atribuir funções não convencionais aos índices (usando o primeiro índice para a coluna e o segundo índice para a linha) e outra é contornar a sintaxe da linguagem computando explicitamente as posições em um arranjo unidimensional. Obviamente, o desvio da convenção provavelmente incorre em um custo que aumenta o grau de interação necessária com os recursos da linguagem e outros códigos, não apenas na forma de maior vulnerabilidade à erros (esquecendo também de inverter a ordem de multiplicação da matriz, revertendo para a convenção durante manutenção de código, etc.) mas também na forma de ter que reorganizar ativamente os elementos (todos os quais devem ser "pesados" em relação à qualquer propósito original, como aumentar o desempenho). A execução do loop por linha é preferível em linguagens principais de linha, como C, e vice-versa para linguagens principais de coluna.

Linguagens de programação e bibliotecas

Linguagens de programação ou suas bibliotecas padrão que oferecem suporte a arranjos multidimensionais, normalmente, têm uma ordem de armazenamento principal de linha ou coluna nativa para esses arranjos.

A ordem principal de linha é usada em C/C++/Objective-C (para arranjos de estilo C), PL/I, Pascal​, Speakeasy^{[carece de fontes]}, SAS e Rasdaman.

A ordem principal de coluna é usada em Fortran, MATLAB, GNU Octave, S-PLUS, R, Julia, e Scilab.

Nem principal de linha nem de coluna

Uma alternativa típica para armazenamento de arranjo densa é usar vetores Iliffe, que normalmente armazena elementos na mesma linha de forma contígua (como a ordem principal de linha), mas não as próprias linhas. Eles são usados em (ordenados por idade): Java, C#/CLI/.Net, Scala e Swift.

Ainda menos denso é usar listas de listas, por exemplo, em Python e na Wolfram do Mathematica'".

Uma abordagem alternativa usa tabelas de tabelas, por exemplo, em Lua.

Bibliotecas externas

O suporte para arranjos multidimensionais também pode ser fornecido por bibliotecas externas, que podem até mesmo suportar ordenações arbitrárias, em que cada dimensão tem um valor de passo e principal de linha ou de coluna são apenas duas interpretações resultantes possíveis.

A ordem principal de linha é o padrão em NumPy (para Python).

A ordem principal de coluna é o padrão em Eigen e Armadillo (ambas para C++).

Um caso especial seria o OpenGL (e o OpenGL ES) para processamento gráfico. Uma vez que "tratamentos matemáticos recentes de álgebra linear e campos relacionados invariavelmente tratam vetores como colunas", o designer Mark Segal decidiu substituir isso pela convenção do predecessor IRIS GL (que era escrever vetores como linhas). Para compatibilidade, matrizes de transformação ainda seriam armazenadas em principal de vetor (o mesmo que principal de linha) em vez de ordem principal de coordenada (o mesmo que principal de coluna) e ele então usou o truque "[para] dizer que matrizes em OpenGL são armazenadas em ordem principal de coluna". Isso era realmente relevante apenas para apresentação, porque a multiplicação da matriz era baseada em pilha e ainda podia ser interpretada como pós-multiplicação mas a realidade vazou através da API baseada em C porque os elementos individuais seriam acessados como M[vetor][coordenada] ou, efetivamente, como M[coluna][linha] (que infelizmente confundiu a convenção que o designer procurou adotar) e isso foi até preservado na OpenGL Shading Language que foi adicionada posteriormente (embora isso também possibilite acessar coordenadas por nome, por exemplo, M[vetor].y). Como resultado, muitos desenvolvedores agora simplesmente declararão que ter a coluna como o primeiro índice é a definição principal de coluna, embora este claramente não seja o caso com uma linguagem principal de coluna real como o Fortran.

Torch (para Lua) mudou a ordem padrão de principal de coluna para principal de linha.

Transposição

Como a troca dos índices de um arranjo é a essência da transposição de arranjo, um arranjo armazenado como principal de linha, mas lido como principal de coluna (ou vice-versa), aparecerá transposto (desde que a matriz seja quadrada). Como realizar esse rearranjo na memória costuma ser uma operação cara, alguns sistemas oferecem opções para especificar matrizes individuais como sendo armazenadas transpostas. O programador deve, então, decidir se reorganiza ou não os elementos na memória, com base no uso real (incluindo o número de vezes que o arranjo é reutilizado em um cálculo).

Por exemplo, as funções BLAS recebem sinalizadores que indicam quais arranjos são transpostos.

Cálculo de endereço em geral

O conceito se generaliza para arranjos com mais de duas dimensões.

Para um arranjo d-dimensional $N_{1}\times N_{2}\times \cdots \times N_{d}$ com dimensões N_k (k=1...d), um determinado elemento deste arranjo é especificado por uma tupla $(n_{1},n_{2},\ldots ,n_{d})$ de índices d (base zero) $n_{k}\in [0,N_{k}-1]$.

Na ordem principal de linha , a última dimensão é contígua, de modo que o deslocamento da memória deste elemento é 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 }\right)n_{k}$

Na ordem principal de coluna , a primeira dimensão é contígua, de modo que o deslocamento da memória deste elemento é 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}$

onde o produto vazio é o elemento de identidade multiplicativo, ou seja,$\prod _{\ell =1}^{0}N_{\ell }=\prod _{\ell =d+1}^{d}N_{\ell }=1$.

Para uma determinada ordem, o "dar passos longos" na dimensão k é dado pelo valor de multiplicação entre parênteses antes do índice n _k nos somatórios do lado direito acima.

De forma mais geral, há "d!" ordens possíveis para um determinada arranjo, uma para cada permutação de dimensões (com principal de linha e ordem de coluna apenas 2 casos especiais), embora as listas de valores de passo não sejam necessariamente permutações entre si, por exemplo, no exemplo 2 por 3 acima, os avanços são (3,1) para principal de linha e (1,2) para principal de coluna.

Ver também

• Arranjo (computação)

Fontes

• Donald E. Knuth, A arte da programação de computadores Volume 1: Algoritmos fundamentais, terceira edição, seção 2.2.6 (Addison-Wesley: Nova York, 1997).