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

Question

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

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) внутри цикла, а не используете итератор.

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

Answer 1

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

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

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

Тогда новый цикл for или итератор может быть намного более эффективным, в зависимости от базовой структуры данных. Причина этого заключается в том, что для некоторых структур данных get(i) является операцией O (n), что делает цикл операцией O (n ² ). Традиционный связанный список является примером такой структуры данных. Все итераторы имеют в качестве основного требования, что 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, поскольку в нем меньше стандартного кода.

Answer 2

Разница не в производительности, а в возможностях. При непосредственном использовании ссылки у вас есть больше возможностей явно использовать тип итератора (например, 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);
     }
}

Answer 3

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

Расширенный оператор for эквивалентен базовому оператору for в форме:

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

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

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

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

Answer 4

Подгруппа 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 (так: просмотрите все классы и выполните поиск таблицы методов перед переходом), а также должен выполнить поиск полей: 2 получить ссылку на массив, чтобы сделать смещение в нем (в каждой итерации).

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

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

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

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

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

Это прекрасно, если вы знаете, что это любая коллекция списков на основе RandomAccess.

Answer 5

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() и продолжает цикл

---

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

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

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

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

Answer 6

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. Она не применима для одновременных коллекций, поскольку они по своей природе отказоустойчивы)

Answer 7

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