Outra vez: Arrays e ponteiros…

Recentemente topei com a seguinte dúvida de um leitor: “Se um item de um array é referenciado por seu ponteiro-base e um offset, uma matriz é um array de ponteiros?”. Infelizmente, não! Para exemplificar, eis o que eu disse, até agora sobre arrays:

Um array e um ponteiro

No caso acima, o ponteiro p aponta para o primeiro item do array a. Note que a variável p contém, em seu interior, o endereço deste primeiro item. Isso significa que se derreferenciarmos o ponteiro p (com o operador de indireção *), obteremos o conteúdo de a[0]. Ou seja: a[0] = *(p+0) = *(a+0). Mas, note o que acontece com um array de ponteiros:

array de ponteiros para char

Cada ítem de a é, em si, um ponteiro para um bloco de chars. Agora, eis a diferença entre isso e um array bidimensional:

Array bidimensional

O símbolo a continua sendo um ponteiro para o primeiro item do array, mas a estrutura, na memória, é a de um array unidimensional simples, onde cada linha tem 9 chars. Os caracteres adicionais, em cada linhas, que não foram preenchidos são automaticamente preenchidos com zeros.

Repare que, na notação da linguagem C, podemos especificar um array “incompleto”, mas somente na última dimensão (a mais a esquerda). Isso é assim porque o compilador precisa saber qual é o tamanho de cada “linha” da “matriz” para calcular a posição inicial da linha desejada… No caso, a especificação a[1][4] é calculada como a+9\cdot1+3, ou, de forma mais genérica:

\displaystyle a[l][c] = *(a + l\cdot C+c)

Onde C é a quantidade de colunas que uma linha possui e as variáveis minúsculas l (letra “éle”) e c correspondem a linha e coluna desejadas. Precisamos multiplicar a linha desejada pelo número de colunas que o array tem e depois adicionar a coluna desejada para obter o offset, em relação ao ponteiro-base a. Note que, em ambos os casos, a especificação a[1][4] nos dará o caracter ‘a’, que está na 13ª posição do array unidimensional equivalente.

Mas, como isso fica se tivermos um array de 3 ou mais dimensões?  Para tornar o cálculo mais simples, especificarei um array “tridimensional” assim: T a[Z][Y][X], onde T é um tipo qualquer e (X,Y,Z) são os tamanhos de cada dimensão. De novo, usarei (x,y,z), minúsculos, para especificar uma posição desejada…

Em primeiro lugar, o tamanho desse array é de X\cdot Y\cdot Z\cdot sizeof(T) bytes e, para encontrarmos o início do array bidimensional especificado por z, precisamos calcular o offset assim: z\cdot X\cdot Y, porque cada uma dessas “camadas” têm X\cdot Y de tamanho. De maneira similar ao array bidimensional, para achar uma coluna nessa “camada”, precisamos fazer y\cdot X+x. Assim, a posição (x,y,z) do array a é derreferenciada como a[z][y][x] = *(a + X\cdot Y\cdot z + X\cdot y + x).

Na notação de arrays, o compilador faz esses cálculos pra você… mas, é bom lembrar que isso é completamente diferente de usar três indireções.

Ahhh. Uma dica: Se for criar arrays multidimensionais, tenha certeza de que as dimensões inferiores tenham tamanho múltiplo de 2^n. Isso porque, já que o compilador terá que usar multiplicações para calcular o offset, dessa maneira ele usará apenas shifts lógicos. Acelera um bocado… Já a dimensão de alta ordem, que não é usada no cálculo do offset como fator multiplicativo, pode ser de qualquer tamanho… Assim, criar um array int a[10][10] é bem menos performático do que criar um int a[10][16]. Você gasta um pouco mais de espaço, mas a performance melhora um bocado.

Anúncios