Por que iniciar um ArrayList com capacidade inicial?

149

O construtor usual de ArrayListé:

ArrayList<?> list = new ArrayList<>();

Mas há também um construtor sobrecarregado com um parâmetro para sua capacidade inicial:

ArrayList<?> list = new ArrayList<>(20);

Por que é útil criar um ArrayListcom uma capacidade inicial quando podemos anexá-lo como quisermos?

Roubar
fonte
17
Você tentou ver o código-fonte ArrayList?
AmitG
@Joachim Sauer: Às vezes, temos conhecimento quando lemos a fonte com atenção. Eu estava tentando se ele leu a fonte. Eu entendi o seu aspecto. Obrigado.
AmitG
ArrayList é um período ruim, por que você gostaria de usar essa estrutura?
PositiveGuy

Respostas:

196

Se você sabe com antecedência qual será o tamanho da ArrayListsolução, é mais eficiente especificar a capacidade inicial. Se você não fizer isso, a matriz interna precisará ser realocada repetidamente à medida que a lista aumentar.

Quanto maior a lista final, mais tempo você economiza, evitando as realocações.

Dito isto, mesmo sem pré-alocação, é garantido que a inserção de nelementos na parte de trás de um tempo ArrayListtotal O(n). Em outras palavras, anexar um elemento é uma operação de tempo constante amortizada. Isso é obtido fazendo com que cada realocação aumente exponencialmente o tamanho da matriz, geralmente por um fator de 1.5. Com essa abordagem, o número total de operações pode ser demonstradoO(n) .

NPE
fonte
5
Embora pré-alocar tamanhos conhecidos seja uma boa idéia, geralmente não é terrível: você precisará de realocações de log (n) para uma lista com um tamanho final de n , o que não é muito.
Joachim Sauer
2
@PeterOlson O(n log n)estaria fazendo horários de log ntrabalho n. Isso é uma superestimação bruta (embora tecnicamente correta com O grande devido ao fato de ser um limite superior). Copia s + s * 1,5 + s * 1,5 ^ 2 + ... + s * 1,5 ^ m (de modo que s * 1,5 ^ m <n <s * 1,5 ^ (m + 1)) elementos no total. Eu não sou bom em somas, então não posso lhe dar a matemática exata em cima da minha cabeça (para redimensionar o fator 2, é 2n, então pode ser 1,5n, dar ou receber uma pequena constante), mas não é preciso olhar muito para ver que essa soma é no máximo um fator constante maior que n. Portanto, são necessárias O (k * n) cópias, o que é obviamente O (n).
1
@ delnan: Não posso discutir com isso! ;) Aliás, gostei muito do seu argumento de estrabismo; vou adicioná-lo ao meu repertório de truques.
NPE
6
É mais fácil argumentar com duplicação. Suponha que você dobre quando estiver cheio, começando com um elemento. Suponha que você queira inserir 8 elementos. Insira um (custo: 1). Insira dois - duplo, copie um elemento e insira dois (custo: 2). Inserir três - duplo, copie dois elementos, insira três (custo: 3). Insira quatro (custo: 1). Inserir cinco - duplo, copie quatro elementos, insira cinco (custo: 5). Insira seis, sete e oito (custo: 3). Custo total: 1 + 2 + 3 + 1 + 5 + 3 = 16, que é o dobro do número de elementos inseridos. A partir deste esboço, você pode provar que o custo médio é de dois por inserção em geral.
precisa
9
Esse é o custo no tempo . Você também pode ver que a quantidade de espaço desperdiçado mudou ao longo do tempo, sendo 0% parte do tempo e próximo a 100% algumas vezes. Alterar o fator de 2 para 1,5 ou 4 ou 100 ou o que quer que seja, altera a quantidade média de espaço desperdiçado e a quantidade média de tempo gasto na cópia, mas a complexidade do tempo permanece linear em média, independentemente do fator.
precisa
41

Porque ArrayListé uma estrutura de dados de matriz de redimensionamento dinâmico , o que significa que ela é implementada como uma matriz com um tamanho fixo inicial (padrão). Quando isso for preenchido, a matriz será estendida para uma de tamanho duplo. Como esta operação é cara, você deseja o mínimo possível.

Portanto, se você sabe que seu limite superior é de 20 itens, é melhor criar o array com comprimento inicial de 20 do que usar um padrão de, digamos, 15 e redimensioná-lo 15*2 = 30e usar apenas 20 enquanto desperdiça os ciclos da expansão.

PS - Como o AmitG diz, o fator de expansão é específico da implementação (neste caso (oldCapacity * 3)/2 + 1)

Iulius Curt
fonte
9
é na verdade #int newCapacity = (oldCapacity * 3)/2 + 1;
AmitG 15/03
25

O tamanho padrão da matriz é 10 .

    /**
     * Constructs an empty list with an initial capacity of ten.
     */
    public ArrayList() {
    this(10);
    } 

Portanto, se você quiser adicionar 100 ou mais registros, poderá ver a sobrecarga da realocação de memória.

ArrayList<?> list = new ArrayList<>();    
// same as  new ArrayList<>(10);      

Portanto, se você tem alguma idéia sobre o número de elementos que serão armazenados no Arraylist, é melhor criar o Arraylist com esse tamanho, em vez de começar com 10 e depois aumentá-lo.

xyz
fonte
Não há garantia de que a capacidade padrão será sempre 10 para versões do JDK no futuro -private static final int DEFAULT_CAPACITY = 10
vikingsteve
17

Na verdade, eu escrevi um post sobre o tópico há 2 meses. O artigo é para C #, List<T>mas o Java ArrayListtem uma implementação muito semelhante. Como ArrayListé implementado usando uma matriz dinâmica, aumenta em tamanho sob demanda. Portanto, o motivo do construtor de capacidade é para fins de otimização.

Quando uma dessas operações de redimensionamento ocorre, o ArrayList copia o conteúdo da matriz em uma nova matriz com o dobro da capacidade da antiga. Esta operação é executada em O (n) tempo.

Exemplo

Aqui está um exemplo de como o ArrayListtamanho aumentaria:

10
16
25
38
58
... 17 resizes ...
198578
297868
446803
670205
1005308

Portanto, a lista começa com uma capacidade de 10, quando o 11º item é adicionado, é aumentado em 50% + 1para 16. No 17º item, o valor ArrayListé aumentado novamente para 25e assim por diante. Agora considere o exemplo em que estamos criando uma lista em que a capacidade desejada já é conhecida 1000000. Criar o ArrayListconstrutor sem o tamanho chamará ArrayList.add 1000000tempos que levam O (1) normalmente ou O (n) no redimensionamento.

1000000 + 16 + 25 + ... + 670205 + 1005308 = 4015851 operações

Compare isso usando o construtor e, em seguida, chamando, ArrayList.addque é garantido para executar em O (1) .

1000000 + 1000000 = 2000000 operações

Java vs C #

Java é como acima, iniciando 10e aumentando cada redimensionamento em 50% + 1. O C # inicia 4e aumenta muito mais agressivamente, dobrando a cada redimensionamento. O 1000000exemplo adiciona acima para C # usa 3097084operações.

Referências

Daniel Imms
fonte
9

Definir o tamanho inicial de um ArrayList, por exemplo, para ArrayList<>(100), reduz o número de vezes que a realocação da memória interna deve ocorrer.

Exemplo:

ArrayList example = new ArrayList<Integer>(3);
example.add(1); // size() == 1
example.add(2); // size() == 2, 
example.add(2); // size() == 3, example has been 'filled'
example.add(3); // size() == 4, example has been 'expanded' so that the fourth element can be added. 

Como você pode ver no exemplo acima, um ArrayListpode ser expandido, se necessário. O que isso não mostra é que o tamanho da Lista de matriz geralmente dobra (embora observe que o novo tamanho depende da sua implementação). O seguinte é citado da Oracle :

"Cada instância ArrayList tem capacidade. A capacidade é o tamanho da matriz usada para armazenar os elementos na lista. É sempre pelo menos tão grande quanto o tamanho da lista. À medida que os elementos são adicionados a um ArrayList, sua capacidade aumenta 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 ".

Obviamente, se você não tem idéia do tipo de intervalo que estará mantendo, definir o tamanho provavelmente não será uma boa ideia - no entanto, se você tiver um intervalo específico em mente, definir uma capacidade inicial aumentará a eficiência da memória .

dsgriffin
fonte
3

O ArrayList pode conter muitos valores e, ao fazer inserções iniciais grandes, você pode solicitar ao ArrayList que aloque um armazenamento maior para começar, a fim de não desperdiçar os ciclos da CPU ao tentar alocar mais espaço para o próximo item. Assim, alocar algum espaço no início é mais eficiente.

Sanober Malik
fonte
3

Isso é para evitar possíveis esforços de realocação para cada objeto.

int newCapacity = (oldCapacity * 3)/2 + 1;

internamente new Object[]é criado.
A JVM precisa de esforço para criar new Object[]quando você adiciona elemento na lista de matrizes. Se você não tem o código acima (qualquer algo que você pensa) para realocação, em seguida, cada vez que quando você chamar arraylist.add(), em seguida, new Object[]tem de ser criado que é inútil e estamos perdendo tempo para aumentar o tamanho de 1 para cada objetos a ser adicionado. Portanto, é melhor aumentar o tamanho Object[]com a seguinte fórmula.
(A JSL usou a fórmula de transmissão fornecida abaixo para aumentar dinamicamente o arraylist em vez de aumentar 1 sempre. Porque para crescer, é necessário um esforço da JVM)

int newCapacity = (oldCapacity * 3)/2 + 1;
AmitG
fonte
O ArrayList não executará a realocação de cada single add- ele já usa alguma fórmula de crescimento internamente. Portanto, a pergunta não é respondida.
AH
@AH Minha resposta é para testes negativos . Por favor, leia nas entrelinhas. Eu disse: "Se você não possui o código acima (qualquer coisa que você pensa) para realocação, toda vez que você chama arraylist.add (), então é necessário criar um novo Object [], o que é inútil e estamos perdendo tempo". e o código é int newCapacity = (oldCapacity * 3)/2 + 1;o que está presente na classe ArrayList. Você ainda acha que não tem resposta?
AmitG
1
Ainda acho que isso não foi respondido: na ArrayListrealocação amortizada ocorre em qualquer caso com qualquer valor para a capacidade inicial. E a pergunta é sobre: ​​Por que usar um valor não padrão para a capacidade inicial? Além disso: "ler nas entrelinhas" não é algo desejado em uma resposta técnica. ;-)
AH
@ Ah, estou respondendo como, o que havia acontecido se não tivéssemos um processo de realocação no ArrayList. Então é a resposta. Tente ler o espírito da resposta :-). Sei melhor que, em ArrayList, a realocação amortizada ocorre em qualquer caso com qualquer valor para a capacidade inicial.
AmitG
2

Eu acho que cada ArrayList é criado com um valor de capacidade init de "10". De qualquer maneira, se você criar um ArrayList sem definir capacidade no construtor, ele será criado com um valor padrão.

sk2212
fonte
2

Eu diria que é uma otimização. ArrayList sem capacidade inicial terá ~ 10 linhas vazias e se expandirá quando você estiver adicionando.

Para ter uma lista com exatamente o número de itens que você precisa chamar trimToSize ()

Daniel Magnusson
fonte
0

De acordo com minha experiência com ArrayList, fornecer uma capacidade inicial é uma boa maneira de evitar custos de realocação. Mas tem uma ressalva. Todas as sugestões mencionadas acima dizem que só se deve fornecer capacidade inicial quando se conhece uma estimativa aproximada do número de elementos. Mas quando tentamos fornecer uma capacidade inicial sem nenhuma idéia, a quantidade de memória reservada e não utilizada será um desperdício, pois talvez nunca seja necessária uma vez que a lista seja preenchida com o número necessário de elementos. O que estou dizendo é que podemos ser pragmáticos no início enquanto alocamos capacidade e, em seguida, encontrar uma maneira inteligente de saber a capacidade mínima necessária em tempo de execução. ArrayList fornece um método chamado ensureCapacity(int minCapacity). Mas então, encontramos uma maneira inteligente ...

Tushar Patidar
fonte
0

Testei ArrayList com e sem initialCapacity e obtive um resultado surpreendente.
Quando defino LOOP_NUMBER para 100.000 ou menos, o resultado é que a configuração de initialCapacity é eficiente.

list1Sttop-list1Start = 14
list2Sttop-list2Start = 10


Mas quando defino LOOP_NUMBER como 1.000.000, o resultado muda para:

list1Stop-list1Start = 40
list2Stop-list2Start = 66


Finalmente, eu não conseguia descobrir como isso funciona ?!
Código de amostra:

 public static final int LOOP_NUMBER = 100000;

public static void main(String[] args) {

    long list1Start = System.currentTimeMillis();
    List<Integer> list1 = new ArrayList();
    for (int i = 0; i < LOOP_NUMBER; i++) {
        list1.add(i);
    }
    long list1Stop = System.currentTimeMillis();
    System.out.println("list1Stop-list1Start = " + String.valueOf(list1Stop - list1Start));

    long list2Start = System.currentTimeMillis();
    List<Integer> list2 = new ArrayList(LOOP_NUMBER);
    for (int i = 0; i < LOOP_NUMBER; i++) {
        list2.add(i);
    }
    long list2Stop = System.currentTimeMillis();
    System.out.println("list2Stop-list2Start = " + String.valueOf(list2Stop - list2Start));
}

Eu testei no windows8.1 e jdk1.7.0_80

Hamedz
fonte
1
oi, infelizmente, a tolerância currentTimeMillis é de até cem milissegundos (dependendo), o que significa que o resultado dificilmente é confiável. Eu sugiro usar alguma biblioteca personalizada para fazer o certo.
2145 Bogdan