Кофе-брейк #137. For loop или Foreach — что из них быстрее в Java? 8 эффективных способов перебора каждой записи в Java Map

Статья из группы Random

For loop или Foreach — что из них быстрее в Java?

Источник: Medium Когда я пару лет назад искал работу, один из вопросов, который мне задали на собеседовании, был о том, должны ли мы перебирать ArrayList, используя for или forEach? Кофе-брейк #137. For loop или Foreach — что из них быстрее в Java? 8 эффективных способов перебора каждой записи в Java Map - 1Споры о разнице в предпочтениях между forEach и for известны давно. У меня сложилось впечатление, что forEach быстрее. Но в итоге я понял, что ошибался. К вашему сведению, цикл forEach (или усовершенствованный цикл for), представленный в Java 1.5, избавляет от беспорядка и вероятности ошибки, полностью скрывая итератор или индексную переменную. Я считаю, что единственное практическое различие между for и forEach заключается в том, что в случае индексируемых объектов у нас нет доступа к index.

for(int i = 0; i < mylist.length; i++) {
 if(i < 5) {
 //do something
 } else {
 //do other stuff
 }
}
Однако мы можем создать отдельную индексную переменную типа int с помощью forEach. Например:

int index = -1;
for(int myint : mylist) {
 index++;
 if(index < 5) {
 //do something
 } else {
 //do other stuff
 }
}
Давайте напишем простой класс, в котором есть метод foreachTest(), который перебирает список, используя forEach.

import java.util.List;

public class ForEachTest {
	List<Integer> intList;
	
    public void foreachTest(){
        for(Integer i : intList){

        }
    }
}
Когда мы компилируем этот класс, компилятор внутренне преобразует код в реализацию итератора. Я декомпилировал скомпилированный код, выполнив javap -verbose IterateListTest.

 public void foreachTest();
    descriptor: ()V
    flags: ACC_PUBLIC
    Code:
      stack=1, locals=3, args_size=1
         0: aload_0
         1: getfield      #19                 // Field intList:Ljava/util/List;
         4: invokeinterface #21,  1           // InterfaceMethod java/util/List.iterator:()Ljava/util/Iterator;
         9: astore_2
        10: goto          23
        13: aload_2
        14: invokeinterface #27,  1           // InterfaceMethod java/util/Iterator.next:()Ljava/lang/Object;
        19: checkcast     #33                 // class java/lang/Integer
        22: astore_1
        23: aload_2
        24: invokeinterface #35,  1           // InterfaceMethod java/util/Iterator.hasNext:()Z
        29: ifne          13
        32: return
      LineNumberTable:
        line 9: 0
        line 12: 32
      LocalVariableTable:
        Start  Length  Slot  Name   Signature
            0      33     0  this   Lcom/greekykhs/springboot/ForEachTest;
      StackMapTable: number_of_entries = 2
        frame_type = 255 /* full_frame */
          offset_delta = 13
          locals = [ class com/greekykhs/springboot/ForEachTest, top, class java/util/Iterator ]
          stack = []
        frame_type = 9 /* same */
Из приведенного выше байт-кода мы видим:
  1. Команда getfield используется для получения переменных целых чисел.

  2. Вызов List.iterator для получения экземпляра итератора.

  3. Вызов iterator.hasNext. Если он возвращает true, следует вызвать метод iterator.next.

Проведем тест производительности. В основном методе IterateListTest я создал список и повторил его, используя циклы for и forEach.

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

public class IterateListTest {
	public static void main(String[] args) {
		List<Integer> mylist = new ArrayList<>();
        for (int i = 0; i < 1000000; i++) {
            mylist.add(i);
        }

        long forLoopStartTime = System.currentTimeMillis();
        for (int i = 0; i < mylist.size(); i++) {mylist.get(i);}

        long forLoopTraversalCost =System.currentTimeMillis()-forLoopStartTime;
        System.out.println("for loop traversal cost for ArrayList= "+ forLoopTraversalCost);

        long forEachStartTime = System.currentTimeMillis();
        for (Integer integer : mylist) {}

        long forEachTraversalCost =System.currentTimeMillis()-forEachStartTime;
        System.out.println("foreach traversal cost for ArrayList= "+ forEachTraversalCost);
	}
}
И вот результат: Кофе-брейк #137. For loop или Foreach — что из них быстрее в Java? 8 эффективных способов перебора каждой записи в Java Map - 2Как мы видим, производительность цикла for лучше, чем цикла forEach. Если же использовать LinkedList вместо ArrayList, то вы сможете увидеть, что производительность forEach лучше для LinkedList. ArrayList внутри использует массивы для хранения элементов. Поскольку массивы представляют собой непрерывные области памяти, временная сложность составляет O (1). Это объясняется тем, что данные извлекаются через индексы. LinkedList использует двунаправленный связанный список. Когда мы используем цикл for для реализации обхода, он каждый раз начинается с головного узла связанного списка, поэтому временная сложность равна O (n*n).

8 эффективных способов перебора каждой записи в Java Map

Источник: Medium На прошлой неделе стажерка спросила у меня, как выполнить итерацию Java Map. Я ответил, что поскольку это очень просто, ответ на этот вопрос всегда есть в Google. Спустя некоторое время она прислала мне адрес страницы в StackOverflow, и оказалось, что на эту проблему обращает внимание огромное количество людей. Поэтому я решил подробно остановиться на вопросе итерации и поделиться несколькими способами ее выполнения с вами. Кофе-брейк #137. For loop или Foreach — что из них быстрее в Java? 8 эффективных способов перебора каждой записи в Java Map - 3

1. Использование iterator и Map.Entry


@Test
public void test1_UsingWhileAndMapEntry(){
    long i = 0;
    Iterator<Map.Entry<Integer, Integer>> it = map.entrySet().iterator();
    while (it.hasNext()) {
        Map.Entry<Integer, Integer> pair = it.next();
        i += pair.getKey() + pair.getValue();
    }
    System.out.println(i);
}

2. Использование foreach и Map.Entry


@Test
public void test2_UsingForEachAndMapEntry(){
    long i = 0;
    for (Map.Entry<Integer, Integer> pair : map.entrySet()) {
        i += pair.getKey() + pair.getValue();
    }
    System.out.println(i);
}

3. Использование foreach из Java 8


@Test
public void test3_UsingForEachAndJava8(){
    final long[] i = {0};
    map.forEach((k, v) -> i[0] += k + v);
    System.out.println(i[0]);
}

4. Использование keySet и foreach


@Test
public void test4_UsingKeySetAndForEach(){
    long i = 0;
    for (Integer key : map.keySet()) {
        i += key + map.get(key);
    }
    System.out.println(i);
}

5. Использование keySet и iterator


@Test
public void test5_UsingKeySetAndIterator(){
    long i = 0;
    Iterator<Integer> it = map.keySet().iterator();
    while (it.hasNext()) {
        Integer key = it.next();
        i += key + map.get(key);
    }
    System.out.println(i);
}

6. Использование for и Map.Entry


@Test
public void test6_UsingForAndIterator(){
    long i = 0;
    for (Iterator<Map.Entry<Integer, Integer>> entries = map.entrySet().iterator(); entries.hasNext(); ) {
        Map.Entry<Integer, Integer> entry = entries.next();
        i += entry.getKey() + entry.getValue();
    }
    System.out.println(i);
}

7. Использование Java 8 Stream API


@Test 
public void test7_UsingJava8StreamApi(){ 
    System. out .println(map.entrySet().stream().mapToLong(e -> e.getKey() + e.getValue()).sum()); 
}

8. Параллельное использование Java 8 Stream API


@Test 
public void test8_UsingJava8StreamApiParallel(){ 
    System. out .println(map.entrySet().parallelStream().mapToLong(e -> e.getKey() + e.getValue()).sum()); 
}

Сравнение каждого способа по скорости:


public final static Integer SIZE = 1000000;
public Map<Integer, Integer> map = toMap();
public Map<Integer, Integer> toMap(){
    map = new HashMap<>(SIZE);
    for (int i = 0; i < SIZE; i++) {
        map.put(i, i);
    }
    return map;
}
Получаем: Кофе-брейк #137. For loop или Foreach — что из них быстрее в Java? 8 эффективных способов перебора каждой записи в Java Map - 4Кофе-брейк #137. For loop или Foreach — что из них быстрее в Java? 8 эффективных способов перебора каждой записи в Java Map - 5Кофе-брейк #137. For loop или Foreach — что из них быстрее в Java? 8 эффективных способов перебора каждой записи в Java Map - 6

Заключение

Из сравнения данных мы узнали, что метод 6 занимает больше всего времени, а метод 8 занимает больше времени, когда число небольшое, но занимает меньше всего времени, когда число значимо, потому что метод 8 выполняется одновременно. Интересно то, что порядок выполнения теста всегда for -> while -> foreach/stream, и я не знаю почему :(
Комментарии (1)
ЧТОБЫ ПОСМОТРЕТЬ ВСЕ КОММЕНТАРИИ ИЛИ ОСТАВИТЬ КОММЕНТАРИЙ,
ПЕРЕЙДИТЕ В ПОЛНУЮ ВЕРСИЮ
Anonymous #2934468 Уровень 28, Russian Federation
22 июня 2022
никогда не проверяйте производительность системным временем....