Arranjos

Um arranjo (array) permite o armazenamento de um número arbitrário de elementos homogêneos (de mesmo tipo), organizados em endereços de memória contíguos e associados a um mesmo identificador. Os elementos individuais podem ser acessados a partir de um índice, e sua posição na memória calculada com uma fórmula matemática.

Nos computadores atuais (2016), a memória e muitos dispositivos de armazenamento externo, são organizados como um array unidimensional, o que permite a um programa que utilize um array explorar esta lógica de endereçamento.

O acesso a elementos de um array pode ser eficientemente calculado em tempo de execução, quando os elementos armazenados ocupam a mesma quantidade de memória. Por exemplo, um array de inteiros de 32-bits (4 bytes), armazenado a partir da posição 8000, teria seu primeiro elemento na posição 8000, o segundo na posição 8004, o terceiro na posição 8008, o quarto na posição 8012, e assim por diante.

Para arrays unidimensionais, sabendo-se o endereço de memória inicial ou base (B), o espaço em memória necessário para armazenar um elementos (T) e o índice do elemento que se deseja acessar (i), a posição de memória do elemento a ser acessado (E) pode ser obtido através da Equação 1.

E = B + i × T

As principais vantagens na utilização de arrays são o tempo de acesso com custo constante (independente do tamanho do array) para acesso randômico, e a característica de não desperdiçar espaço extra para o armazenamento dos elementos. As principais desvantagens na utilização de arrays surgem nas operações de inserção e remoção de elementos.

Arranjos Dinâmicos

Em algumas linguagens de programação, os arrays estão disponíveis em forma de arrays estáticos, cujo tamanho pode ser definido no momento da criação do array, porém o número de elementos não pode variar ao longo do tempo. Nestes casos, o array permite acesso rápido aos elementos, porém não permite a implementação dos conceitos de inserção e remoção de elementos.

Os arrays dinâmicos (também conhecidos como vetores, arrays mutáveis, ou array list), são estruturas semelhantes aos arrays, com a mesma forma de organização em memória, mas que permitem a inserção e a remoção de elementos, aumentando e diminuindo o tamanho da estrutura de dados quando necessário.

Um array dinâmico não é a mesma coisa que um array alocado dinamicamente, embora esta estrutura seja comumente utilizada para implementar a base de armazenamento de dados de um array dinâmico.

As vantagens de utilizar um array dinâmico no lugar de um array estático aparecem quando a aplicação apresenta

  • um número de elementos a ser inserido desconhecido e/ou complexo de ser calculado;
  • o número de elementos a ser inserido pode ser alterado, mesmo que em algum momento, seja conhecido;
  • o custo amortizado de aumentar o tamanho do array não impacta na eficiência ou responsividade da aplicação.

A acesso aos elementos de um array dinâmico é exatamente igual ao acesso a elementos em um array estático, no entanto, o array dinâmico adiciona a capacidade de inserção e remoção de elementos, e estas operações apresentam um custo de execução que deve ser levado em consideração.

Ao inserir um elemento no array, todos os elementos existentes após o ponto de inserção devem ser movidos uma posição para frente, de forma que o elemento inserido não sobrescreva um elemento já existente, por esse motivo, o custo de inserção no array dinâmico, no pior caso, tem um custo de N operações ("mover um elemento") para a inserção, onde N é, potencialmente, o número de elementos já inseridos no array (imagine que o novo elemento está sendo inserido na primeira posição do array). Por isso, diz-se que a operação de inserção em um array dinâmico tem custo O(N) (em notação Big-O).

A inserção no final do array dinâmico, por sua vez, não envolverá a movimentação de nenhum elemento, tendo assim, um custo constante, independente do número de elementos no array.

Na inserção, mesmo no final do array, pode ocorrer de não haver mais espaço disponível para armazenamento, sendo necessário que a capacidade de armazenamento do array seja aumentada. Esta operação de aumento da capacidade do array tem custo diretamente proporcional ao tamanho do array, uma vez que é necessário criar uma nova área de armazenamento, e copiar todos os elementos da área de armazenamento original para a nova. Este processo de aumento de tamanho, claramente tem um custo de execução da ordem de O(N) operações, no entanto, se a cada vez que o array precisar ter seu tamanho aumentado, este aumento for realizado por uma grande quantidade, por exemplo dobrando o tamanho do array, o número de operações de aumento do array será pequeno em relação ao número de elementos armazenados no array, fazendo com que o custo geral seja constante amortizado.

Baseado na análise do custo amortizado, diz-se que a inserção de elementos ao final do array dinâmico, tem custo constante, O(1).

Assim como no caso da inserção de elementos, a exclusão de elementos de um array dinâmico também exige a movimentação dos elementos (neste caso, do final em direção ao elemento removido), e por esse motivo, a remoção dos elementos possui custo O(N). No entanto, a remoção do último elemento necessita apenas de uma operação, e possui custo O(1).

Para garantir a eficiência na utilização do array dinâmico, o seu tamanho não deve ser continuamente diminuído, sob pena de que seja necessário aumentá-lo novamente devido a novas inserções, por esse motivo, o array só deve ter seu tamanho reduzido quando ficar com um número muito pequeno de elementos em relação a sua capacidade, por exemplo, 30% de ocupação.

Muitas vezes se utiliza 25% de ocupação pois a divisão por 4 pode ser executada com N >> 2, que é uma operação muito mais rápida que a divisão.

Implementação de um arranjo dinâmico

Na implementação de um arranjo dinâmico, é necessário que se mantenha uma área para armazenamento dos valores (data) e um controle do número de elementos já inseridos na estrutura (count). A capacidade de armazenamento também deve ser controlada, no entanto em diversas linguagens (principalmente nas orientadas à objetos) esta informação pode ser obtida a partir da área de armazenamento.

Os algoritmos aqui apresentados levam em consideração que o primeiro índice para acesso aos elementos é Zero (0). Para sistemas onde o primeiro índice é Um (1), devem ser realizadas as devidas alterações.

Inserção no final do arranjo

A inserção ao final do arranjo dinâmico (Algoritmo 1) tem custo computacional constante amortizado (O(1)), quando o aumento do arranjo permite que o custo de aumentar a área de armazenamento seja bem dividido ao longo do tempo de uso da estrutura.

Inserção no final do arranjo

append ( value ):
    ensureEnoughSpace ()
    data[count] = value
    count = count + 1

Inserção em uma posição específica

Para inserir um novo elemento em uma posição específica do arranjo (Algoritmo 2), é necessário validar a posição na qual o elemento será inserido, e mover os elementos para uma posição imediatamente posterior à que estão (Algoritmo 3), de forma a garantir que a posição a ser preenchida esteja disponível. Devido a essa movimentação dos elementos já existentes no arranjo, o custo da inserção em uma posição arbitrária do arranjo é O(N), pois são executadas, no máximo, N operações para mover os elementos.

Inserção em uma posição específica

insert ( index, value ):
    if ( isIndexValid ( index ) )
        ensureEnoughSpace ()
        moveElementsForward ( index )
        data[index] = value
        count = count + 1
    else
        Error 'Invalid index: ', index

Move, para frente, os elementos

moveElementsForward ( index )
    if ( isIndexValid ( index ) )
        for (i = count, i > index, i = i - 1)
            data[i] = data[i - 1]

Remoção de elementos

De forma similar à inclusão de novos elementos, a remoção de um elemento arbitrário do arranjo (Algoritmo (4) requer de todos os elementos posteriores a ele sejam movidos para uma posição anterior àquela em que se encontram (Algoritmo 5), de forma a não gerar "espaços" nos dados. Como essa movimentação pode ser necessária para os N elementos restantes no arranjo, o custo para essa operação é da ordem O(N), ou seja, cresce linearmente com relação ao número de elementos armazenados. A remoção do último elemento do arranjo não requer a movimentação de nenhum elemento, e com isso possui custo constante (O(1)).

Remoção de um elemento em uma posição específica

remove ( index ):
    if ( isIndexValid ( index ) )
        moveElementsBackward( index )
        count = count - 1
    else
        Error 'Invalid index: ', index

Move, para trás, os elementos

moveElementsBackward ( index )
    if ( isIndexValid ( index ) )
        for (i = index + 1, i < count, i = i + 1)
            data[i - 1] = data[i]

Accesso a dados

Os arranjos dinâmicos utilizam uma estrutura de armazenamento de dados que utiliza uma área contínua de memória, que associado ao fato destas estruturas serem utilizadas para o armazenamento de dados homogêneos, permite que o acesso randômico seja realizado de forma bastante eficiente, com custo constante independente do número de elementos armazenados (isso, não levando em consideração linhas de cache). Além disso, uma vez que o número de elementos é controlado pela estrutura, o controle ao acesso de posições inválidas é facilitado (Algoritmo 6).

Consulta um elemento em uma posição específica

get ( index ) -> Dado:
    if ( isIndexValid ( index ) )
        return data[index]
    else
        Error 'Invalid index: ', index

Funções de suporte

Verificação do número de elementos

Duas funções podem ser definidas para se verificar o número de elementos de um arranjo dinâmico. Uma função que retorna o número de elementos existentes no arranjo (Algoritmo 7), e uma função que testa se existe algum elemento no arranjo (Algoritmo 8).

Consulta o número de elementos no arranjo.

count ( ) -> Integer:
    return count

Verifica se existem elementos no arranjo.

empty ( ) -> Boolean:
    return count == 0

Validação de índices

Em diversas situações é necessário validar se um número utilizado para acessar uma posição específica do arranjo é um índice válido para permitir esse acesso. Um índice válido em um arranjo é um número inteiro, positivo, e que não seja maior que o número de elementos já inseridos na estrutura (Algoritmo 9).

Teste para validar um índice para acesso a um elemento

isIndexValid ( index ) -> Boolean:
    return ( index >= 0  ) && ( index < count )

Incremento de espaço no arranjo

Quando um elemento deve ser inserido no arranjo, é necessário garantir que exista espaço suficiente para armazenar este elemento. Para melhorar a eficiência do ajuste de tamanho, e permitir que as operações realizadas no último elemento do arranjo (inclusão e remoção) tenham, ao menos, custo constante amortizado, o tamanho da área de armazenamento deve ser incrementado com "uma quantidade suficiente de elementos". Esta quantidade varia para cada implementação, sendo muito comuns os casos onde o tamanho desta área é dobrado (100% de aumento) (Algoritmo 10), ou é aumentado em 50%.

Garante que existe espaço suficiente para armazenamento

ensureEnoughSpace ():
    if ( count == data.length )
        storage = createStorage( data.length * 2 )
        for ( i = 0, i < count, i = i + 1)
            storage[i] = data[i]
        data = storage

Por simplicidade, o tamanho da área de armazenamento está sendo dobrada quando necessário, no entanto, outros fatores de aumento de tamanho (como 1.5 - que pode ser implementado como (N * 3) >> 1), podem ser mais eficientes com relação à utilização da memória, diminuindo possíveis desperdícios.