Qual é mais eficiente, um loop para cada ou um iterador?

206

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 este não é uma cópia exata do presente , presente , presente , ou esta , apesar de uma das respostas à última pergunta chega perto. A razão pela qual isso não é uma bobagem é que a maioria deles está comparando loops onde você chama get(i)dentro do loop, em vez de usar o iterador.

Conforme sugerido no Meta , postarei minha resposta a esta pergunta.

Paul Wagland
fonte
Eu acho que ele não fazer a diferença desde a sua Java eo mecanismo de templates é pouco mais do que o açúcar sintático
Hassan Syed
Duplicata em potencial: stackoverflow.com/questions/89891/…
OMG Ponies
2
@ Pôneis do OMG: não acredito que seja uma duplicata, pois isso não compara o loop com o iterador, mas pergunta por que as coleções retornam iteradores, em vez de tê-los diretamente na classe.
Paul Wagland

Respostas:

264

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

Se, no entanto, você quer dizer com loop o antigo loop "estilo c":

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

Então o novo loop for, ou iterador, pode ser muito mais eficiente, dependendo da estrutura de dados subjacente. A razão para isso é que, para algumas estruturas de dados, get(i)é uma operação O (n), que torna o loop uma operação O (n 2 ). 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 de loop for, compare os bytecodes gerados a partir dos dois snippets 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 qualquer um dos formulários. Portanto, você deve escolher a forma de loop mais esteticamente atraente para você, para a maioria das pessoas que será o loop for-each, pois possui menos código padrão.

Paul Wagland
fonte
4
Acredito que ele estava dizendo o contrário, que foo.get (i) pode ser muito menos eficiente. Pense no LinkedList. Se você fizer um foo.get (i) no meio de uma LinkedList, ele precisará atravessar todos os nós anteriores para chegar ao i. Um iterador, por outro lado, manterá um identificador para a estrutura de dados subjacente e permitirá que você percorra os nós, um de cada vez.
Michael Krauklis
1
Não é grande coisa, mas um for(int i; i < list.size(); i++) {loop de estilo também deve ser avaliado list.size()no final de cada iteração; se usado, às vezes é mais eficiente armazenar em cache o resultado list.size()primeiro.
Brett Ryan
3
Na verdade, a declaração original também é verdadeira para o caso de ArrayList e todos os outros que implementam a interface RandomAccess. O loop "estilo C" é mais rápido que o loop baseado no iterador. docs.oracle.com/javase/7/docs/api/java/util/RandomAccess.html
andresp
4
Um motivo para usar o loop antigo do estilo C em vez da abordagem do Iterator, independentemente de ser a versão foreach ou a desejada, é o lixo. Muitas estruturas de dados instanciam um novo Iterator quando .iterator () é chamado, no entanto, elas podem ser acessadas sem alocação usando o loop de estilo C. Isso pode ser importante em certos ambientes de alto desempenho em que se tenta evitar (a) atingir o alocador ou (b) coletas de lixo.
Dan
3
Assim como outro comentário, para ArrayLists, o loop for (int i = 0 ....) é cerca de duas vezes mais rápido que o uso do iterador ou da abordagem for (:), portanto, realmente depende da estrutura subjacente. E, como observação lateral, a iteração do HashSets também é muito cara (muito mais que uma Lista de matrizes), portanto, evite aquelas como a praga (se você puder).
Leo
106

A diferença não está no desempenho, mas na capacidade. Ao usar uma referência diretamente, você tem mais poder sobre explicitamente o uso de 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 pode referenciar o iterador em seu loop. Isso permite que você faça coisas como remover itens da sua coleção sem obter uma 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();
     }
}

Isso não é, pois lançará uma exceção de modificação simultânea:

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

for(Object o : set){
     if(o meets some condition){
          set.remove(o);
     }
}
Michael Krauklis
fonte
12
Isso é muito verdadeiro, mesmo que não responda diretamente à pergunta que eu marquei +1 por ser informativa e por responder à pergunta lógica subsequente.
Paul Wagland
1
Sim, podemos acessar elementos de coleção com loop foreach, mas não podemos removê-los, mas podemos remover elementos com o Iterator.
precisa saber é o seguinte
22

Para expandir a resposta de Paul, ele demonstrou que o bytecode é o mesmo naquele compilador específico (presumivelmente javac da Sun?), Mas não é garantido que diferentes compiladores gerem o mesmo bytecode, certo? Para ver qual é a diferença real entre os dois, vamos direto à fonte e verifique a Especificação da Linguagem Java, especificamente 14.14.2, "A declaração aprimorada" :

A fordeclaração aprimorada é equivalente a uma fordeclaração básica 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 pode significar diferenças marginais no código de bytes, mas na realidade o loop for aprimorado é necessário para:

  • Invocar o .iterator()método
  • Usar .hasNext()
  • Disponibilize a variável local via .next()

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

Cowan
fonte
Na verdade, o teste que fiz foi com o compilador Eclipse, mas seu argumento geral ainda permanece. +1
Paul Wagland 22/01
3

A parte foreachinferior está criando oiterator , chamando hasNext () e chamando next () para obter o valor; O problema com o desempenho ocorre apenas se você estiver usando algo que implemente o RandomomAccess.

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

Os problemas de desempenho com o loop baseado no iterador são:

  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 faça a pesquisa da tabela de métodos antes do salto).
  3. a implementação do iterador precisa fazer pelo menos 2 campos de pesquisa para tornar hasNext()o valor da chamada o valor: # 1 obter contagem atual e # 2 obter contagem total
  4. dentro do loop do corpo, há outra chamada virtual invokeInterface iter.next(assim: percorra todas as classes e faça a pesquisa da tabela de métodos antes do salto) e também faça a pesquisa de campos: # 1 obtenha o índice e # 2 obtenha a referência ao array para fazer o deslocamento nele (em todas as iterações).

Uma otimização potencial é mudar para umindex iteration com a pesquisa de tamanho em cache:

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

Aqui temos:

  1. uma chamada de método virtual invokeInterface 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 loop for do corpo, que é uma pesquisa de campo na matriz e, em seguida, pode fazer o deslocamento na matriz

Reduzimos uma tonelada de chamadas de método, pesquisas de campo. Isso você não quer fazer com LinkedListou com algo que não seja um RandomAccessobjeto de coleção, caso contrário, ele customList.get(x)se transformará em algo que terá que atravessar a LinkedListcada iteração.

Isso é perfeito quando você sabe que existe qualquer RandomAccesscoleção de listas baseada.

denis_lor
fonte
1

foreachusa iteradores sob o capô de qualquer maneira. Realmente é apenas açúcar sintático.

Considere o seguinte programa:

import java.util.List;
import java.util.ArrayList;

public class Whatever {
    private final List<Integer> list = new ArrayList<>();
    public void main() {
        for(Integer i : list) {
        }
    }
}

Vamos compilá-lo com javac Whatever.java,
e ler o bytecode desmontado de main(), usando javap -c Whatever:

public void main();
  Code:
     0: aload_0
     1: getfield      #4                  // Field list:Ljava/util/List;
     4: invokeinterface #5,  1            // InterfaceMethod java/util/List.iterator:()Ljava/util/Iterator;
     9: astore_1
    10: aload_1
    11: invokeinterface #6,  1            // InterfaceMethod java/util/Iterator.hasNext:()Z
    16: ifeq          32
    19: aload_1
    20: invokeinterface #7,  1            // InterfaceMethod java/util/Iterator.next:()Ljava/lang/Object;
    25: checkcast     #8                  // class java/lang/Integer
    28: astore_2
    29: goto          10
    32: return

Podemos ver que é foreachcompilado em um programa que:

  • Cria o iterador usando List.iterator()
  • If Iterator.hasNext(): chama Iterator.next()e continua o loop

Quanto a "por que esse loop inútil não é otimizado a partir do código compilado? Podemos ver que ele não faz nada com o item da lista": bem, é possível codificar seu iterável de modo que .iterator()tenha efeitos colaterais , ou que .hasNext()tenha efeitos colaterais ou consequências significativas.

Você pode imaginar facilmente que uma iterável que representa uma consulta rolável de um banco de dados pode fazer algo dramático .hasNext()(como entrar em contato com o banco de dados ou fechar um cursor porque você atingiu o final do conjunto de resultados).

Portanto, mesmo que possamos provar que nada acontece no corpo do loop ... é mais caro (intratável?) Provar que nada significativo / conseqüente acontece quando iteramos. O compilador deve deixar esse corpo de loop vazio no programa.

O melhor que poderíamos esperar seria um aviso do compilador . É interessante que javac -Xlint:all Whatever.javafaz não avisar-nos sobre este corpo de loop vazio. O IntelliJ IDEA faz isso. É certo que eu configurei o IntelliJ para usar o Eclipse Compiler, mas talvez não seja esse o motivo.

insira a descrição da imagem aqui

Birchlabs
fonte
0

O iterador é uma interface na estrutura Java Collections que fornece métodos para percorrer ou iterar sobre uma coleção.

O iterador e o loop for agem de maneira semelhante quando seu 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, de volta ao caso do loop e iterador for.

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

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

eccentricCoder
fonte
1
Sua afirmação sobre a diferença não é verdadeira, o loop for each também usa um iterador subaquático e, portanto, tem o mesmo comportamento.
Paul Wagland 28/02
@Pault Wagland, eu modifiquei a minha resposta obrigado por apontar o erro
eccentricCoder
suas atualizações ainda não são precisas. Os dois trechos de código que você possui são definidos pelo idioma para serem os mesmos. Se houver alguma diferença no comportamento, isso é um bug na implementação. A única diferença é se você tem ou não acesso ao iterador.
Paul Wagland 28/02
@ Paul Wagland Mesmo se você usar a implementação padrão de cada loop que usa um iterador, ele ainda emitirá uma exceção se você tentar usar o método remove () durante operações simultâneas. Verificação geral a seguir para obter mais informações aqui
eccentricCoder
1
com o loop for each, você não obtém acesso ao iterador; portanto, não pode chamar remover nele. Mas isso não vem ao caso, na sua resposta você afirma que um é seguro para threads, enquanto o outro não. De acordo com a especificação da linguagem, eles são equivalentes; portanto, ambos são tão seguros quanto o segmento de coleções subjacentes.
Paul Wagland 28/02
-8

Devemos evitar o uso do loop for tradicional ao trabalhar com o Collections. A razão simples que mostrarei é que a complexidade do loop for é da ordem O (sqr (n)) e a complexidade do Iterator ou mesmo o loop for aprimorado é apenas O (n). Portanto, há uma diferença de desempenho. Basta pegar uma lista de 1000 itens e imprimi-la usando os dois lados. e também imprima a diferença de horário para a execução. Você pode ver a diferença.

Chandan
fonte
adicione alguns exemplos ilustrativos para apoiar suas declarações.
Rajesh Pitty
@ Chandan Desculpe, mas o que você escreveu está errado. Por exemplo: std :: vector também é uma coleção, mas seu acesso custa O (1). Portanto, um loop for tradicional sobre um vetor é apenas O (n). Eu acho que você quer dizer, se o acesso do contêiner subjacente tem custo de acesso de O (n), então é para std :: list, que existe uma complexidade de O (n ^ 2). O uso de iteradores nesse caso reduzirá o custo para O (n), porque os iteradores permitem acesso direto aos elementos.
Kaiser #
Se você fizer o cálculo da diferença de horário, verifique se os dois conjuntos estão classificados (ou distribuídos aleatoriamente de maneira não ordenada) e execute o teste duas vezes para cada conjunto e calcule a segunda execução apenas de cada um. Verifique seus horários novamente com isso (é uma longa explicação de por que você precisa executar o teste duas vezes). Você precisa demonstrar (talvez com código) como isso é verdade. Caso contrário, tanto quanto eu sei, ambos são idênticos em termos de desempenho, mas não de capacidade.
Ydobonebi