java over Qual é mais eficiente, um loop for-each ou um iterador?




java foreach iterable (6)

Qual é a maneira mais eficiente de percorrer uma coleção?

List<Integer>  a = new ArrayList<Integer>();
for (Integer integer : a) {
  integer.toString();
}

ou

List<Integer>  a = new ArrayList<Integer>();
for (Iterator iterator = a.iterator(); iterator.hasNext();) {
   Integer integer = (Integer) iterator.next();
   integer.toString();
}

Por favor note que esta não é uma cópia exata this , this , this ou this , embora uma das respostas à última questão se aproxime. A razão pela qual isso não é um dupe, é que a maioria deles está comparando loops onde você chama get(i) dentro do loop, em vez de usar o iterador.

Como sugerido no Meta , vou postar minha resposta para essa pergunta.


Se você está apenas vagando pela coleção para ler todos os valores, então não há diferença entre usar um iterador ou a nova sintaxe de loop for, já que a nova sintaxe simplesmente usa o iterador embaixo d'água.

Se, no entanto, você quer dizer por loop o antigo loop "c-style":

for(int i=0; i<list.size(); i++) {
   Object o = list.get(i);
}

Em seguida, o novo loop for, ou iterador, pode ser muito mais eficiente, dependendo da estrutura de dados subjacente. A razão para isto é que, para algumas estruturas de dados, get(i) é uma operação O (n), que torna o loop uma operação O (n2). Uma lista vinculada tradicional é um exemplo dessa estrutura de dados. Todos os iteradores têm como requisito fundamental que next() deve ser uma operação O (1), fazendo o loop O (n).

Para verificar se o iterador é usado debaixo d'água pela nova sintaxe do loop for, compare os bytecodes gerados dos dois trechos Java a seguir. Primeiro o loop for:

List<Integer>  a = new ArrayList<Integer>();
for (Integer integer : a)
{
  integer.toString();
}
// Byte code
 ALOAD 1
 INVOKEINTERFACE java/util/List.iterator()Ljava/util/Iterator;
 ASTORE 3
 GOTO L2
L3
 ALOAD 3
 INVOKEINTERFACE java/util/Iterator.next()Ljava/lang/Object;
 CHECKCAST java/lang/Integer
 ASTORE 2 
 ALOAD 2
 INVOKEVIRTUAL java/lang/Integer.toString()Ljava/lang/String;
 POP
L2
 ALOAD 3
 INVOKEINTERFACE java/util/Iterator.hasNext()Z
 IFNE L3

E segundo, o iterador:

List<Integer>  a = new ArrayList<Integer>();
for (Iterator iterator = a.iterator(); iterator.hasNext();)
{
  Integer integer = (Integer) iterator.next();
  integer.toString();
}
// Bytecode:
 ALOAD 1
 INVOKEINTERFACE java/util/List.iterator()Ljava/util/Iterator;
 ASTORE 2
 GOTO L7
L8
 ALOAD 2
 INVOKEINTERFACE java/util/Iterator.next()Ljava/lang/Object;
 CHECKCAST java/lang/Integer
 ASTORE 3
 ALOAD 3
 INVOKEVIRTUAL java/lang/Integer.toString()Ljava/lang/String;
 POP
L7
 ALOAD 2
 INVOKEINTERFACE java/util/Iterator.hasNext()Z
 IFNE L8

Como você pode ver, o código de bytes gerado é efetivamente idêntico, portanto, não há penalidade de desempenho ao usar um dos dois formulários. Portanto, você deve escolher a forma de loop que é mais esteticamente atraente para você, para a maioria das pessoas que será o loop for-each, já que tem menos código clichê.


O iterador é uma interface no framework Java Collections que fornece métodos para percorrer ou iterar em uma coleção.

O iterador e o loop funcionam de forma semelhante quando o motivo é apenas percorrer uma coleção para ler seus elementos.

for-each é apenas uma maneira de iterar sobre a coleção.

Por exemplo:

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

//using for-each loop
for(String msg: messages){
    System.out.println(msg);
}

//using iterator 
Iterator<String> it = messages.iterator();
while(it.hasNext()){
    String msg = it.next();
    System.out.println(msg);
}

E para cada loop pode ser usado apenas em objetos que implementam a interface do iterador.

Agora, voltemos ao caso do loop for e do iterador.

A diferença surge quando você tenta modificar uma coleção. Nesse caso, o iterador é mais eficiente devido à propriedade fail-fast . ie. ele verifica qualquer modificação na estrutura da coleção subjacente antes de iterar no próximo elemento. Se houver alguma modificação encontrada, ela lançará o ConcurrentModificationException .

(Observação: essa funcionalidade do iterador é aplicável apenas no caso de classes de coleta no pacote java.util. Não é aplicável a coleções simultâneas, pois elas são à prova de falhas por natureza)


A diferença não está no desempenho, mas na capacidade. Ao usar uma referência diretamente, você tem mais poder explicitamente usando um tipo de iterador (por exemplo, List.iterator () vs. List.listIterator (), embora na maioria dos casos eles retornem a mesma implementação). Você também tem a capacidade de referenciar o Iterador em seu loop. Isso permite que você faça coisas como remover itens de sua coleção sem obter um ConcurrentModificationException.

por exemplo

Está tudo bem

Set<Object> set = new HashSet<Object>();
// add some items to the set

Iterator<Object> setIterator = set.iterator();
while(setIterator.hasNext()){
     Object o = setIterator.next();
     if(o meets some condition){
          setIterator.remove();
     }
}

Isto não é, uma vez que irá lançar uma exceção de modificação concorrente:

Set<Object> set = new HashSet<Object>();
// add some items to the set

for(Object o : set){
     if(o meets some condition){
          set.remove(o);
     }
}

Devemos evitar o uso de loop tradicional ao trabalhar com coleções. A simples razão que eu darei é que a complexidade do loop for é da ordem O (sqr (n)) e complexidade do Iterator ou até mesmo o loop for aprimorado é apenas O (n). Por isso, dá uma diferença de desempenho .. Basta ter uma lista de cerca de 1000 itens e imprimi-lo usando os dois sentidos. e também imprime a diferença de tempo para a execução. Você pode ver a diferença.


O undereach foreach está criando o iterator , chamando hasNext () e chamando next () para obter o valor; O problema com o desempenho vem somente se você estiver usando algo que implementa o RandomomAccess.

for (Iterator<CustomObj> iter = customList.iterator(); iter.hasNext()){
   CustomObj custObj = iter.next();
   ....
}

Problemas de desempenho com o loop baseado em iterador é porque é:

  1. alocar um objeto mesmo se a lista estiver vazia ( Iterator<CustomObj> iter = customList.iterator(); );
  2. iter.hasNext() Durante cada iteração do loop, há uma chamada virtual invokeInterface (percorra todas as classes e, em seguida, faça a pesquisa da tabela de métodos antes do salto).
  3. a implementação do iterador tem que fazer pelo menos 2 campos de pesquisa para fazer a figura de chamada hasNext() o valor: # 1 obter contagem atual e # 2 obter contagem total
  4. dentro do loop do corpo, há outra chamada virtual iter.next (assim: percorrer todas as classes e fazer pesquisa de tabela de método antes do salto) e também tem que fazer pesquisa de campos: # 1 obter o índice e # 2 obter o referência ao array para fazer o offset nele (em cada iteração).

Uma potencial otimização é alternar para uma index iteration com a consulta de tamanho em cache:

for(int x = 0, size = customList.size(); x < size; x++){
  CustomObj custObj = customList.get(x);
  ...
}

Aqui temos:

  1. um método virtual invokeInterface chama customList.size() na criação inicial do loop for para obter o tamanho
  2. a chamada do método get customList.get(x) durante o corpo para loop, que é uma pesquisa de campo para a matriz e, em seguida, pode fazer o deslocamento na matriz

Nós reduzimos uma tonelada de chamadas de método, pesquisas de campo. Isso você não quer fazer com LinkedList ou com algo que não seja uma obj RandomAccess , caso contrário o customList.get(x) vai se transformar em algo que tem que percorrer o LinkedList em cada iteração.

Isso é perfeito quando você sabe que é qualquer coleção de lista baseada em RandomAccess .


Para expandir a resposta do próprio Paul, ele demonstrou que o bytecode é o mesmo daquele compilador em particular (presumivelmente o javac da Sun?), Mas não é garantido que compiladores diferentes gerem o mesmo bytecode, certo? Para ver qual é a diferença real entre os dois, vamos direto para a fonte e verificamos a Especificação da Linguagem Java, especificamente 14.14.2, "The enhanced for statement" :

O aprimorado for instrução é equivalente a um básico for declaração do formulário:

for (I #i = Expression.iterator(); #i.hasNext(); ) {
    VariableModifiers(opt) Type Identifier = #i.next();    
    Statement 
}

Em outras palavras, é exigido pelo JLS que os dois sejam equivalentes. Em teoria, isso poderia significar diferenças marginais no bytecode, mas na realidade o loop for aprimorado é necessário para:

  • Invoque o método .iterator()
  • Use .hasNext()
  • Disponibilizar a variável local via .next()

Então, em outras palavras, para todos os efeitos práticos, o bytecode será idêntico ou quase idêntico. É difícil imaginar qualquer implementação de compilador que resulte em qualquer diferença significativa entre os dois.





foreach