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

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

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, я буду публиковать свой ответ на этот вопрос.

Если вы просто бродите по коллекции, чтобы прочитать все значения, то нет разницы между использованием итератора или нового синтаксиса цикла 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, поскольку в нем меньше стандартного кода.

Разница не в производительности, а в возможностях. При непосредственном использовании ссылки у вас есть больше возможностей явно использовать тип итератора (например, 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 () и вызов следующей () , чтобы получить значение; Проблема с производительностью возникает только в том случае, если вы используете что-то, что реализует 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()при первоначальном создании цикла for для получения размера
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()
• If Iterator.hasNext(): вызывает Iterator.next()и продолжает цикл

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

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

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

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

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 наименований и распечатайте его обоими способами. а также распечатать разницу во времени для исполнения. Вы можете увидеть разницу.