Por que a matriz de vetor dobrou?

Question

Por que a implementação clássica do vetor (ArrayList para pessoas Java) dobrar de tamanho interno variedade em cada expansão em vez de triplicar ou quadruplicar-lo?

Answer 1

Ao calcular o tempo médio para inserir em um vetor, você precisa permitir que as inserções não-crescimento e as inserções em crescimento.

Chamar o número total de operações para inserir n itens o _{total de} , e a média o _média .

Se você inserir n itens, e você crescer por um fator de A , conforme necessário, em seguida, há o _Total = n + SA ⁱ [0 A n] operações. Na pior das hipóteses você usar 1 / A do armazenamento alocado.

Intuitivamente, A = 2 meios na pior das hipóteses você tem o _Total = 2n , então o _média é o (1), e o pior caso de você usar 50% do armazenamento alocado.

Para uma maior A , você tem um o _{total menor} , mas o armazenamento mais desperdício.

Para uma menor A , o _Total é maior, mas você não perder tanto armazenamento. Enquanto ela cresce geometricamente, ainda é O (1) amortizado inserção tempo, mas a constante vai ficar maior.

para factores de crescimento 1,25 (vermelho), 1,5 (ciano), 2 (preto), 3 (azul) e 4 (verde), estes gráficos mostram ponto e a eficiência de tamanho médio (proporção de tamanho / espaço alocado; quanto mais, melhor ) à esquerda e eficiência de tempo (proporção de inserções / operações; quanto mais, melhor) à direita para a inserção de 400.000 itens. 100% de eficiência de espaço é alcançado para todos os factores de crescimento anteriores apenas para redimensionar; o caso de A = 2 mostra a eficiência de tempo entre 25% e 50%, e a eficiência do espaço de cerca de 50%, o que é bom para a maioria dos casos:

Para tempos de execução, tais como Java, arrays são de zero preenchido, de modo que o número de operações para alocar é proporcional ao tamanho da matriz. Tendo em conta esta dá reduz a diferença entre as estimativas de eficiência de tempo:

Answer 2

exponencialmente dobrando o tamanho da matriz (ou string) é um bom compromisso entre ter número suficiente de células na matriz e desperdiçando muita memória.

Say começamos com 10 elementos:

1 - 10
2-20
3-40
4-80
5-160

Quando o triplo do tamanho, nós crescemos muito rápido

1 - 10
2-30
3-90
4 - 270
5-810

Na prática, você iria crescer talvez 10 ou 12 vezes. Se você triplicar você talvez fazê-lo 7 ou 8 vezes -. A batida de tempo de execução de reafectação é isso algumas vezes é suficientemente pequeno para se preocupar, mas você é mais provável que completamente superação o tamanho necessário

Answer 3

Se você fosse para alocar um bloco incomum de tamanho de memória, em seguida, quando esse bloco fica desalocadas (ou porque você está redimensionando-lo ou ele fica GC'd) haveria um buraco incomum de tamanho na memória que poderia causar dores de cabeça para o gerenciador de memória. Portanto, é geralmente preferido para alocar memória em potências de dois. Em alguns casos, o gerenciador de memória subjacente só vai te dar blocos de determinados tamanhos, e se você pedir um tamanho estranho ele irá arredondar para o tamanho maior seguinte. Então, ao invés de pedir para 470 unidades, ficando para trás 512 de qualquer maneira, e depois redimensionamento mais uma vez você já usou todos os 470 que você pediu, pode muito bem pedir 512 para começar.

Answer 4

Qualquer múltiplo é um compromisso. Torná-lo muito grande e você desperdiça muita memória. Torná-lo muito pequeno e você perder muito tempo para realocações e cópia. Eu acho que a duplicação está lá porque ele funciona e é muito fácil de implementar. Eu também vi um STL-como biblioteca proprietária que usa 1.5 como multiplicador para o mesmo -. Eu acho que seus desenvolvedores considerado dobrando desperdiçando muita memória

Answer 5

Se você está perguntando sobre a implementação específica do Java de Vector e ArrayList , então não é necessariamente dobrou em cada expansão.

A partir do Javadoc para Vector:

Cada vector tenta optimizar a gestão de armazenamento através da manutenção de um capacity e um capacityIncrement. A capacidade é de sempre, pelo menos, tão grande como o tamanho do vector; é geralmente maior, porque como os componentes são adicionados ao vector, aumenta o armazenamento do vector em pedaços do tamanho de capacityIncrement. Uma aplicação pode aumentar a capacidade de um vector antes de introduzir um grande número de componentes; isto reduz a quantidade de reatribuição incremental.

Um dos construtores para Vector permite que você especifique o tamanho ea capacidade de incremento inicial para a Vector. A classe Vector também oferece a ensureCapacity(int minCapacity) e setSize(int newSize), de ajustes manuais do tamanho mínimo do vetor e para redimensionar o vetor em seu próprio país.

A classe ArrayList é muito semelhante:

Cada instância ArrayList tem uma capacidade. A capacidade é o tamanho da matriz usado para armazenar os elementos da lista. É sempre pelo menos tão grande quanto o tamanho da lista. Como os elementos são adicionados a um ArrayList, a sua capacidade cresce automaticamente. Os detalhes da política de crescimento não são especificados além do fato de que a adição de um elemento tem custo de tempo amortizado constante.

Uma aplicação pode aumentar a capacidade de uma instância ArrayList antes da adição de um grande número de elementos usando a operação EnsureCapacity. Isso pode reduzir a quantidade de realocação incremental.

Se você está perguntando sobre a aplicação geral de um vetor, que a escolha do aumento no tamanho e por quanto é um trade-off. Geralmente, os vectores são apoiados por matrizes. As matrizes são de um tamanho fixo. Para redimensionar um vetor porque é cheia significa que você tem que copiar todos os elementos de uma matriz em uma nova matriz, maior. Se você fizer sua nova matriz muito grande, então você alocou memória que você nunca vai usar. Se for muito pequeno, ele pode levar muito tempo para copiar os elementos da matriz antiga para a nova matriz, maior -. Uma operação que você não deseja executar muitas vezes

Answer 6

Pessoalmente, eu acho que é uma escolha arbitriary. Nós poderíamos usar base e, em vez de base 2 (em vez de dobrar o tamanho apenas múltipla por (1 + e).)

Se você estiver indo para estar adicionando grandes quantidades de variáveis ??para o vetor, então, seria vantajoso ter uma base elevada (para reduzir o amnt de copiar você vai fazer.) Por outro lado, se você precisa estar armazenando apenas alguns membros sobre avg, em seguida, uma base baixa vai ficar bem e reduzir a quantidade de sobrecarga, portanto, acelerando as coisas.

Base 2 é uma solução de compromisso.

Answer 7

Não há nenhuma razão de desempenho para a duplicação vs triplicando ou quadruplicando como todos têm as mesmas grandes perfis de desempenho S. No entanto, em termos absolutos dobrando tenderá a ser mais eficiente do espaço no cenário normal.