Matriz dinâmica - Dynamic array

Vários valores são inseridos no final de uma matriz dinâmica usando expansão geométrica. Células cinza indicam espaço reservado para expansão. A maioria das inserções é rápida (tempo constante), enquanto algumas são lentas devido à necessidade de realocação (tempo Θ ( n ), rotulado com tartarugas). O tamanho lógico e a capacidade da matriz final são mostrados.

Em informática , uma matriz dinâmica , matriz growable , matriz redimensionável , tabela dinâmica , matriz mutável , ou lista de matriz é um acesso aleatório , a lista de variáveis de tamanho estrutura de dados que permite que os elementos a ser adicionados ou removidos. É fornecido com bibliotecas padrão em muitas linguagens de programação convencionais modernas. Os arrays dinâmicos superam um limite de arrays estáticos , que têm uma capacidade fixa que precisa ser especificada na alocação.

Um array dinâmico não é a mesma coisa que um array alocado dinamicamente , que é um array cujo tamanho é fixo quando o array é alocado, embora um array dinâmico possa usar esse array de tamanho fixo como back end.

Matrizes dinâmicas de tamanho limitado e capacidade

Um array dinâmico simples pode ser construído alocando um array de tamanho fixo, normalmente maior do que o número de elementos imediatamente necessários. Os elementos da matriz dinâmica são armazenados de forma contígua no início da matriz subjacente e as posições restantes no final da matriz subjacente são reservadas ou não utilizadas. Elementos podem ser adicionados ao final de um array dinâmico em tempo constante usando o espaço reservado, até que este espaço seja totalmente consumido. Quando todo o espaço é consumido e um elemento adicional deve ser adicionado, a matriz de tamanho fixo subjacente precisa ser aumentada em tamanho. Normalmente, o redimensionamento é caro porque envolve a alocação de uma nova matriz subjacente e a cópia de cada elemento da matriz original. Os elementos podem ser removidos do final de uma matriz dinâmica em tempo constante, pois nenhum redimensionamento é necessário. O número de elementos usados ​​pelo conteúdo do array dinâmico é seu tamanho lógico ou tamanho , enquanto o tamanho do array subjacente é chamado de capacidade ou tamanho físico do array dinâmico , que é o tamanho máximo possível sem realocar dados.

Um array de tamanho fixo será suficiente em aplicações onde o tamanho lógico máximo é fixo (por exemplo, por especificação) ou pode ser calculado antes que o array seja alocado. Uma matriz dinâmica pode ser preferida se:

  • o tamanho lógico máximo é desconhecido, ou difícil de calcular, antes que a matriz seja alocada
  • considera-se que um tamanho lógico máximo dado por uma especificação tende a mudar
  • o custo amortizado de redimensionar uma matriz dinâmica não afeta significativamente o desempenho ou capacidade de resposta

Expansão geométrica e custo amortizado

Para evitar incorrer no custo de redimensionar muitas vezes, os arrays dinâmicos são redimensionados em uma grande quantidade, como dobrar de tamanho, e usam o espaço reservado para expansão futura. A operação de adicionar um elemento ao final pode funcionar da seguinte maneira:

function insertEnd(dynarray a, element e)
    if (a.size == a.capacity)
        // resize a to twice its current capacity:
        a.capacity  a.capacity * 2 
        // (copy the contents to the new memory location here)
    a[a.size]  e
    a.size  a.size + 1

À medida que n elementos são inseridos, as capacidades formam uma progressão geométrica . Expandir a matriz em qualquer proporção constante a garante que a inserção de n elementos leve O ( n ) tempo total, o que significa que cada inserção leva um tempo constante amortizado . Muitos arrays dinâmicos também desalocam parte do armazenamento subjacente se seu tamanho cair abaixo de um certo limite, como 30% da capacidade. Este limite deve ser estritamente menor que 1 / a , a fim de fornecer histerese (fornecer uma banda estável para evitar crescimento e encolhimento repetidamente) e suportar sequências mistas de inserções e remoções com custo constante amortizado.

Matrizes dinâmicas são um exemplo comum ao ensinar análise amortizada .

Fator de crescimento

O fator de crescimento para a matriz dinâmica depende de vários fatores, incluindo uma compensação de espaço-tempo e algoritmos usados ​​no próprio alocador de memória. Para o fator de crescimento a , o tempo médio por operação de inserção é cerca de a / ( a −1), enquanto o número de células perdidas é limitado acima por ( a −1) n . Se o alocador de memória usar um algoritmo de alocação de primeiro ajuste , os valores do fator de crescimento, como a = 2, podem fazer com que a expansão dinâmica da matriz fique sem memória, embora uma quantidade significativa de memória ainda possa estar disponível. Tem havido várias discussões sobre os valores do fator de crescimento ideal, incluindo propostas para o índice de ouro , bem como o valor 1,5. Muitos livros didáticos, no entanto, usam a  = 2 para fins de simplicidade e análise.

Abaixo estão os fatores de crescimento usados ​​por várias implementações populares:

Implementação Fator de crescimento ( a )
Java ArrayList 1,5 (3/2)
Python PyListObject ~ 1,125 (n + n >> 3)
Microsoft Visual C ++ 2013 1,5 (3/2)
G ++ 5.2.0 2
Clang 3.6 2
Loucura do Facebook / FBVector 1,5 (3/2)
Rust Vec 2
Fatias Go entre 1,25 e 2

atuação

Comparação de estruturas de dados de lista
Olhadinha Transformar (inserir ou excluir) em ... Excesso de espaço,
média
Começo Fim Meio
Lista ligada Θ ( n ) Θ (1) Θ (1), elemento final conhecido;
Θ ( n ), elemento final desconhecido
Hora de
espiar + Θ (1)
Θ ( n )
Variedade Θ (1) N / D N / D N / D 0
Array dinâmico Θ (1) Θ ( n ) Θ (1) amortizado Θ ( n ) Θ ( n )
Árvore balanceada Θ (log n) Θ (log n) Θ (log n ) Θ (log n ) Θ ( n )
Lista de acesso aleatório Θ (log n) Θ (1) N / D N / D Θ ( n )
Árvore de matriz com hash Θ (1) Θ ( n ) Θ (1) amortizado Θ ( n ) Θ (√ n )

A matriz dinâmica tem desempenho semelhante a uma matriz, com a adição de novas operações para adicionar e remover elementos:

  • Obter ou definir o valor em um índice específico (tempo constante)
  • Iterando sobre os elementos em ordem (tempo linear, bom desempenho do cache)
  • Inserindo ou excluindo um elemento no meio da matriz (tempo linear)
  • Inserir ou excluir um elemento no final da matriz (tempo amortizado constante)

Os arrays dinâmicos se beneficiam de muitas das vantagens dos arrays, incluindo boa localidade de referência e utilização do cache de dados , compactação (baixo uso de memória) e acesso aleatório . Eles geralmente têm apenas uma pequena sobrecarga fixa adicional para armazenar informações sobre o tamanho e a capacidade. Isso torna os arrays dinâmicos uma ferramenta atraente para a construção de estruturas de dados amigáveis ​​ao cache . No entanto, em linguagens como Python ou Java, que impõem a semântica de referência, o array dinâmico geralmente não armazena os dados reais, mas sim as referências aos dados que residem em outras áreas da memória. Nesse caso, acessar itens na matriz sequencialmente envolverá, na verdade, o acesso a várias áreas não contíguas da memória, de modo que as muitas vantagens da facilidade de uso do cache dessa estrutura de dados são perdidas.

Em comparação com as listas vinculadas , os arrays dinâmicos têm indexação mais rápida (tempo constante versus tempo linear) e iteração normalmente mais rápida devido à localização aprimorada de referência; no entanto, as matrizes dinâmicas requerem tempo linear para inserir ou excluir em um local arbitrário, uma vez que todos os elementos a seguir devem ser movidos, enquanto as listas vinculadas podem fazer isso em um tempo constante. Esta desvantagem é atenuada pelo buffer de lacuna e variantes de vetor em camadas discutidas em Variantes abaixo. Além disso, em uma região de memória altamente fragmentada , pode ser caro ou impossível encontrar espaço contíguo para uma grande matriz dinâmica, enquanto as listas vinculadas não exigem que toda a estrutura de dados seja armazenada de forma contígua.

Uma árvore balanceada pode armazenar uma lista ao fornecer todas as operações de matrizes dinâmicas e listas vinculadas de forma razoavelmente eficiente, mas tanto a inserção no final quanto a iteração sobre a lista são mais lentas do que para uma matriz dinâmica, em teoria e na prática, devido ao não armazenamento contíguo e sobrecarga de travessia / manipulação de árvore.

Variantes

Os buffers de lacuna são semelhantes aos arrays dinâmicos, mas permitem operações eficientes de inserção e exclusão agrupadas perto do mesmo local arbitrário. Algumas implementações de deque usam deques de matriz , que permitem a inserção / remoção de tempo constante amortizado em ambas as extremidades, em vez de apenas uma extremidade.

Goodrich apresentou um algoritmo de array dinâmico chamado de vetores em camadas que fornece desempenho O ( n 1 / k ) para inserções e exclusões de qualquer lugar no array, e O ( k ) get e set, onde k ≥ 2 é um parâmetro constante.

A árvore de matriz de hash (HAT) é um algoritmo de matriz dinâmica publicado por Sitarski em 1996. A árvore de matriz de hash desperdiça a ordem de n 1/2 da quantidade de espaço de armazenamento, onde n é o número de elementos na matriz. O algoritmo tem desempenho amortizado O (1) ao anexar uma série de objetos ao final de uma árvore de array em hash.

Em um artigo de 1999, Brodnik et al. descrevem uma estrutura de dados de matriz dinâmica em camadas, que desperdiça apenas n 1/2 espaço para n elementos em qualquer ponto no tempo, e provam um limite inferior mostrando que qualquer matriz dinâmica deve desperdiçar tanto espaço se as operações permanecerem tempo constante amortizado . Além disso, eles apresentam uma variante em que aumentar e diminuir o buffer não apenas amortizou, mas também o tempo constante do pior caso.

Bagwell (2002) apresentou o algoritmo VList, que pode ser adaptado para implementar um array dinâmico.

Suporte de linguas

C ++ 's std::vectore de ferrugem s' std::vec::Vecsão implementações de matrizes dinâmicas, como são as ArrayListclasses fornecidas com o Java API e o Framework .

A List<>classe genérica fornecida com a versão 2.0 do .NET Framework também é implementada com matrizes dinâmicas. Smalltalk 's OrderedCollectioné uma matriz dinâmica com índice dinâmico de início e fim, tornando a remoção do primeiro elemento também O (1).

A listimplementação do tipo de dados do Python é um array dinâmico.

Delphi e D implementam arrays dinâmicos no núcleo da linguagem.

O Ada.Containers.Vectorspacote genérico de Ada fornece implementação de array dinâmico para um determinado subtipo.

Muitas linguagens de script, como Perl e Ruby, oferecem arrays dinâmicos como um tipo de dados primitivo integrado .

Várias estruturas de várias plataformas fornecer implementações matriz dinâmica de C , incluindo CFArraye CFMutableArrayno núcleo Foundation , e GArraye GPtrArrayem Glib .

Common Lisp fornece um suporte rudimentar para vetores redimensionáveis, permitindo configurar o arraytipo embutido como ajustável e o local de inserção pelo ponteiro de preenchimento .

Referências

  1. ^ a b Veja, por exemplo, o código-fonte da classe java.util.ArrayList do OpenJDK 6 .
  2. ^ Lambert, Kenneth Alfred (2009), "Physical size and logical size" , Fundamentals of Python: From First Programs Through Data Structures , Cengage Learning, p. 510, ISBN 978-1423902188
  3. ^ a b Goodrich, Michael T .; Tamassia, Roberto (2002), "1.5.2 Analyzing an Extendable Array Implementation", Algorithm Design: Foundations, Analysis and Internet Examples , Wiley, pp. 39-41.
  4. ^ a b Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L .; Stein, Clifford (2001) [1990]. "17.4 Tabelas dinâmicas". Introdução aos Algoritmos (2ª ed.). MIT Press e McGraw-Hill. pp. 416-424. ISBN 0-262-03293-7.
  5. ^ a b c "Vetor C ++ STL: definição, fator de crescimento, funções membro" . Arquivado do original em 06/08/2015 . Página visitada em 05-08-2015 .
  6. ^ "fator de crescimento do vetor de 1,5" . comp.lang.c ++. moderado . Grupos do Google.
  7. ^ Liste a implementação do objeto de github.com/python/cpython/, recuperado em 2020-03-23.
  8. ^ Brais, Hadi. "Dissecando o vetor C ++ STL: Parte 3 - Capacidade e tamanho" . Micromistérios . Página visitada em 05-08-2015 .
  9. ^ "facebook / loucura" . GitHub . Página visitada em 05-08-2015 .
  10. ^ "rust-lang / rust" . GitHub . Obtido em 2020-06-09 .
  11. ^ "golang / go" . GitHub . Obtido em 2021-09-14 .
  12. ^ Dia 1 Keynote - Bjarne Stroustrup: C ++ 11 Style no GoingNative 2012 em channel9.msdn.com a partir do minuto 45 ou foil 44
  13. ^ Processamento de números: por que você nunca, jamais, NUNCA deve usar a lista vinculada em seu código novamente em kjellkod.wordpress.com
  14. ^ Brodnik, Andrej; Carlsson, Svante; Sedgewick, Robert ; Munro, JI; Demaine, ED (1999), Resizable Arrays in Optimal Time and Space (Technical Report CS-99-09) (PDF) , Departamento de Ciência da Computação, University of Waterloo
  15. ^ a b c Chris Okasaki (1995). "Listas de acesso aleatório puramente funcionais". Anais da Sétima Conferência Internacional sobre Linguagens de Programação Funcional e Arquitetura de Computadores : 86–95. doi : 10.1145 / 224164.224187 .
  16. ^ Goodrich, Michael T .; Kloss II, John G. (1999), "Tiered Vectors: Efficient Dynamic Arrays for Rank-Based Sequences" , Workshop on Algorithms and Data Structures , Lecture Notes in Computer Science, 1663 : 205-216 , doi : 10.1007 / 3-540 -48447-7_21 , ISBN 978-3-540-66279-2
  17. ^ Sitarski, Edward (setembro de 1996), "HATs: Hashed array trees" , Algorithm Alley, Dr. Dobb's Journal , 21 (11)
  18. ^ Brodnik, Andrej; Carlsson, Svante; Sedgewick, Robert ; Munro, JI; Demaine, ED (1999), Resizable Arrays in Optimal Time and Space (PDF) (Technical Report CS-99-09), Departamento de Ciência da Computação, University of Waterloo
  19. ^ Bagwell, Phil (2002), Fast Functional Lists, Hash-Lists, Deques and Variable Length Arrays , EPFL
  20. ^ Javadoc ligadoArrayList
  21. ^ Classe ArrayList

links externos