Kaffeepause Nr. 137. For-Schleife oder Foreach – welche ist in Java schneller? 8 effiziente Möglichkeiten, jeden Eintrag in einer Java-Map zu durchlaufen

For-Schleife oder Foreach – welche ist in Java schneller?

Quelle: Medium Als ich vor ein paar Jahren nach einem Job suchte, wurde mir in einem Interview unter anderem die Frage gestellt, ob wir mit for oder forEach über eine ArrayList iterieren sollten . Die Debatte über den Unterschied in den Präferenzen zwischen forEach und for gibt es schon seit langem. Ich hatte den Eindruck, dass forEach schneller ist. Aber am Ende wurde mir klar, dass ich falsch lag. Zu Ihrer Information: Die in Java 1.5 eingeführte forEach- Schleife (oder verbesserte for- Schleife ) beseitigt Unordnung und Fehlermöglichkeiten, indem sie den Iterator oder die Indexvariable vollständig ausblendet. Ich glaube, der einzige praktische Unterschied zwischen for und forEach besteht darin, dass wir bei indizierten Objekten keinen Zugriff auf den Index haben.

for(int i = 0; i < mylist.length; i++) {
 if(i < 5) {
 //do something
 } else {
 //do other stuff
 }
}

Wir können jedoch mit forEach eine separate Indexvariable vom Typ int erstellen . Zum Beispiel:

int index = -1;
for(int myint : mylist) {
 index++;
 if(index < 5) {
 //do something
 } else {
 //do other stuff
 }
}

Schreiben wir eine einfache Klasse mit einer foreachTest() -Methode, die mit forEach eine Liste durchläuft .

import java.util.List;

public class ForEachTest {
	List<Integer> intList;

    public void foreachTest(){
        for(Integer i : intList){

        }
    }
}

Wenn wir diese Klasse kompilieren, konvertiert der Compiler den Code intern in eine Iterator-Implementierung. Ich habe den kompilierten Code dekompiliert, indem ich javap -verbose IterateListTest ausgeführt habe .

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 */

Aus dem obigen Bytecode sehen wir:

1. Der Befehl getfield wird verwendet, um ganzzahlige Variablen abzurufen.

2. Rufen Sie List.iterator auf , um eine Iteratorinstanz zu erhalten.

3. Rufen Sie iterator.hasNext auf . Wenn es true zurückgibt, sollte die Methode iterator.next aufgerufen werden .

Lassen Sie uns einen Leistungstest durchführen. In der Hauptmethode „IterateListTest“ habe ich eine Liste erstellt und diese mithilfe von for- und forEach -Schleifen durchlaufen .

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

Und hier ist das Ergebnis: Wie wir sehen können, ist die Leistung der for- Schleife besser als die der forEach -Schleife . Wenn Sie LinkedList anstelle von ArrayList verwenden , können Sie sehen, dass die Leistung von forEach für LinkedList besser ist . ArrayList verwendet intern Arrays zum Speichern von Elementen. Da Arrays zusammenhängende Speicherbereiche sind, beträgt die Zeitkomplexität O(1). Dies liegt daran, dass Daten über Indizes abgerufen werden. LinkedList verwendet eine doppelt verknüpfte Liste. Wenn wir eine for- Schleife verwenden , um die Durchquerung zu implementieren, beginnt sie jedes Mal am Kopfknoten der verknüpften Liste, sodass die zeitliche Komplexität O(n*n) beträgt.

8 effiziente Möglichkeiten, jeden Eintrag in einer Java-Map zu durchlaufen

Quelle: Medium Letzte Woche fragte mich ein Praktikant, wie man eine Java Map iteriert. Ich habe geantwortet, dass die Antwort auf diese Frage immer bei Google zu finden sei, da sie sehr einfach sei. Nach einiger Zeit schickte sie mir die Adresse der Seite auf StackOverflow und es stellte sich heraus, dass eine große Anzahl von Leuten auf dieses Problem achtete. Aus diesem Grund habe ich beschlossen, mich mit dem Thema Iteration zu befassen und Ihnen verschiedene Möglichkeiten zur Umsetzung vorzustellen.

1. Verwendung von Iterator und 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. Verwendung von foreach und 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. Verwendung von foreach aus 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. Verwendung von keySet und foreach

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

5. Verwendung von KeySet und 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. Verwendung von for und 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. Verwendung der Java 8 Stream API

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

8. Parallele Nutzung der Java 8 Stream API

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

Vergleich der einzelnen Methoden hinsichtlich der Geschwindigkeit:

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

Wir bekommen:

Abschluss

Durch den Vergleich der Daten haben wir gelernt, dass Methode 6 die meiste Zeit und Methode 8 die meiste Zeit benötigt, wenn die Zahl klein ist, aber die kürzeste Zeit, wenn die Zahl signifikant ist, da Methode 8 gleichzeitig ausgeführt wird. Das Interessante ist, dass die Testausführungsreihenfolge immer für -> while -> foreach/stream gilt und ich nicht weiß warum :(