Array ou List em Java. O que é mais rápido?

Eu tenho que manter milhares de strings na memory para serem acessadas serialmente em Java. Devo armazená-los em uma matriz ou devo usar algum tipo de lista?

Como os arrays mantêm todos os dados em um espaço contíguo de memory (diferentemente das Lists), o uso de um array para armazenar milhares de strings causaria problemas?

Resposta: O consenso comum é que a diferença de desempenho é pequena. Interface de lista fornece mais flexibilidade.

Eu sugiro que você use um profiler para testar o que é mais rápido.

Minha opinião pessoal é que você deve usar listas.

Eu trabalho em uma grande base de código e um grupo anterior de desenvolvedores usou arrays em todos os lugares . Isso tornou o código muito inflexível. Depois de alterar grandes partes dele para Listas, não notamos diferença na velocidade.

A maneira Java é que você deve considerar qual abstração de dados é mais adequada às suas necessidades. Lembre-se de que, em Java, uma Lista é um resumo, não um tipo de dados concreto. Você deve declarar as cadeias como uma lista e, em seguida, inicializá-lo usando a implementação de ArrayList.

List strings = new ArrayList(); 

Essa separação do tipo de dados abstratos e da implementação específica é um dos principais aspectos da programação orientada a objects.

Um ArrayList implementa o List Abstract Data Type usando uma matriz como sua implementação subjacente. A velocidade de access é praticamente idêntica a uma matriz, com as vantagens adicionais de poder adicionar e subtrair elementos a uma lista (embora seja uma operação O (n) com uma ArrayList) e se você decidir alterar a implementação subjacente posteriormente você pode. Por exemplo, se você perceber que precisa de access sincronizado, poderá alterar a implementação para um Vetor sem rewrite todo o seu código.

Na verdade, o ArrayList foi projetado especificamente para replace a construção de matriz de baixo nível na maioria dos contextos. Se o Java estava sendo projetado hoje, é inteiramente possível que os arrays fossem deixados de fora em favor do construtor ArrayList.

Como os arrays mantêm todos os dados em um espaço contíguo de memory (diferentemente das Lists), o uso de um array para armazenar milhares de strings causaria problemas?

Em Java, todas as collections armazenam apenas referências a objects, não os objects em si. Ambos os arrays e ArrayList armazenarão alguns milhares de referências em um array contíguo, então eles são essencialmente idênticos. Você pode considerar que um bloco contíguo de alguns milhares de referências de 32 bits estará sempre disponível em hardware moderno. Isso não garante que você não fique sem memory, é claro, apenas que o bloco contíguo de requisito de memory não é difícil de ser atingido.

Você deve preferir tipos genéricos em matrizes. Como mencionado por outros, os arrays são inflexíveis e não possuem o poder expressivo dos tipos genéricos. (Eles, no entanto, suportam typechecking em tempo de execução, mas isso combina muito com tipos genéricos.)

Mas, como sempre, ao otimizar, você deve sempre seguir estas etapas:

  • Não otimize até que você tenha uma versão agradável, limpa e funcional do seu código. Mudar para tipos genéricos poderia muito bem estar motivado nesta etapa já.
  • Quando você tiver uma versão legal e limpa, decida se ela é rápida o suficiente.
  • Se não for rápido o suficiente, meça seu desempenho . Essa etapa é importante por dois motivos. Se você não medir, não saberá (1) o impacto de qualquer otimização feita e (2) saberá onde otimizar.
  • Otimize a parte mais quente do seu código.
  • Meça novamente. Isto é tão importante quanto medir antes. Se a otimização não melhorar as coisas, reverta-a . Lembre-se, o código sem a otimização era limpo, legal e funcional.

Embora as respostas que propõem o uso do ArrayList façam sentido na maioria dos cenários, a questão real do desempenho relativo não foi realmente respondida.

Existem algumas coisas que você pode fazer com uma matriz:

  • crie isso
  • definir um item
  • obter um item
  • clone / copie

Conclusão geral

Embora as operações get e set sejam um pouco mais lentas em uma ArrayList (respectivamente 1 e 3 nanossegundos por chamada em minha máquina), há muito pouca sobrecarga de uso de uma ArrayList vs. uma matriz para qualquer uso não intensivo. No entanto, existem algumas coisas que você deve ter em mente:

  • resize as operações em uma lista (quando chamar list.add(...) ) é caro e deve-se tentar definir a capacidade inicial em um nível adequado quando possível (observe que o mesmo problema surge quando se usa uma matriz)
  • ao lidar com primitivos, os arrays podem ser significativamente mais rápidos, pois permitirão evitar muitas conversões de boxe / unboxing
  • um aplicativo que somente recebe / define valores em um ArrayList (não muito comum!) pode ver um ganho de desempenho de mais de 25% ao alternar para um array

Resultados detalhados

Aqui estão os resultados que eu medi para essas três operações usando a biblioteca de benchmarking jmh (vezes em nanossegundos) com o JDK 7 em uma máquina desktop padrão x86. Observe que ArrayList nunca são redimensionados nos testes para garantir que os resultados sejam comparáveis. Código de referência disponível aqui .

Criação de Array / ArrayList

Executei 4 testes, executando as seguintes instruções:

  • createArray1: Integer[] array = new Integer[1];
  • createList1: List list = new ArrayList<> (1);
  • createArray10000: Integer[] array = new Integer[10000];
  • createList10000: List list = new ArrayList<> (10000);

Resultados (em nanossegundos por chamada, 95% de confiança):

 apgaArrayVsList.CreateArray1 [10.933, 11.097] apgaArrayVsList.CreateList1 [10.799, 11.046] apgaArrayVsList.CreateArray10000 [394.899, 404.034] apgaArrayVsList.CreateList10000 [396.706, 401.266] 

Conclusão: sem diferença perceptível .

obter operações

Eu corri 2 testes, executando as seguintes declarações:

  • getList: return list.get(0);
  • getArray: return array[0];

Resultados (em nanossegundos por chamada, 95% de confiança):

 apgaArrayVsList.getArray [2.958, 2.984] apgaArrayVsList.getList [3.841, 3.874] 

Conclusão: obter de uma matriz é cerca de 25% mais rápido do que obter de uma ArrayList, embora a diferença seja apenas na ordem de um nanossegundo.

definir operações

Eu corri 2 testes, executando as seguintes declarações:

  • setList: list.set(0, value);
  • setArray: array[0] = value;

Resultados (em nanossegundos por chamada):

 apgaArrayVsList.setArray [4.201, 4.236] apgaArrayVsList.setList [6.783, 6.877] 

Conclusão: definir operações em matrizes é cerca de 40% mais rápido que em listas, mas, quanto a get, cada operação de conjunto leva alguns nanossegundos – assim, para a diferença atingir 1 segundo, seria necessário definir itens na lista / array centenas de milhões de vezes!

clonar / copiar

O construtor de cópias da ArrayList delega para Arrays.copyOf portanto, o desempenho é idêntico à cópia da matriz (copiar uma matriz via clone , Arrays.copyOf ou System.arrayCopy não faz diferença material no desempenho ).

Eu estou supondo que o cartaz original está vindo de um fundo C ++ / STL que está causando alguma confusão. Em C ++ std::list é uma lista duplamente vinculada.

Em Java [java.util.]List é uma interface livre de implementação (class abstrata pura em termos C ++). List pode ser uma lista duplamente vinculada – java.util.LinkedList é fornecido. No entanto, 99 vezes fora de 100 quando você quer fazer uma nova List , você deseja usar java.util.ArrayList vez disso, que é o equivalente aproximado de C ++ std::vector . Existem outras implementações padrão, como aquelas retornadas por java.util.Collections.emptyList() e java.util.Arrays.asList() .

Do ponto de vista do desempenho, há um pequeno sucesso de ter que passar por uma interface e um object extra, no entanto, inlining em tempo de execução significa que isso raramente tem qualquer significado. Lembre-se também que String é tipicamente um object mais array. Então, para cada input, você provavelmente tem dois outros objects. Em C ++ std::vector , embora copiando por valor sem um ponteiro como tal, os arrays de caracteres formarão um object para string (e estes geralmente não serão compartilhados).

Se esse código específico for realmente sensível ao desempenho, você poderá criar um único array char[] (ou até mesmo byte[] ) para todos os caracteres de todas as cadeias e, em seguida, uma matriz de deslocamentos. IIRC, é assim que o javac é implementado.

Bem, em primeiro lugar, vale a pena esclarecer o que você quer dizer com “lista” no sentido clássico de estruturas de dados de composição (ou seja, uma linked list) ou você quer dizer java.util.List? Se você quer dizer um java.util.List, é uma interface. Se você quiser usar uma matriz, basta usar a implementação ArrayList e obterá comportamento e semântica semelhantes a um array. Problema resolvido.

Se você quer dizer uma matriz versus uma lista encadeada, é um argumento ligeiramente diferente para o qual voltamos ao Big O (aqui está uma explicação simples em inglês se esse for um termo não familiar.

Matriz;

  • Acesso Aleatório: O (1);
  • Inserir: O (n);
  • Apagar: O (n).

Lista vinculada:

  • Acesso Aleatório: O (n);
  • Inserir: O (1);
  • Apagar: O (1).

Então você escolhe o que melhor se adapta ao seu tamanho. Se você resize, inserir e excluir muito, talvez uma linked list seja a melhor opção. O mesmo vale para se o access random for raro. Você menciona o access serial. Se você está fazendo principalmente o access serial com muito pouca modificação, provavelmente não importa qual você escolher.

Listas vinculadas têm uma sobrecarga ligeiramente maior, pois, como você diz, você está lidando com blocos de memory potencialmente não-contíguos e (efetivamente) pointers para o próximo elemento. Isso provavelmente não é um fator importante, a menos que você esteja lidando com milhões de inputs.

Eu escrevi um pequeno benchmark para comparar ArrayLists com Arrays. No meu laptop antigo, o tempo para percorrer um arraylist de 5000 elementos, 1.000 vezes, era cerca de 10 milissegundos mais lento do que o código de matriz equivalente.

Então, se você não está fazendo nada além de repetir a lista, e você está fazendo muito, então talvez valha a otimização. Caso contrário, eu usaria a Lista, porque isso facilitará quando você precisar otimizar o código.

nb Eu notei que usando for String s: stringsList foi cerca de 50% mais lento do que usar um for-loop de estilo antigo para acessar a lista. Vai a figura … Aqui estão as duas funções que eu cronometrei; o array e a lista foram preenchidos com 5000 strings aleatórias (diferentes).

 private static void readArray(String[] strings) { long totalchars = 0; for (int j = 0; j < ITERATIONS; j++) { totalchars = 0; for (int i = 0; i < strings.length; i++) { totalchars += strings[i].length(); } } } private static void readArrayList(List stringsList) { long totalchars = 0; for (int j = 0; j < ITERATIONS; j++) { totalchars = 0; for (int i = 0; i < stringsList.size(); i++) { totalchars += stringsList.get(i).length(); } } } 

Concordo que, na maioria dos casos, você deve escolher a flexibilidade e a elegância de ArrayLists em matrizes – e, na maioria dos casos, o impacto no desempenho do programa será insignificante.

No entanto, se você estiver fazendo uma iteração constante e pesada com pouca alteração estrutural (sem adicionar e remover) para, digamos, renderização de software ou uma máquina virtual personalizada, meus testes de comparativos de access sequencial mostram que ArrayLists são 1.5x mais lentos que matrizes no meu sistema (Java 1.6 no meu iMac de um ano de idade).

Algum código:

 import java.util.*; public class ArrayVsArrayList { static public void main( String[] args ) { String[] array = new String[300]; ArrayList list = new ArrayList(300); for (int i=0; i<300; ++i) { if (Math.random() > 0.5) { array[i] = "abc"; } else { array[i] = "xyz"; } list.add( array[i] ); } int iterations = 100000000; long start_ms; int sum; start_ms = System.currentTimeMillis(); sum = 0; for (int i=0; i 

Não, porque tecnicamente, o array armazena apenas a referência às strings. As cadeias são alocadas em um local diferente. Para mil itens, eu diria que uma lista seria melhor, é mais lenta, mas oferece mais flexibilidade e é mais fácil de usar, especialmente se você for redimensioná-los.

Se você tem milhares, considere usar um trie. Uma trie é uma estrutura em forma de tree que mescla os prefixos comuns da string armazenada.

Por exemplo, se as cadeias fossem

 intern international internationalize internet internets 

O trie iria armazenar:

 intern -> \0 international -> \0 -> ize\0 net ->\0 ->s\0 

As cadeias de caracteres exigem 57 caracteres (incluindo o terminador nulo, ‘\ 0’) para armazenamento, mais qualquer que seja o tamanho do object String que os contenha. (Na verdade, provavelmente devemos arredondar todos os tamanhos para múltiplos de 16, mas …) Chame de 57 + 5 = 62 bytes, aproximadamente.

O trie requer 29 (incluindo o terminador nulo, ‘\ 0’) para armazenamento, mais o tamanho dos nós trie, que são uma referência a uma matriz e uma lista de nós filhos trie.

Para este exemplo, isso provavelmente é o mesmo; para milhares, provavelmente sai menos desde que você tenha prefixos comuns.

Agora, ao usar o trie em outro código, você terá que converter para String, provavelmente usando um StringBuffer como intermediário. Se muitas das cordas estão em uso ao mesmo tempo como Strings, fora da trie, é uma perda.

Mas se você está usando apenas alguns no momento – digamos, para pesquisar coisas em um dictionary – o trie pode economizar muito espaço. Definitivamente menos espaço do que armazená-los em um HashSet.

Você diz que está acessando-os “em série” – se isso significa sequencialmente um alfabeto, o trio também obviamente lhe dá ordem alfabética de graça, se você iterar a profundidade primeiro.

ATUALIZAR:

Como Mark notou, não houve diferença significativa após o aquecimento da JVM (várias passagens de teste). Verificado com matriz recriada ou até mesmo nova passagem começando com nova linha de matriz. Com grande probabilidade este conjunto simples de sinais com access ao índice não deve ser usado em favor de collections.

Ainda primeiro 1-2 passes simples array é 2-3 vezes mais rápido.

POSTE ORIGINAL:

Demasiadas palavras para o assunto muito simples de verificar. Sem qualquer array de perguntas é várias vezes mais rápido que qualquer contêiner de class . Corri nesta questão procurando alternativas para minha seção crítica de desempenho. Aqui está o código do protótipo que construí para verificar a situação real:

 import java.util.List; import java.util.Arrays; public class IterationTest { private static final long MAX_ITERATIONS = 1000000000; public static void main(String [] args) { Integer [] array = {1, 5, 3, 5}; List list = Arrays.asList(array); long start = System.currentTimeMillis(); int test_sum = 0; for (int i = 0; i < MAX_ITERATIONS; ++i) { // for (int e : array) { for (int e : list) { test_sum += e; } } long stop = System.currentTimeMillis(); long ms = (stop - start); System.out.println("Time: " + ms); } } 

E aqui está a resposta:

Baseado na matriz (a linha 16 está ativa):

 Time: 7064 

Com base na lista (a linha 17 está ativa):

 Time: 20950 

Mais algum comentário sobre 'mais rápido'? Isso é bem entendido. A questão é quando cerca de 3 vezes mais rápido é melhor para você do que a flexibilidade da Lista. Mas esta é outra questão. A propósito, verifiquei isso também com base na ArrayList construída manualmente. Quase o mesmo resultado.

Como já existem muitas boas respostas aqui, gostaria de fornecer algumas outras informações de visão prática, que são a comparação de desempenho de inserção e iteração: matriz primitiva vs Lista vinculada em Java.

Esta é uma verificação de desempenho simples real.
Então, o resultado dependerá do desempenho da máquina.

O código fonte usado para isso está abaixo:

 import java.util.Iterator; import java.util.LinkedList; public class Array_vs_LinkedList { private final static int MAX_SIZE = 40000000; public static void main(String[] args) { LinkedList lList = new LinkedList(); /* insertion performance check */ long startTime = System.currentTimeMillis(); for (int i=0; i 

O resultado de desempenho está abaixo:

insira a descrição da imagem aqui

Lembre-se de que um ArrayList encapsula um array, portanto, há pouca diferença em relação ao uso de um array primitivo (exceto pelo fato de que uma List é muito mais fácil de se trabalhar em java).

A única vez que faz sentido preferir uma matriz a uma ArrayList é quando você está armazenando primitivos, ou seja, byte, int, etc, e você precisa da eficiência de espaço que você obtém usando matrizes primitivas.

Array vs. List choice não é tão importante (considerando performance) no caso de armazenar objects string. Porque o array e a lista armazenam referências de objects de string, não os objects reais.

  1. Se o número de strings for quase constante, use um array (ou ArrayList). Mas se o número varia demais, é melhor usar o LinkedList.
  2. Se houver (ou haverá) necessidade de adicionar ou excluir elementos no meio, você certamente terá que usar o LinkedList.

Se você souber antecipadamente o tamanho dos dados, um array será mais rápido.

Uma lista é mais flexível. Você pode usar um ArrayList que é apoiado por um array.

lista é mais lento do que matrizes.Se você precisa de eficiência usar matrizes.Se você precisar de flexibilidade usar lista.

Você pode viver com um tamanho fixo, os arrays serão mais rápidos e precisarão de menos memory.

Se você precisar da flexibilidade da interface List com a adição e remoção de elementos, a questão permanece qual implementação você deve escolher. Freqüentemente ArrayList é recomendado e usado para qualquer caso, mas também ArrayList tem seus problemas de desempenho se elementos no início ou no meio da lista devem ser removidos ou inseridos.

Portanto, você pode querer dar uma olhada em http://java.dzone.com/articles/gaplist-%E2%80%93-lightning-fast-list que apresenta o GapList. Essa nova implementação de lista combina os pontos fortes de ArrayList e LinkedList, resultando em um desempenho muito bom para quase todas as operações.

Dependendo da implementação. É possível que uma matriz de tipos primitivos seja menor e mais eficiente que ArrayList. Isso ocorre porque a matriz armazenará os valores diretamente em um bloco contíguo de memory, enquanto a implementação ArrayList mais simples armazenará pointers para cada valor. Em uma plataforma de 64 bits, isso pode fazer uma enorme diferença.

É claro que é possível que a implementação do jvm tenha um caso especial para essa situação, caso em que o desempenho será o mesmo.

A lista é a maneira preferida no java 1.5 e além, pois pode usar genéricos. Matrizes não podem ter genéricos. Também os Arrays têm um comprimento pré-definido, que não pode crescer dinamicamente. Inicializar uma matriz com um tamanho grande não é uma boa ideia. ArrayList é o caminho para declarar um array com genéricos e pode crescer dinamicamente. Mas se excluir e inserir for usado com mais frequência, a linked list será a estrutura de dados mais rápida a ser usada.

Arrays recomendados em todos os lugares onde você pode usá-los em vez de listas, especialmente no caso de saber que os itens contam e o tamanho não mudaria.

Veja a prática recomendada do Oracle Java: http://docs.oracle.com/cd/A97688_16/generic.903/bp/java.htm#1007056

Claro, se você precisar adicionar e remover objects da coleção, muitas vezes, listas de uso fácil.

ArrayList armazena seus itens em uma matriz Object[] e usa o método toArray que é muito mais rápido (a barra azul) do que o typescript. Isso é seguro para os tipos, já que a matriz não digitada é empacotada no tipo genérico ArrayList que é verificado pelo compilador.

insira a descrição da imagem aqui

Este gráfico mostra uma referência com n = 5 no Java 7. No entanto, a imagem não muda muito com mais itens ou outra VM. A sobrecarga da CPU pode não parecer drástica, mas se sum. É provável que os consumidores de um array tenham que convertê-lo em uma coleção para fazer qualquer coisa com ele, então converta o resultado de volta em um array para alimentá-lo em outro método de interface, etc. Usar um ArrayList simples em vez de um array melhora o desempenho sem adicionar muita pegada. ArrayList adiciona uma sobrecarga constante de 32 bytes à matriz empacotada. Por exemplo, um array com dez objects requer 104 bytes, um ArrayList 136 bytes.

Essa operação é executada em tempo constante, por isso é muito mais rápida do que qualquer uma das opções acima (barra amarela). Isso não é o mesmo que uma cópia defensiva. Uma coleção não modificável mudará quando seus dados internos forem alterados. Se isso acontecer, os clientes poderão executar um ConcurrentModificationException enquanto iterar sobre os itens. Pode ser considerado design defeituoso que uma interface forneça methods que lançam uma UnsupportedOperationException em tempo de execução. No entanto, pelo menos para uso interno, esse método pode ser uma alternativa de alto desempenho para uma cópia defensiva – algo que não é possível com matrizes.

Nenhuma das respostas tinha informações que me interessavam – varredura repetitiva da mesma matriz muitas vezes. Tive que criar um teste JMH para isso.

Resultados (Java 1.8.0_66 x32, iterando matriz simples é pelo menos 5 vezes mais rápido que ArrayList):

 Benchmark Mode Cnt Score Error Units MyBenchmark.testArrayForGet avgt 10 8.121 ? 0.233 ms/op MyBenchmark.testListForGet avgt 10 37.416 ? 0.094 ms/op MyBenchmark.testListForEach avgt 10 75.674 ? 1.897 ms/op 

Teste

 package my.jmh.test; import java.util.ArrayList; import java.util.List; import java.util.concurrent.TimeUnit; import org.openjdk.jmh.annotations.Benchmark; import org.openjdk.jmh.annotations.BenchmarkMode; import org.openjdk.jmh.annotations.Fork; import org.openjdk.jmh.annotations.Measurement; import org.openjdk.jmh.annotations.Mode; import org.openjdk.jmh.annotations.OutputTimeUnit; import org.openjdk.jmh.annotations.Scope; import org.openjdk.jmh.annotations.State; import org.openjdk.jmh.annotations.Warmup; @State(Scope.Benchmark) @Fork(1) @Warmup(iterations = 5, timeUnit = TimeUnit.SECONDS) @Measurement(iterations = 10) @BenchmarkMode(Mode.AverageTime) @OutputTimeUnit(TimeUnit.MILLISECONDS) public class MyBenchmark { public final static int ARR_SIZE = 100; public final static int ITER_COUNT = 100000; String arr[] = new String[ARR_SIZE]; List list = new ArrayList<>(ARR_SIZE); public MyBenchmark() { for( int i = 0; i < ARR_SIZE; i++ ) { list.add(null); } } @Benchmark public void testListForEach() { int count = 0; for( int i = 0; i < ITER_COUNT; i++ ) { for( String str : list ) { if( str != null ) count++; } } if( count > 0 ) System.out.print(count); } @Benchmark public void testListForGet() { int count = 0; for( int i = 0; i < ITER_COUNT; i++ ) { for( int j = 0; j < ARR_SIZE; j++ ) { if( list.get(j) != null ) count++; } } if( count > 0 ) System.out.print(count); } @Benchmark public void testArrayForGet() { int count = 0; for( int i = 0; i < ITER_COUNT; i++ ) { for( int j = 0; j < ARR_SIZE; j++ ) { if( arr[j] != null ) count++; } } if( count > 0 ) System.out.print(count); } } 

“Milhares” não é um grande número. Alguns milhares de strings de tamanho de parágrafo são da ordem de alguns megabytes de tamanho. Se tudo o que você deseja fazer é acessá-los em série, use uma Lista unificada e imutável .

Não entre na armadilha de otimizar sem o benchmarking adequado. Como outros sugeriram, use um profiler antes de fazer qualquer suposição.

As diferentes estruturas de dados que você enumerou têm finalidades diferentes. Uma lista é muito eficiente na inserção de elementos no início e no final, mas sofre muito ao acessar elementos randoms. Uma matriz tem armazenamento fixo, mas fornece access random rápido. Finalmente, um ArrayList melhora a interface para um array, permitindo que ele cresça. Normalmente, a estrutura de dados a ser usada deve ser ditada pela maneira como os dados armazenados serão acessados ​​ou adicionados.

Sobre o consumo de memory. Você parece estar misturando algumas coisas. Uma matriz só lhe dará um pedaço contínuo de memory para o tipo de dados que você possui. Não se esqueça que o java tem um tipo de dados fixo: booleano, char, int, long, float e Object (isso inclui todos os objects, até mesmo um array é um Object). Isso significa que se você declarar uma matriz de seqüências de caracteres de seqüência de caracteres [1000] ou MyObject myObjects [1000] você obterá apenas 1000 checkboxs de memory grande o suficiente para armazenar o local (referências ou pointers) dos objects. You don’t get a 1000 memory boxes big enough to fit the size of the objects. Don’t forget that your objects are first created with “new”. This is when the memory allocation is done and later a reference (their memory address) is stored in the array. The object doesn’t get copied into the array only it’s reference.

I don’t think it makes a real difference for Strings. What is contiguous in an array of strings is the references to the strings, the strings themselves are stored at random places in memory.

Arrays vs. Lists can make a difference for primitive types, not for objects. IF you know in advance the number of elements, and don’t need flexibility, an array of millions of integers or doubles will be more efficient in memory and marginally in speed than a list, because indeed they will be stored contiguously and accessed instantly. That’s why Java still uses arrays of chars for strings, arrays of ints for image data, etc.

Array is faster – all memory is pre-allocated in advance.

A lot of microbenchmarks given here have found numbers of a few nanoseconds for things like array/ArrayList reads. This is quite reasonable if everything is in your L1 cache.

A higher level cache or main memory access can have order of magnitude times of something like 10nS-100nS, vs more like 1nS for L1 cache. Accessing an ArrayList has an extra memory indirection, and in a real application you could pay this cost anything from almost never to every time, depending on what your code is doing between accesses. And, of course, if you have a lot of small ArrayLists this might add to your memory use and make it more likely you’ll have cache misses.

The original poster appears to be using just one and accessing a lot of contents in a short time, so it should be no great hardship. But it might be different for other people, and you should watch out when interpreting microbenchmarks.

Java Strings, however, are appallingly wasteful, especially if you store lots of small ones (just look at them with a memory analyzer, it seems to be > 60 bytes for a string of a few characters). An array of strings has an indirection to the String object, and another from the String object to a char[] which contains the string itself. If anything’s going to blow your L1 cache it’s this, combined with thousands or tens of thousands of Strings. So, if you’re serious – really serious – about scraping out as much performance as possible then you could look at doing it differently. You could, say, hold two arrays, a char[] with all the strings in it, one after another, and an int[] with offsets to the starts. This will be a PITA to do anything with, and you almost certainly don’t need it. And if you do, you’ve chosen the wrong language.

I came here to get a better feeling for the performance impact of using lists over arrays. I had to adapt code here for my scenario: array/list of ~1000 ints using mostly getters, meaning array[j] vs. list.get(j)

Taking the best of 7 to be unscientific about it (first few with list where 2.5x slower) I get this:

 array Integer[] best 643ms iterator ArrayList best 1014ms iterator array Integer[] best 635ms getter ArrayList best 891ms getter (strange though) 

– so, very roughly 30% faster with array

The second reason for posting now is that no-one mentions the impact if you do math/matrix/simulation/optimization code with nested loops.

Say you have three nested levels and the inner loop is twice as slow you are looking at 8 times performance hit. Something that would run in a day now takes a week.

*EDIT Quite shocked here, for kicks I tried declaring int[1000] rather than Integer[1000]

 array int[] best 299ms iterator array int[] best 296ms getter 

Using Integer[] vs. int[] represents a double performance hit, ListArray with iterator is 3x slower than int[]. Really thought Java’s list implementations were similar to native arrays…

Code for reference (call multiple times):

  public static void testArray() { final long MAX_ITERATIONS = 1000000; final int MAX_LENGTH = 1000; Random r = new Random(); //Integer[] array = new Integer[MAX_LENGTH]; int[] array = new int[MAX_LENGTH]; List list = new ArrayList() {{ for (int i = 0; i < MAX_LENGTH; ++i) { int val = r.nextInt(); add(val); array[i] = val; } }}; long start = System.currentTimeMillis(); int test_sum = 0; for (int i = 0; i < MAX_ITERATIONS; ++i) { // for (int e : array) // for (int e : list) for (int j = 0; j < MAX_LENGTH; ++j) { int e = array[j]; // int e = list.get(j); test_sum += e; } } long stop = System.currentTimeMillis(); long ms = (stop - start); System.out.println("Time: " + ms); } 

It depends on how you have to access it.

After storing, if you mainly want to do search operation, with little or no insert/delete, then go for Array (as search is done in O(1) in arrays, whereas add/delete may need re-ordering of the elements).

After storing, if your main purpose is to add/delete strings, with little or no search operation, then go for List.

ArrayList internally uses array object to add(or store) the elements. In other words, ArrayList is backed by Array data -structure.The array of ArrayList is resizable (or dynamic).

Array is faster than Array because ArrayList internally use array. if we can directly add elements in Array and indirectly add element in Array through ArrayList always directly mechanism is faster than indirectly mechanism.

There are two overloaded add() methods in ArrayList class:
1. add(Object) : adds object to the end of the list.
2. add(int index , Object ) : inserts the specified object at the specified position in the list.

How the size of ArrayList grows dynamically?

 public boolean add(E e) { ensureCapacity(size+1); elementData[size++] = e; return true; } 

Important point to note from above code is that we are checking the capacity of the ArrayList , before adding the element. ensureCapacity() determines what is the current size of occupied elements and what is the maximum size of the array. If size of the filled elements (including the new element to be added to the ArrayList class) is greater than the maximum size of the array then increase the size of array. But the size of the array can not be increased dynamically. So what happens internally is new Array is created with capacity

Till Java 6

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

(Update) From Java 7

  int newCapacity = oldCapacity + (oldCapacity >> 1); 

also, data from the old array is copied into the new array.

Having overhead methods in ArrayList that’s why Array is faster than ArrayList .