Какой из циклов в Java быстрее: for или for-each

В Java есть два основных способа обхода коллекций: простой цикл for и цикл for-each, появившийся в JDK 5. Задумывались ли вы когда-нибудь об их разнице с точки зрения производительности?

Реализация for-each

Цикл for-each — это синтаксический сахар. Компилятор преобразует for-each в вызов итератора. Давайте рассмотрим следующий пример:

public class TestForeach {     List<Integer> integers;     public void testForeach(){         for(Integer i : integers){          }     } }

Скомпилируем и посмотрим на байткод с помощью команды javap -verbose Testforeach.

public void testForeach();     descriptor: ()V     flags: ACC_PUBLIC     Code:       stack=1, locals=3, args_size=1          0: aload_0          1: getfield      #2                  // Field integers:Ljava/util/List;          4: invokeinterface #3,  1            // InterfaceMethod java/util/List.iterator:()Ljava/util/Iterator;          9: astore_1         10: aload_1         11: invokeinterface #4,  1            // InterfaceMethod java/util/Iterator.hasNext:()Z         16: ifeq          32         19: aload_1         20: invokeinterface #5,  1            // InterfaceMethod java/util/Iterator.next:()Ljava/lang/Object;         25: checkcast     #6                  // class java/lang/Integer         28: astore_2         29: goto          10         32: return       LineNumberTable:         line 11: 0         line 13: 29         line 14: 32       LocalVariableTable:         Start  Length  Slot  Name   Signature            29       0     2     i   Ljava/lang/Integer;             0      33     0  this   Ltest/TestForeach; }

Общий смысл этого байткода заключается в использовании команды getfield для получения переменной integers и вызова List.iterator для получения экземпляра итератора, у которого вызывается метод hasNext. Если hasNext возвращает true, то вызывается метод Iterator.next.

Тест производительности

Теперь давайте сравним производительность циклов for и for-each.

public class ForLoopTest {      public static void main(String[] args) {         List<Integer> arrayList = new ArrayList<>();         for (int i = 0; i < 10000000; i++) {             arrayList.add(i);         }          long arrayListStartTime = System.currentTimeMillis();         for (int i = 0; i < arrayList.size(); i++) {             arrayList.get(i);         }          long arrayListCost =System.currentTimeMillis()-arrayListStartTime;         System.out.println("ArrayList for loop traversal cost: "+ arrayListCost);          long arrayListForeachStartTime = System.currentTimeMillis();         for (Integer integer : arrayList) {          }          long arrayListForeachCost =System.currentTimeMillis()-arrayListForeachStartTime;         System.out.println("ArrayList foreach traversal cost: "+ arrayListForeachCost);

Результаты приведены в таблице ниже.

Наверняка вы видите вполне ожидаемые результаты. Для ArrayList производительность for лучше, чем for-each. Можно ли объявить for победителем? Нет. Давайте заменим ArrayList на LinkedList и повторим эксперимент.

Результаты будут несколько другими.

Анализ результатов

Почему цикл for работает с ArrayList быстрее, чем с LinkedList? Все дело во внутреннем устройстве ArrayList и LinkedList.

В ArrayList элементы хранятся в массиве. Массив представляет собой непрерывную область памяти с доступом к элементам по индексу. Временная сложность — O(1).

LinkedList представляет собой двусвязный список. Получение элемента по индексу на каждой итерации for происходит путем обхода списка с головы. Временная сложность — O(n*n).

Заключение

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

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

3. Используя паттерн «итератор», циклу for-each не нужно заботиться о конкретной реализации коллекции. При необходимости можно легко изменить реализацию коллекции без модификации кода.

Совсем скоро состоится открытый урок, на котором начинающие java разработчики смогут усвоить основы ООП в java. На этом уроке поговорим о конструкторах, создании объектов, состоянии объектов, полях класса, методах, поведении объектов, интерфейсах, контракте взаимодействия. Регистрация доступна по ссылке.