Qual lista
https://stackoverflow.com/questions/135314
-
02-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
O que é a implementação mais rápida lista (em java) em um cenário onde a lista será criado um elemento de cada vez, em seguida, em um momento posterior ser lido um elemento de cada vez? A lê será feito com um iterador e, em seguida, a lista será então destruída.
Eu sei que a notação Big O para get é O (1) e adicionar é O (1) para um ArrayList, enquanto LinkedList é O (n) para get e O (1) para o add. Será que se comportam iterador com a mesma notação Big O?
Solução
Depende em grande parte se você sabe o tamanho máximo de cada lista na frente.
Se você fizer isso, ArrayList uso; certamente será mais rápido.
Caso contrário, você provavelmente vai ter que perfil. Embora o acesso ao ArrayList é O (1), a criação não é tão simples, por causa do redimensionamento dinâmico.
Outro ponto a considerar é que o espaço-tempo trade-off não é clara. Cada objeto Java tem um pouco de sobrecarga. Enquanto um ArrayList pode perder algum espaço em ranhuras excedentes, cada ranhura é de apenas 4 bytes (ou 8 em uma JVM de 64 bits). Cada elemento de um LinkedList é provavelmente cerca de 50 bytes (talvez 100 em uma JVM de 64 bits). Então você tem que ter algumas ranhuras desperdiçado em um ArrayList antes de um LinkedList realmente ganha sua vantagem espaço presumido. Localidade de referência é também um factor, e ArrayList é preferível há muito.
Na prática, eu quase sempre usar ArrayList.
Outras dicas
primeiros pensamentos:
- refatorar seu código para não precisar da lista.
- Simplificar os dados para baixo para um tipo de dados escalar, então, usar: int []
- Ou mesmo apenas usar uma matriz de qualquer objeto que você tem: Object [] - John Gardner
- Inicializar a lista para o tamanho total: new ArrayList (123);
Claro que, como toda a gente está mencionando, fazer testes de desempenho, provar a sua nova solução é uma melhoria.
iteração através de uma lista ligada é O (1) por elemento.
O tempo de execução Big O para cada opção é a mesma. Provavelmente o ArrayList será mais rápido por causa da melhor localidade memória, mas você tem que medir para saber com certeza. Escolha o que torna mais clara código.
Note-se que a iteração através de um exemplo de LinkedList pode ser O (n ^ 2) se feito ingènua. Especificamente:
List<Object> list = new LinkedList<Object>();
for (int i = 0; i < list.size(); i++) {
list.get(i);
}
Esta é absolutamente horrível em termos de eficiência devido ao fato de que a lista deve ser percorrido até i duas vezes para cada iteração. Se você fizer uso LinkedList, certifique-se de usar um Iterator ou Java 5 do reforçada for-loop:
for (Object o : list) {
// ...
}
O código de cima é o (n), uma vez que a lista é atravessada statefully no local.
Para evitar todos os problemas acima, é só usar ArrayList. Não é sempre a melhor escolha (especialmente para eficiência de espaço), mas geralmente é uma aposta segura.
Eu sugiro aferição ele. Uma coisa é ler a API, mas até que você experimentá-lo por si mesmo, ele tinha acadêmico.
Deve ser justo fácil de teste, apenas certifique-se de fazer operações significativas, ou hotspot vai out-esperto você e otimizar tudo para um NO-OP:)
Você certamente quer uma ArrayList . Ambos adicionar e leitura são "amortizados constante de tempo" (ou seja, O (1)), conforme especificado na documentação (note que isso é verdade mesmo que a lista tem de aumentar o seu tamanho - é concebido como que vêem http://java.sun.com/j2se/1.5.0/docs /api/java/util/ArrayList.html ). Se você sabe mais ou menos o número de objetos que você estará armazenando em seguida, até mesmo o aumento de tamanho ArrayList é eliminado.
Somando-se o fim de uma lista ligada é O (1), mas o multiplicador constante é maior do que ArrayList (desde que você está geralmente criando um objeto nó de cada vez). A leitura é praticamente idêntico ao do ArrayList se você estiver usando um iterador.
É uma boa regra para usar sempre a estrutura mais simples possível, a menos que haja uma boa razão para não. Aqui não existe tal razão.
A citação exata da documentação para ArrayList é: "O add corridas de operação em tempo constante amortizado, isto é, acrescentando n elementos requer tempo O (n) Todas as outras operações são executadas em tempo linear (grosso modo).. o fator constante é baixo quando comparado com que para a implementação LinkedList ".
Há uma nova implementação Lista chamado GlueList que é mais rápido do que todas as implementações clássico de lista.
Eu realmente começado a pensar que qualquer uso de estruturas de dados com comportamento não-determinístico, como ArrayList ou HashMap, deve ser evitado, então eu diria que só usam ArrayList se você pode obrigado seu tamanho; qualquer ilimitada LinkedList lista de uso. Isso é porque eu principalmente sistemas de código com requisitos de tempo quase real embora.
O principal problema é que qualquer alocação de memória (que poderia acontecer aleatoriamente com qualquer operação de adição) também poderia causar uma coleta de lixo, e qualquer coleta de lixo pode causar-lhe perder um alvo. Quanto maior for a alocação, o mais provável é que ocorra, e isso também é agravado se você estiver usando coletor CMS. CMS é não-compactação, assim que encontrar espaço para um novo nó lista ligada é geralmente vai ser mais fácil do que encontrar espaço para uma nova matriz 10.000 elemento.
A mais rigorosa a sua abordagem para a codificação, o mais perto que você pode chegar a tempo real com um JVM estoque. Mas escolher apenas estruturas de dados com o comportamento determinista é um dos primeiros passos que você teria que tomar.
