Coffee break #137. Para sa loop o Foreach - alin ang mas mabilis sa Java? 8 Mahusay na Paraan para Mag-loop sa Bawat Entry sa isang Java Map

Para sa loop o Foreach - alin ang mas mabilis sa Java?

Pinagmulan: Medium Noong naghahanap ako ng trabaho ilang taon na ang nakalilipas, isa sa mga tanong sa akin sa isang panayam ay kung dapat ba tayong umulit sa isang ArrayList gamit ang for o forEach ? Ang debate tungkol sa pagkakaiba sa mga kagustuhan sa pagitan ng forEach at for ay matagal nang umiikot. Nasa ilalim ako ng impresyon na ang forEach ay mas mabilis. Pero in the end narealize ko na mali pala ako. FYI, ang forEach loop (o pinahusay para sa loop ) na ipinakilala sa Java 1.5 ay nag-aalis ng kalat at posibilidad ng error sa pamamagitan ng pagtatago sa iterator o index variable nang buo. Naniniwala ako na ang tanging praktikal na pagkakaiba sa pagitan ng for at forEach ay na sa kaso ng mga na-index na bagay, wala kaming access sa index.

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

Gayunpaman, maaari tayong lumikha ng isang hiwalay na variable ng index ng uri int gamit ang forEach . Halimbawa:

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

Sumulat tayo ng isang simpleng klase na mayroong paraang foreachTest() na umuulit sa isang listahan gamit ang forEach .

import java.util.List;

public class ForEachTest {
	List<Integer> intList;

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

        }
    }
}

Kapag pinagsama-sama namin ang klase na ito, panloob na kino-convert ng compiler ang code sa isang pagpapatupad ng iterator. Na-decompile ko ang pinagsama-samang code sa pamamagitan ng pagpapatakbo ng 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 */

Mula sa bytecode sa itaas nakikita natin:

1. Ang getfield command ay ginagamit upang makakuha ng mga variable na integer.

2. Tumawag sa List.iterator upang makakuha ng isang instance ng iterator.

3. Tumawag sa iterator.hasNext . Kung ito ay nagbabalik ng true, ang iterator.next na paraan ay dapat na tinatawag na .

Magsagawa tayo ng pagsubok sa pagganap. Sa pangunahing paraan ng IterateListTest , gumawa ako ng isang listahan at inulit ito gamit ang para sa at para sa bawat mga loop .

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

At narito ang resulta: Gaya ng nakikita natin, ang pagganap ng for loop ay mas mahusay kaysa sa forEach loop . Kung gumagamit ka ng LinkedList sa halip na ArrayList , makikita mo na ang forEach performance ay mas mahusay para sa LinkedList . Ang ArrayList ay panloob na gumagamit ng mga array upang mag-imbak ng mga elemento. Dahil ang mga array ay magkadikit na mga rehiyon ng memorya, ang pagiging kumplikado ng oras ay O(1). Ito ay dahil ang data ay kinukuha sa pamamagitan ng mga index. Gumagamit ang LinkedList ng dobleng naka-link na listahan. Kapag gumamit kami ng for loop upang ipatupad ang traversal, magsisimula ito sa head node ng naka-link na listahan sa bawat oras, kaya ang pagiging kumplikado ng oras ay O(n*n).

8 Mahusay na Paraan para Mag-loop sa Bawat Entry sa isang Java Map

Source: Medium Noong nakaraang linggo, tinanong ako ng isang intern kung paano umulit ng Java Map. Sumagot ako na dahil ito ay napaka-simple, ang sagot sa tanong na ito ay palaging nasa Google. Pagkaraan ng ilang oras, ipinadala niya sa akin ang address ng pahina sa StackOverflow, at lumabas na napakalaking bilang ng mga tao ang nagbigay pansin sa problemang ito. Samakatuwid, nagpasya akong mag-isip tungkol sa isyu ng pag-ulit at ibahagi ang ilang mga paraan upang gawin ito sa iyo.

1. Gamit ang iterator at 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. Gamit ang foreach at 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. Paggamit ng foreach mula sa 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. Gamit ang keySet at foreach

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

5. Gamit ang keySet at 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. Paggamit para sa at 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. Paggamit ng Java 8 Stream API

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

8. Parallel na paggamit ng Java 8 Stream API

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

Paghahambing ng bawat pamamaraan sa mga tuntunin ng bilis:

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

Nakukuha namin:

Konklusyon

Mula sa paghahambing ng data, nalaman namin na ang paraan 6 ay tumatagal ng pinakamaraming oras at ang paraan 8 ay tumatagal ng pinakamaraming oras kapag ang bilang ay maliit, ngunit tumatagal ng pinakamaliit na oras kapag ang numero ay makabuluhan dahil ang paraan 8 ay isinasagawa nang sabay-sabay. Ang kagiliw-giliw na bagay ay ang order ng pagpapatupad ng pagsubok ay palaging para sa -> habang -> foreach/stream at hindi ko alam kung bakit :(