Eu tenho que manter milhares de strings na memória para ser acessado serialmente em Java. Devo armazená-los em uma matriz ou devo usar algum tipo de lista?

Como matrizes mantêm todos os dados em um pedaço contíguo de memória (ao contrário de Listas), o uso de uma matriz para armazenar milhares de seqüências causaria problemas?

Sugiro que você use um criador de perfil 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 usava matrizes em todos os lugares . Isso tornou o código muito inflexível. Depois de alterar grandes partes dele para Listas, notamos nenhuma 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 seqüências de caracteres como uma lista e, em seguida, inicialize-a usando a implementação ArrayList.

List<String> strings = new ArrayList<String>();

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

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

De fato, o ArrayList foi projetado especificamente para substituir a construção de matriz de baixo nível na maioria dos contextos. Se o Java estivesse sendo projetado hoje, é perfeitamente possível que as matrizes tivessem sido totalmente excluídas em favor da construção ArrayList.

Como matrizes mantêm todos os dados em um pedaço contíguo de memória (ao contrário de Listas), o uso de uma matriz para armazenar milhares de seqüências causaria problemas?

Em Java, todas as coleções armazenam apenas referências a objetos, não os próprios objetos. As matrizes e ArrayList armazenam alguns milhares de referências em uma matriz contígua, portanto, são essencialmente idênticas. Você pode considerar que um bloco contíguo de alguns milhares de referências de 32 bits estará sempre prontamente disponível no hardware moderno. Isso não garante que você não fique completamente sem memória, é claro, apenas que o requisito de bloco de memória contíguo não é difícil de preencher.

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

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

• crie
• definir um item
• obter um item
• clonar / copiar

Conclusão geral

Embora as operações get e set sejam um pouco mais lentas em um ArrayList (resp. 1 e 3 nanossegundos por chamada em minha máquina), há muito pouco uso de um ArrayList vs. um array para qualquer uso não intensivo. No entanto, há algumas coisas a serem lembradas:

• operações de redimensionamento em uma lista (ao chamar list.add(...)) são caras e deve-se tentar definir a capacidade inicial em um nível adequado sempre que possível (observe que o mesmo problema ocorre ao usar uma matriz)
• ao lidar com primitivas, as matrizes podem ser significativamente mais rápidas, pois permitem evitar muitas conversões de boxe / unboxing
• um aplicativo que apenas obtém / define valores em um ArrayList (não muito comum!) pode ver um ganho de desempenho superior a 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 (tempos em nanossegundos) com o JDK 7 em uma máquina desktop x86 padrão. Observe que o ArrayList nunca é redimensionado nos testes para garantir que os resultados sejam comparáveis. Código de referência disponível aqui .

Criação de array / ArrayList

Eu executei 4 testes, executando as seguintes instruções:

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

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

a.p.g.a.ArrayVsList.CreateArray1         [10.933, 11.097]
a.p.g.a.ArrayVsList.CreateList1          [10.799, 11.046]
a.p.g.a.ArrayVsList.CreateArray10000    [394.899, 404.034]
a.p.g.a.ArrayVsList.CreateList10000     [396.706, 401.266]

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

obter operações

Eu executei 2 testes, executando as seguintes instruções:

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

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

a.p.g.a.ArrayVsList.getArray   [2.958, 2.984]
a.p.g.a.ArrayVsList.getList    [3.841, 3.874]

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

definir operações

Eu executei 2 testes, executando as seguintes instruções:

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

Resultados (em nanossegundos por chamada):

a.p.g.a.ArrayVsList.setArray   [4.201, 4.236]
a.p.g.a.ArrayVsList.setList    [6.783, 6.877]

Conclusão: as operações de configuração em matrizes são cerca de 40% mais rápidas que nas listas, mas, quanto ao get, cada operação de configuração leva alguns nanossegundos - portanto, para que a diferença atinja 1 segundo, seria necessário definir itens na lista / matriz centenas de milhões de vezes!

clonar / copiar

Delegados cópia do construtor de ArrayList para Arrays.copyOfisso o desempenho é idêntica à matriz cópia (cópia de uma matriz por meio de clone, Arrays.copyOfou System.arrayCopy não faz qualquer diferença significativa em termos de performance ).

Você deve preferir tipos genéricos sobre matrizes. Conforme mencionado por outros, matrizes são inflexíveis e não têm o poder expressivo de tipos genéricos. (No entanto, eles suportam a digitação em tempo de execução, mas isso se mistura muito com tipos genéricos.)

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

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

Eu estou supondo que o pôster original é proveniente de um background C ++ / STL, o que está causando alguma confusão. Em C ++, std::listhá uma lista duplamente vinculada.

Em Java [java.util.]Listé uma interface livre de implementação (classe abstrata pura em termos de C ++). Listpode ser uma lista duplamente vinculada - java.util.LinkedListé fornecida. No entanto, 99 vezes em 100 quando você deseja criar um novo List, deseja usar java.util.ArrayList, que é o equivalente aproximado de C ++ std::vector. Existem outras implementações padrão, como as retornadas por java.util.Collections.emptyList()e java.util.Arrays.asList().

Do ponto de vista de desempenho, há um pequeno impacto de ter que passar por uma interface e um objeto extra, no entanto, a execução em tempo de execução significa que isso raramente tem algum significado. Lembre-se também de que Stringnormalmente são um objeto mais uma matriz. Portanto, para cada entrada, você provavelmente tem dois outros objetos. No C ++ std::vector<std::string>, apesar de copiar por valor sem um ponteiro, as matrizes de caracteres formarão um objeto para string (e geralmente não serão compartilhadas).

Se esse código em particular for realmente sensível ao desempenho, você poderá criar uma única char[]matriz (ou mesmo byte[]) para todos os caracteres de todas as seqüências e, em seguida, uma matriz de compensações. IIRC, é assim que o javac é implementado.

Concordo que na maioria dos casos você deve escolher a flexibilidade e a elegância das ArrayLists em vez das 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 poucas alterações estruturais (sem adição e remoção) para, digamos, renderização de gráficos de software ou uma máquina virtual personalizada, meus testes de benchmarking de acesso sequencial mostram que ArrayLists são 1,5x mais lentas do que as matrizes no meu sistema (Java 1.6 no meu iMac de um ano).

Algum código:

import java.util.*;

public class ArrayVsArrayList {
    static public void main( String[] args ) {

        String[] array = new String[300];
        ArrayList<String> list = new ArrayList<String>(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<iterations; ++i) {
          for (int j=0; j<300; ++j) sum += array[j].length();
        }

        System.out.println( (System.currentTimeMillis() - start_ms) + " ms (array)" );
        // Prints ~13,500 ms on my system

        start_ms = System.currentTimeMillis();
        sum = 0;

        for (int i=0; i<iterations; ++i) {
          for (int j=0; j<300; ++j) sum += list.get(j).length();
        }

        System.out.println( (System.currentTimeMillis() - start_ms) + " ms (ArrayList)" );
        // Prints ~20,800 ms on my system - about 1.5x slower than direct array access
    }
}

Bem, em primeiro lugar, vale a pena esclarecer que você quer dizer "lista" no sentido clássico das estruturas de dados de ficção científica (ou seja, uma lista vinculada) ou quer dizer java.util.List? Se você quer dizer um java.util.List, é uma interface. Se você deseja usar uma matriz, basta usar a implementação ArrayList e obterá um comportamento e semântica semelhantes a uma matriz. Problema resolvido.

Se você quer dizer uma matriz versus uma lista vinculada, é um argumento um pouco diferente para o qual voltamos ao Big O (aqui está uma explicação clara em inglês, se esse é um termo desconhecido).

Matriz;

• Acesso aleatório: O (1);
• Inserção: O (n);
• Excluir: O (n).

Lista vinculada:

• Acesso aleatório: O (n);
• Inserção: O (1);
• Apagar: O (1).

Assim, você escolhe o que melhor se adapta à forma como redimensiona sua matriz. Se você redimensionar, insira e exclua muito, talvez uma lista vinculada seja a melhor opção. O mesmo vale se o acesso aleatório for raro. Você mencionou o acesso serial. Se você está fazendo principalmente acesso serial com muito pouca modificação, provavelmente não importa qual você escolher.

As listas vinculadas têm uma sobrecarga um pouco maior, pois, como você diz, você está lidando com blocos de memória potencialmente não contíguos e (efetivamente) ponteiros para o próximo elemento. Provavelmente esse não é um fator importante, a menos que você esteja lidando com milhões de entradas.

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

Portanto, se você não está fazendo nada além de iterar a lista e está fazendo muito, talvez valha a pena a otimização. Senão, eu deveria usar a lista, porque vai torná-lo mais fácil quando você fazer necessidade de otimizar o código.

NB I fez aviso que o uso for String s: stringsListfoi cerca de 50% mais lento do que usar um estilo antigo loop for para acessar a lista. Vai entender ... Aqui estão as duas funções que cronometrei; a matriz e a lista foram preenchidas com 5000 seqüências 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<String> 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();
        }
    }
}

Não, porque tecnicamente, o array armazena apenas a referência às strings. As próprias strings 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ê deseja redimensioná-las.

Se você tem milhares, considere usar um trie. Um trie é uma estrutura semelhante a uma árvore que mescla os prefixos comuns da sequência armazenada.

Por exemplo, se as strings fossem

intern
international
internationalize
internet
internets

O trie armazenaria:

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

As strings requerem 57 caracteres (incluindo o terminador nulo, '\ 0') para armazenamento, mais qualquer que seja o tamanho do objeto String que os contém. (Na verdade, provavelmente devemos arredondar todos os tamanhos até múltiplos de 16, mas ...) Chame 57 + 5 = 62 bytes, aproximadamente.

A 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 trie filhos.

Para este exemplo, isso provavelmente sai da mesma forma; para milhares, provavelmente sai menos, desde que você tenha prefixos comuns.

Agora, ao usar o trie em outro código, você precisará converter para String, provavelmente usando um StringBuffer como intermediário. Se muitas das strings estiverem em uso ao mesmo tempo como Strings, fora do teste, será uma perda.

Mas se você estiver usando apenas alguns, por exemplo - para procurar coisas em um dicionário -, o teste pode economizar muito espaço. Definitivamente menos espaço do que armazená-los em um HashSet.

Você diz que está acessando-os "serialmente" - se isso significa sequencialmente uma ordem alfabética, o trie também obviamente fornece ordem alfabética gratuitamente, se você iterá-la em profundidade primeiro.

ATUALIZAR:

Como Mark observou, não há diferença significativa após o aquecimento da JVM (várias passagens do teste). Verificado com matriz recriada ou mesmo nova passagem, iniciando com nova linha de matriz. Com grande probabilidade, isso indica que uma matriz simples com acesso ao índice não deve ser usada em favor de coleções.

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

POST ORIGINAL:

Palavras demais para o assunto muito simples de verificar. Sem nenhuma matriz de perguntas, é várias vezes mais rápido que qualquer contêiner de classe . Eu corro nessa 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<Integer> 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:

Com base 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 três vezes mais rápido é melhor para você do que a flexibilidade da lista. Mas essa é outra questão. A propósito, eu verifiquei isso também com base em construído manualmente ArrayList. Quase o mesmo resultado.

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

Esta é uma verificação de desempenho simples real.
Portanto, 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<MAX_SIZE; i++) {
            lList.add(i);
        }

        long stopTime = System.currentTimeMillis();
        long elapsedTime = stopTime - startTime;
        System.out.println("[Insert]LinkedList insert operation with " + MAX_SIZE + " number of integer elapsed time is " + elapsedTime + " millisecond.");

        int[] arr = new int[MAX_SIZE];

        startTime = System.currentTimeMillis();
        for(int i=0; i<MAX_SIZE; i++){
            arr[i] = i; 
        }

        stopTime = System.currentTimeMillis();
        elapsedTime = stopTime - startTime;
        System.out.println("[Insert]Array Insert operation with " + MAX_SIZE + " number of integer elapsed time is " + elapsedTime + " millisecond.");


        /* iteration performance check */

        startTime = System.currentTimeMillis();

        Iterator itr = lList.iterator();

        while(itr.hasNext()) {
            itr.next();
            // System.out.println("Linked list running : " + itr.next());
        }

        stopTime = System.currentTimeMillis();
        elapsedTime = stopTime - startTime;
        System.out.println("[Loop]LinkedList iteration with " + MAX_SIZE + " number of integer elapsed time is " + elapsedTime + " millisecond.");


        startTime = System.currentTimeMillis();

        int t = 0;
        for (int i=0; i < MAX_SIZE; i++) {
            t = arr[i];
            // System.out.println("array running : " + i);
        }

        stopTime = System.currentTimeMillis();
        elapsedTime = stopTime - startTime;
        System.out.println("[Loop]Array iteration with " + MAX_SIZE + " number of integer elapsed time is " + elapsedTime + " millisecond.");
    }
}

O resultado de desempenho está abaixo:

A lista é mais lenta que as matrizes. Se você precisar de eficiência, use matrizes. Se precisar de flexibilidade, use lista.

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

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

A escolha da matriz versus a lista não é tão importante (considerando o desempenho) no caso de armazenar objetos de sequência. Como a matriz e a lista armazenam referências de objetos de seqüência de caracteres, não os objetos reais.

1. Se o número de strings for quase constante, use uma matriz (ou ArrayList). Mas se o número variar muito, é melhor usar o LinkedList.
2. Se houver (ou haverá) a necessidade de adicionar ou excluir elementos no meio, você certamente precisará usar o LinkedList.

Eu vim aqui para ter uma idéia melhor do impacto no desempenho do uso de listas sobre matrizes. Eu tive que adaptar o código aqui para o meu cenário: array / lista de ~ 1000 ints usando principalmente getters, o que significa array [j] vs. list.get (j)

Tomando o melhor de 7 para não ser científico sobre isso (primeiro com lista onde 2,5x mais lento), entendi o seguinte:

array Integer[] best 643ms iterator
ArrayList<Integer> best 1014ms iterator

array Integer[] best 635ms getter
ArrayList<Integer> best 891ms getter (strange though)

- aproximadamente 30% mais rápido com o array

A segunda razão para postar agora é que ninguém menciona o impacto se você fizer código matemático / matriz / simulação / otimização com loops aninhados .

Digamos que você tenha três níveis aninhados e o loop interno seja duas vezes mais lento que você está olhando 8 vezes o desempenho atingido. Algo que funcionaria em um dia agora leva uma semana.

* EDIT Muito chocado aqui, por chutes tentei declarar int [1000] ao invés de Inteiro [1000]

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

Usando o número inteiro [] vs. int [] representa uma ocorrência de desempenho duplo, o ListArray com o iterador é 3x mais lento que o int []. Realmente pensei que as implementações de lista do Java eram semelhantes às matrizes nativas ...

Código de referência (ligue várias vezes):

    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<Integer> list = new ArrayList<Integer>()
        {{
            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);
    }

Se você souber com antecedência qual é o tamanho dos dados, uma matriz será mais rápida.

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

Se você pode viver com um tamanho fixo, as matrizes serão mais rápidas e precisarão de menos memória.

Se você precisar da flexibilidade da interface da lista para adicionar e remover elementos, a questão permanece: qual implementação você deve escolher. Freqüentemente, o ArrayList é recomendado e usado para qualquer caso, mas o ArrayList também apresenta problemas de desempenho se os elementos no início ou no meio da lista tiverem que ser removidos ou inseridos.

Portanto, convém 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 armazena os valores diretamente em um bloco de memória contíguo, enquanto a implementação ArrayList mais simples armazena ponteiros para cada valor. Especialmente em uma plataforma de 64 bits, isso pode fazer uma enorme diferença.

Obviamente, é possível que a implementação da jvm tenha um caso especial para essa situação; nesse caso, 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. As matrizes também têm um comprimento predefinido, que não pode crescer dinamicamente. Iniciar uma matriz com um tamanho grande não é uma boa ideia. ArrayList é a maneira de declarar uma matriz com genéricos e pode crescer dinamicamente. Porém, se excluir e inserir é usado com mais frequência, a lista vinculada é a estrutura de dados mais rápida a ser usada.

Matrizes recomendadas em todos os lugares em que você pode usá-las em vez de listar, especialmente se você souber que a contagem e o tamanho dos itens não serão alterados.

Consulte as práticas recomendadas do Oracle Java: http://docs.oracle.com/cd/A97688_16/generic.903/bp/java.htm#1007056

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

Nenhuma das respostas tinha informações nas quais eu estava interessado - varredura repetitiva da mesma matriz muitas e muitas vezes. Teve que criar um teste JMH para isso.

Resultados (Java 1.8.0_66 x32, a iteração da matriz simples é pelo menos 5 vezes mais rápida que o 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<String> 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 número grande. Alguns milhares de strings de comprimento de parágrafo são da ordem de alguns megabytes de tamanho. Se tudo o que você deseja fazer é acessar esses itens em série, use uma Lista vinculada imutável e isolada .

Não caia na armadilha de otimizar sem um benchmarking adequado. Como outros sugeriram, use um criador de perfil 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 aleatórios. Uma matriz possui armazenamento fixo, mas fornece acesso aleatório rápido. Finalmente, um ArrayList melhora a interface de 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 memória. Você parece estar misturando algumas coisas. Uma matriz fornecerá apenas um pedaço contínuo de memória para o tipo de dados que você possui. Não esqueça que o java possui tipos de dados fixos: booleano, char, int, long, float e Object (isso inclui todos os objetos, até mesmo uma matriz é um Objeto). Isso significa que se você declarar uma matriz de seqüências de caracteres String [1000] ou MyObject myObjects [1000], obterá apenas 1000 caixas de memória grandes o suficiente para armazenar a localização (referências ou ponteiros) dos objetos. Você não recebe 1000 caixas de memória grandes o suficiente para caber no tamanho dos objetos. Não esqueça que seus objetos foram criados pela primeira vez com "novo". É quando a alocação de memória é concluída e, posteriormente, uma referência (seu endereço de memória) é armazenada na matriz. O objeto não é copiado para a matriz, apenas sua referência.

Eu não acho que isso faça uma diferença real para o Strings. O que é contíguo em uma matriz de cadeias de caracteres são as referências às cadeias, as próprias cadeias são armazenadas em lugares aleatórios na memória.

Matrizes vs. listas podem fazer a diferença para tipos primitivos, não para objetos. Se você conhece antecipadamente o número de elementos e não precisa de flexibilidade, uma matriz de milhões de números inteiros ou duplos será mais eficiente na memória e marginalmente na velocidade do que na lista, porque eles serão armazenados de forma contígua e acessados ​​instantaneamente. É por isso que o Java ainda usa matrizes de caracteres para seqüências de caracteres, matrizes de entradas para dados de imagem etc.

A matriz é mais rápida - toda a memória é pré-alocada com antecedência.

Muitas marcas de micropigmentação fornecidas aqui encontraram números de alguns nanossegundos para coisas como leituras de array / ArrayList. Isso é bastante razoável se tudo estiver no cache L1.

Um cache de nível superior ou acesso à memória principal pode ter tempos de magnitude de ordem de algo como 10nS-100nS, em comparação com 1nS para o cache L1. O acesso a um ArrayList possui uma indireção extra de memória e, em um aplicativo real, você pode pagar esse custo de quase nunca a todas as vezes, dependendo do que seu código está fazendo entre os acessos. E, é claro, se você tiver muitas ArrayLists pequenas, isso pode aumentar o uso da memória e aumentar a probabilidade de falhas no cache.

O pôster original parece estar usando apenas um e acessando muitos conteúdos em um curto espaço de tempo, portanto não deve haver grandes dificuldades. Mas pode ser diferente para outras pessoas, e você deve ter cuidado ao interpretar marcas de micropigmentação.

As Java Strings, no entanto, são terrivelmente desperdiçadas, especialmente se você armazenar muitas pequenas (basta olhar para elas com um analisador de memória, parece ser> 60 bytes para uma sequência de poucos caracteres). Uma matriz de seqüências de caracteres tem uma indireta para o objeto String e outra do objeto String para um char [] que contém a própria string. Se alguma coisa vai explodir seu cache L1, é isso, combinado com milhares ou dezenas de milhares de Strings. Portanto, se você está falando sério - realmente sério - sobre como obter o máximo de desempenho possível, pode pensar em fazê-lo de maneira diferente. Você poderia, digamos, manter duas matrizes, um caractere [] com todas as seqüências de caracteres, um após o outro, e um int [] com deslocamentos para o início. Será uma PITA para fazer qualquer coisa, e você quase certamente não precisa dela. E se você faz, você '

Depende de como você deve acessá-lo.

Após o armazenamento, se você deseja fazer principalmente uma operação de pesquisa, com pouca ou nenhuma inserção / exclusão, vá para Matriz (como a pesquisa é feita em O (1) nas matrizes, enquanto adicionar / excluir pode precisar reordenar os elementos) .

Após o armazenamento, se o seu principal objetivo for adicionar / excluir seqüências de caracteres, com pouca ou nenhuma operação de pesquisa, vá para Lista.

ArrayList internamente usa o objeto de matriz para adicionar (ou armazenar) os elementos. Em outras palavras, o ArrayList é apoiado por dados-estrutura do array. O array do ArrayList é redimensionável (ou dinâmico).

Matriz é mais rápida que Matriz porque ArrayList usa internamente matriz. se podemos adicionar diretamente elementos em Array e indiretamente, adicionar elementos a Array através de ArrayList, sempre o mecanismo diretamente é mais rápido que o mecanismo indiretamente.

Existem dois métodos add () sobrecarregados na classe ArrayList:
1 add(Object) .: adiciona um objeto ao final da lista.
2 add(int index , Object ) .: insere o objeto especificado na posição especificada na lista.

Como o tamanho do ArrayList cresce dinamicamente?

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

Um ponto importante a ser observado no código acima é que estamos verificando a capacidade do ArrayList, antes de adicionar o elemento. sureCapacity () determina qual é o tamanho atual dos elementos ocupados e qual é o tamanho máximo da matriz. Se o tamanho dos elementos preenchidos (incluindo o novo elemento a ser adicionado à classe ArrayList) for maior que o tamanho máximo da matriz, aumente o tamanho da matriz. Mas o tamanho da matriz não pode ser aumentado dinamicamente. Então, o que acontece internamente é que um novo array é criado com capacidade

Até Java 6

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

(Atualização) do Java 7

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

Além disso, os dados da matriz antiga são copiados para a nova matriz.

Tendo métodos de sobrecarga no ArrayList, é por isso que o Array é mais rápido que ArrayList.

Matrizes - sempre seria melhor quando temos que obter resultados mais rápidos

Listas - Executa resultados de inserção e exclusão, pois eles podem ser feitos em O (1) e isso também fornece métodos para adicionar, buscar e excluir dados facilmente. Muito mais fácil de usar.

Mas lembre-se sempre de que a busca de dados seria rápida quando a posição do índice na matriz em que os dados são armazenados - for conhecida.

Isso pode ser alcançado bem, classificando a matriz. Portanto, isso aumenta o tempo para buscar os dados (ou seja, armazenar os dados + classificar os dados + procurar a posição em que os dados são encontrados). Portanto, isso aumenta a latência adicional para buscar os dados da matriz, mesmo que eles sejam bons em buscar os dados mais cedo.

Portanto, isso poderia ser resolvido com uma estrutura de dados trie ou estrutura de dados ternária. Como discutido acima, a estrutura de dados trie seria muito eficiente na pesquisa dos dados. A pesquisa de uma palavra específica pode ser feita na magnitude de O (1). Quando o tempo importa, ie; se você precisar pesquisar e recuperar dados rapidamente, poderá usar a estrutura de dados trie.

Se você deseja que seu espaço de memória seja menos consumido e deseja ter um melhor desempenho, siga a estrutura de dados ternária. Ambos são adequados para armazenar um grande número de strings (por exemplo, palavras semelhantes contidas no dicionário).