Ordem de linha e de coluna

Na computação, ordem de linha e ordem de coluna são métodos para armazenar matrizes multidimensionais [en] em armazenamento linear, como a memória de acesso aleatório (RAM).

A diferença entre as ordens reside em quais elementos de um arranjo (array) são contíguos na memória. Na ordem de linha, os elementos consecutivos de uma linha residem próximos uns dos outros, enquanto o mesmo vale para elementos consecutivos de uma coluna na ordem de coluna. Embora os termos aludam às 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 ordem de linha e ordem de coluna são equivalentes às ordens lexicográfica e colexicográfica, respectivamente. As matrizes, sendo comumente representadas como coleções de vetores de linha ou coluna, usando essa abordagem, são efetivamente armazenadas como vetores consecutivos ou componentes vetoriais consecutivos. Tais formas de armazenar dados são referidas como AoS e SoA [en], respectivamente.

O layout de dados é crítico para passar arranjos corretamente entre programas escritos em diferentes linguagens de programação. Também é importante para o desempenho ao percorrer um arranjo porque as CPUs modernas processam dados sequenciais de forma mais eficiente do que dados não sequenciais. Isso se deve principalmente ao cache da CPU, que explora a localidade de referência espacial.^[1] Além disso, o acesso contíguo torna possível usar instruções SIMD (instrução única, dados múltiplos) que operam em vetores de dados. Em algumas mídias, como armazenamento de dados em fita magnética [en], o acesso sequencial é ordens de magnitude mais rápido do que o acesso não sequencial.^{[carece de fontes?]}

Os termos ordem de linha (row-major) e ordem de coluna (column-major) 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 participar da ordenação, o primeiro seria chamado de maior (major) e o último de menor (minor). Se dois atributos participarem da ordenação, é suficiente nomear apenas o atributo maior.

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

Embora a linha seja indicada pelo primeiro índice e a coluna pelo segundo índice, nenhuma ordem de agrupamento entre as dimensões é implícita por isso. A escolha de como agrupar e ordenar os índices, seja pelos métodos de ordem de linha ou ordem de coluna, é, portanto, uma questão de convenção. A mesma terminologia pode ser aplicada a arranjos de dimensões ainda maiores. O agrupamento por ordem de linha começa no índice mais à esquerda e o por ordem de coluna no índice mais à direita, levando a ordens lexicográfica e colexicográfica (ou colex), respectivamente.

Por exemplo, a 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}}}$

poderia ser armazenada de duas maneiras possíveis:

Endereço	Ordem de linha	Ordem de coluna
0	${\displaystyle \color {Blue}a_{11}}$	${\displaystyle \color {Blue}a_{11}}$
1	${\displaystyle \color {Blue}a_{12}}$	${\displaystyle \color {Orange}a_{21}}$
2	${\displaystyle \color {Blue}a_{13}}$	${\displaystyle \color {Blue}a_{12}}$
3	${\displaystyle \color {Orange}a_{21}}$	${\displaystyle \color {Orange}a_{22}}$
4	${\displaystyle \color {Orange}a_{22}}$	${\displaystyle \color {Blue}a_{13}}$
5	${\displaystyle \color {Orange}a_{23}}$	${\displaystyle \color {Orange}a_{23}}$

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

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

Endereço x + N_x*y	Acesso A[y][x]	Valor ${\displaystyle a_{y,x}}$
0	A[0][0]	${\displaystyle a_{11}}$
1	A[0][1]	${\displaystyle a_{12}}$
2	A[0][2]	${\displaystyle a_{13}}$
3	A[1][0]	${\displaystyle a_{21}}$
4	A[1][1]	${\displaystyle a_{22}}$
5	A[1][2]	${\displaystyle a_{23}}$

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

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

Endereço y + N_y*(x-1)	Acesso A(y,x)	Valor ${\displaystyle a_{y,x}}$
1	A(1,1)	${\displaystyle a_{11}}$
2	A(2,1)	${\displaystyle a_{21}}$
3	A(1,2)	${\displaystyle a_{12}}$
4	A(2,2)	${\displaystyle a_{22}}$
5	A(1,3)	${\displaystyle a_{13}}$
6	A(2,3)	${\displaystyle a_{23}}$

Observe como o uso de A[i][j] com indexação em várias etapas como em C, ao contrário de uma notação neutra como A(i,j) como em Fortran, quase inevitavelmente implica ordem 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é ser atribuída a 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 é ordem 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 de coluna em um ambiente de ordem de linha, ou vice-versa, por qualquer motivo, uma solução alternativa é atribuir papéis não convencionais aos índices (usando o primeiro índice para a coluna e o segundo índice para a linha), e outra é ignorar a sintaxe da linguagem calculando explicitamente as posições em um arranjo unidimensional. Obviamente, desviar da convenção provavelmente incorre em um custo que aumenta com o grau de interação necessária com os recursos da linguagem convencional e outros códigos, não apenas na forma de maior vulnerabilidade a erros (esquecer de também inverter a ordem de multiplicação da matriz, reverter para a convenção durante a manutenção do código, etc.), mas também na forma de ter que reorganizar ativamente os elementos, o que deve ser pesado contra qualquer propósito original, como aumentar o desempenho. Executar o loop no sentido da linha é preferível em linguagens de ordem de linha como C e vice-versa para linguagens de ordem de coluna.

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

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

A ordem de coluna é usada em Fortran,^[7][8] IDL [en],^[7] MATLAB,^[8] GNU Octave, Julia,^[9] S, S-PLUS,^[10] R,^[11] Scilab,^[12] Yorick e rasdaman [en].^[13]

Uma alternativa típica para armazenamento de arranjos densos é usar vetores de Iliffe [en], que normalmente armazenam ponteiros para elementos na mesma linha de forma contígua (como ordem de linha), mas não as linhas em si. Eles são usados em (ordenados por idade): Java,^[14] C#/CLI/.Net, Scala,^[15] e Swift.

Ainda menos denso é usar listas de listas, por exemplo, em Python,^[16] e na Wolfram do Wolfram Mathematica.^[17]

Uma abordagem alternativa usa tabelas de tabelas, por exemplo, em Lua.^[18]

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

A ordem de linha é o padrão no NumPy^[19] (para Python).

A ordem de coluna é o padrão no Eigen [en]^[20] e Armadillo (ambos para C++).

Um caso especial seria o OpenGL (e OpenGL ES) para processamento gráfico. Como "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 no predecessor IRIS GL [en], que era escrever vetores como linhas; para compatibilidade, as matrizes de transformação ainda seriam armazenadas em ordem de vetor-maior (=ordem de linha) em vez de coordenada-maior (=ordem de coluna), e ele então usou o truque "[de] dizer que as matrizes no OpenGL são armazenadas em ordem de coluna".^[21] Isso era realmente relevante apenas para apresentação, porque a multiplicação de matrizes era baseada em pilha e ainda podia ser interpretada como pós-multiplicação, mas, pior, a realidade vazou através da API baseada em C porque elementos individuais seriam acessados como M[vetor][coordenada] ou, efetivamente, M[coluna][linha], o que infelizmente confundiu a convenção que o designer procurava adotar, e isso foi até preservado na OpenGL Shading Language que foi adicionada posteriormente (embora isso também torne possível 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 de ordem de coluna, embora este claramente não seja o caso com uma linguagem de ordem de coluna real como Fortran.

Torch [en] (para Lua) mudou da ordem de coluna^[22] para a ordem de linha^[23] padrão.

Como trocar os índices de um arranjo é a essência da transposição de arranjo, um arranjo armazenado como ordem de linha, mas lido como ordem de coluna (ou vice-versa), parecerá transposto. Como a realização real desse rearranjo na memória [en] é tipicamente uma operação cara, alguns sistemas fornecem opções para especificar matrizes individuais como sendo armazenadas transpostas. O programador deve então decidir se deve ou não reorganizar 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 [en] recebem sinalizadores indicando quais arranjos estão transpostos.^[24]

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

Para um arranjo de dimensão d ${\displaystyle N_{1}\times N_{2}\times \cdots \times N_{d}}$ com dimensões N_k (k=1...d), um dado elemento desse arranjo é especificado por uma tupla ${\displaystyle (n_{1},n_{2},\ldots ,n_{d})}$ de d índices (baseados em zero) ${\displaystyle n_{k}\in [0,N_{k}-1]}$.

Na ordem de linha, a última dimensão é contígua, de modo que o deslocamento de memória (memory-offset) desse elemento é 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}}$$

Na ordem de coluna, a primeira dimensão é contígua, de modo que o deslocamento de memória desse elemento é 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}}$$ onde o produto vazio é o elemento neutro multiplicativo, ou seja, ${\textstyle \prod _{\ell =1}^{0}N_{\ell }=\prod _{\ell =d+1}^{d}N_{\ell }=1}$.

Para uma dada ordem, o passo [en] (stride) na dimensão k é dado pelo valor de multiplicação entre parênteses antes do índice n_k nas somas do lado direito acima.

Mais geralmente, existem d! ordens possíveis para um determinado arranjo, uma para cada permutação de dimensões (com ordem de linha e ordem de coluna sendo apenas 2 casos especiais), embora as listas de valores de passo não sejam necessariamente permutações uma da outra, por exemplo, no exemplo 2 por 3 acima, os passos são (3,1) para ordem de linha e (1,2) para ordem de coluna.

• Arranjo (estrutura de dados)
• Comparação de linguagens de programação (arranjo) [en]
• Matriz esparsa
• Ordem de Morton [en], outra maneira de mapear dados multidimensionais para um índice unidimensional
• Origem do índice [en], outra diferença entre os tipos de arranjo em diferentes linguagens de programação
• Representação de matriz [en]
• Vetorização (matemática) [en], o equivalente a transformar uma matriz no vetor de ordem de coluna correspondente

Referências

• Donald E. Knuth, The Art of Computer Programming Volume 1: Fundamental Algorithms, third edition, section 2.2.6 (Addison-Wesley: New York, 1997).