Что является более эффективным: цикл для каждого или итератор?

Какой самый эффективный способ пройти через коллекцию?

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

или же

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

Обратите внимание, что это не является точной копией этого, этого, этого или этого, хотя один из ответов на последний вопрос подходит близко. Причина того, что это не обман, в том, что большинство из них сравнивают циклы, где вы вызываете get(i) внутри цикла, а не с помощью итератора.

Как предложено на Meta, я буду публиковать свой ответ на этот вопрос.

Источник

7 ответов

Решение

Если вы просто бродите по коллекции, чтобы прочитать все значения, то нет разницы между использованием итератора или нового синтаксиса цикла for, поскольку новый синтаксис просто использует итератор под водой.

Однако, если вы подразумеваете под циклом старый цикл "c-style":

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

Тогда новый цикл for, или итератор, может быть намного более эффективным, в зависимости от базовой структуры данных. Причина этого в том, что для некоторых структур данных get(i) является операцией O(n), которая делает цикл операцией O (n2). Традиционный связанный список является примером такой структуры данных. Все итераторы имеют в качестве основного требования, что next() должна быть операция O(1), делая цикл O(n).

Чтобы убедиться, что итератор используется под водой новым синтаксисом цикла for, сравните сгенерированные байт-коды из следующих двух фрагментов Java. Первый цикл 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

И второе, итератор:

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

Как видите, сгенерированный байт-код фактически идентичен, поэтому использование любой формы не снижает производительности. Поэтому вы должны выбрать форму цикла, которая наиболее эстетически привлекательна для вас, для большинства людей это будет цикл for-each, поскольку в нем меньше стандартного кода.

Источник

Разница не в производительности, а в возможностях. При непосредственном использовании ссылки у вас есть больше возможностей явно использовать тип итератора (например, List.iterator() и List.listIterator(), хотя в большинстве случаев они возвращают одну и ту же реализацию). У вас также есть возможность ссылаться на Итератор в вашем цикле. Это позволяет вам делать такие вещи, как удаление элементов из вашей коллекции, не получая исключение ConcurrentModificationException.

например

Хорошо:

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();
     }
}

Это не так, поскольку это вызовет исключение одновременной модификации:

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

for(Object o : set){
     if(o meets some condition){
          set.remove(o);
     }
}
Источник

Чтобы расширить собственный ответ Пола, он продемонстрировал, что байт-код одинаков на этом конкретном компиляторе (предположительно, в javac от Sun?), Но разные компиляторы не гарантируют генерацию одного и того же байт-кода, верно? Чтобы увидеть разницу между ними, давайте сразу обратимся к источнику и проверим Спецификацию языка Java, в частности 14.14.2, "Улучшенный оператор for":

Улучшенный for утверждение эквивалентно основному for утверждение формы:

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

Другими словами, JLS требует, чтобы оба были эквивалентны. Теоретически это может означать незначительные различия в байт-коде, но в действительности расширенный цикл for необходим для:

  • Вызвать .iterator() метод
  • использование .hasNext()
  • Сделать локальную переменную доступной через .next()

Таким образом, другими словами, для всех практических целей байт-код будет идентичен или почти идентичен. Трудно представить какую-либо реализацию компилятора, которая привела бы к какой-либо значительной разнице между ними.

Источник

foreach Подземелье создает iterator вызывая hasNext() и вызывая next(), чтобы получить значение; Проблема с производительностью возникает только в том случае, если вы используете что-то, что реализует RandomomAccess.

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

Проблемы с производительностью цикла, основанного на итераторах, заключаются в следующем:

  1. выделение объекта, даже если список пуст Iterator<CustomObj> iter = customList.iterator(););
  2. iter.hasNext() во время каждой итерации цикла происходит виртуальный вызов invokeInterface (просмотрите все классы, затем выполните поиск таблицы методов перед переходом).
  3. реализация итератора должна сделать поиск по крайней мере 2 полей, чтобы сделать hasNext() вызовите цифру значение: #1 получить текущий счет #2 получить общий счет
  4. внутри цикла тела есть еще один виртуальный вызов invokeInterface iter.next (так: просмотрите все классы и выполните поиск таблицы методов перед переходом), а также выполните поиск по полям: #1 получить индекс и #2 получить ссылку на массив, чтобы выполнить смещение в нем (в каждой итерации).

Потенциальная оптимизация состоит в том, чтобы перейти к index iteration с поиском кэшированного размера:

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

Здесь мы имеем:

  1. один вызов виртуального метода invokeInterface customList.size() при первоначальном создании цикла для получения размера
  2. вызов метода get customList.get(x) во время тела для цикла, который является полем поиска в массиве, а затем может сделать смещение в массив

Мы сократили тонну вызовов методов, полевых поисков. Это вы не хотите делать с LinkedList или с чем-то, что не является RandomAccess коллекция объектов, в противном случае customList.get(x) собирается превратиться в нечто, что должно пересечь LinkedList на каждой итерации.

Это прекрасно, когда ты знаешь, что RandomAccess на основе списка коллекции.

Источник

foreach все равно использует итераторы под капотом. Это действительно просто синтаксический сахар.

Рассмотрим следующую программу:

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) {
        }
    }
}

Давайте скомпилируем это с javac Whatever.java,
И прочитайте разобранный байт-код main(), с помощью 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

Мы это видим foreach компилируется в программу, которая:

  • Создает итератор, используя List.iterator()
  • Если Iterator.hasNext(): вызывает Iterator.next() и продолжается кругом

Что касается того, "почему этот бесполезный цикл не оптимизируется из скомпилированного кода? Мы видим, что он ничего не делает с элементом списка": ну, вы можете написать свой итеративный код так, чтобы .iterator() имеет побочные эффекты, или так, чтобы .hasNext() имеет побочные эффекты или значимые последствия.

Вы можете легко представить, что итератор, представляющий прокручиваемый запрос из базы данных, может сделать что-то драматическое в .hasNext() (например, связаться с базой данных или закрыть курсор, потому что вы достигли конца набора результатов).

Таким образом, хотя мы можем доказать, что в теле цикла ничего не происходит... это дороже (неразрешимо?) Доказать, что ничего значимого / последовательного не происходит, когда мы выполняем итерацию. Компилятор должен оставить это пустое тело цикла в программе.

Лучшее, на что мы могли надеяться, это предупреждение компилятора. Интересно что javac -Xlint:all Whatever.java не предупреждает нас об этом пустом теле цикла. IntelliJ IDEA делает, хотя. По общему признанию я настроил IntelliJ для использования Eclipse Compiler, но это не может быть причиной этого.

Источник

Возможно, вам придется использовать итераторы, если вам нужно изменить коллекцию в вашем цикле. Первый подход бросит исключение.

for (String i : list) {
    System.out.println(i);
    list.remove(i); // throws exception
} 

Iterator it=list.iterator();
while (it.hasNext()){
    System.out.println(it.next());
    it.remove(); // valid here
}
Источник

Iterator - это интерфейс в платформе Java Collections, который предоставляет методы для обхода или перебора коллекции.

Итератор и цикл for действуют аналогично, когда ваш мотив состоит в том, чтобы просто пройти по коллекции, чтобы прочитать ее элементы.

for-each это всего лишь один из способов перебора коллекции.

Например:

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);
}

И цикл for-each может использоваться только для объектов, реализующих интерфейс итератора.

Теперь вернемся к случаю цикла for и итератора.

Разница возникает, когда вы пытаетесь изменить коллекцию. В этом случае итератор более эффективен из-за своего свойства fail-fast. то есть. он проверяет любые изменения в структуре базовой коллекции перед тем, как перейти к следующему элементу. Если будут найдены какие-либо изменения, будет выдано исключение ConcurrentModificationException.

(Примечание: эта функциональность итератора применима только в случае классов коллекций в пакете java.util. Она не применима для одновременных коллекций, поскольку они по своей природе отказоустойчивы)

Источник

Мы должны избегать использования традиционного цикла for при работе с коллекциями. Простая причина, по которой я приведу, состоит в том, что сложность цикла for имеет порядок O(sqr(n)), а сложность Iterator или даже расширенного цикла for равна O(n). Таким образом, это дает разницу в производительности. Просто возьмите список из примерно 1000 наименований и распечатайте его обоими способами. а также распечатать разницу во времени для исполнения. Вы можете увидеть разницу.

Источник
Другие вопросы по тегам