乐趣区

JAVA遍历机制的性能的比较

jiezi

    本文首发于 cartoon 的博客
     转载请注明出处:https://cartoonyu.github.io/cartoon-blog/post/java/java%E9%81%8D%E5%8E%86%E6%9C%BA%E5%88%B6%E7%9A%84%E6%80%A7%E8%83%BD%E6%AF%94%E8%BE%83/

缘由

    近段时间在写 leetcode 的 Lemonade Change 时候，发现了 for 循环与 forEach 循环的耗时是不一致的，在提交记录上面差了一倍 ……
    平常开发绝大部分业务逻辑的实现都需要遍历机制的帮忙，虽说也有注意到各数据结构操作的性能比较，但是忽视了遍历机制性能的差异。原本前两天就开始动手写，拖延症 ……

正文

    现阶段我所知道 JAVA 遍历机制有三种

  • for 循环
  • forEach 循环
  • Iterator 循环

    JAVA 数据结构千千万，但是大部分都是对基础数据结构的封装，比较 HashMap 依赖于 Node 数组，LinkedList 底层是链表，ArrayList 对数组的再封装 …… 扯远了

    总结来说，JAVA 的基础数据结构，我觉得有两种

  • 数组
  • 链表

    如果是加上 Hash(Hash 的操作与数组以及链表不太一致)，就是三种

    因为平常开发大部分都优先选择包装后的数据结构，所以下面我会使用

  • ArrayList(包装后的数组)
  • LinkedList(包装后的链表)
  • HashSet(包装后的 Hash 类型数组)

    这三种数据结构在遍历机制不同的时候时间的差异

    可能有人对我为什么不对比 HashMap 呢，因为 JAVA 设计中，是先实现了 Map，再实现 Set。如果你有阅读过源码就会发现: 每个 Set 子类的实现中，都有一个序列化后的 Map 对应属性实现，而因为 Hash 的查找时间复杂度为 O(1)，得出 key 后查找 value 的时间大致是一致的，所以我不对比 HashMap。

题外话

    我在阅读《疯狂 JAVA》读到:JAVA 的设计者将 Map 的内部 entry 数组中的 value 设为 null 进而实现了 Set。因为我是以源码以及官方文档为准，具体我不清楚正确与否，但是因为 Hash 中的 key 互不相同，Set 中元素也互不相同，所以我认为这个观点是正确的。

    为了测试的公平性，我会采取以下的限定

  • 每种数据结构的大小都设置三种量级

    • 10
    • 100
    • 1000
  • 元素都采用随机数生成
  • 遍历进行操作都为输出当前元素的值

    注: 时间开销受本地环境的影响，可能测量值会出现变化，但是总体上比例是正确的

ArrayList 的比较

  • 代码

    public class TextArray {

    private static Random random;

    private static List<Integer> list1;

    private static List<Integer> list2;

    private static List<Integer> list3;

    public static void execute(){random=new Random();
        initArray();
        testForWith10Object();
        testForEachWith10Object();
        testIteratorWith10Object();
        testForWith100Object();
        testForEachWith100Object();
        testIteratorWith100Object();
        testForWith1000Object();
        testForEachWith1000Object();
        testIteratorWith1000Object();}

    private static void testForWith10Object(){printFor(list1);
    }

    private static void testForWith100Object(){printFor(list2);
    }

    private static void testForWith1000Object(){printFor(list3);
    }

    private static void testForEachWith10Object(){printForeach(list1);
    }

    private static void testForEachWith100Object(){printForeach(list2);
    }

    private static void testForEachWith1000Object(){printForeach(list3);
    }

    private static void testIteratorWith10Object() {printIterator(list1);
    }

    private static void testIteratorWith100Object() {printIterator(list2);
    }

    private static void testIteratorWith1000Object() {printIterator(list3);
    }

    private static void printFor(List<Integer> list){System.out.println();
        System.out.print("data:");
        long start=System.currentTimeMillis();
        for(int i=0,length=list.size();i<length;i++){System.out.print(list.get(i)+" ");
        }
        System.out.println();
        long end=System.currentTimeMillis();
        System.out.println("for for"+list.size()+":"+(end-start)+"ms");
    }

    private static void printForeach(List<Integer> list){System.out.println();
        System.out.print("data:");
        long start=System.currentTimeMillis();
        for(int temp:list){System.out.print(temp+" ");
        }
        System.out.println();
        long end=System.currentTimeMillis();
        System.out.println("foreach for"+list.size()+":"+(end-start)+"ms");
    }

    private static void printIterator(List<Integer> list){System.out.println();
        System.out.print("data:");
        Iterator<Integer> it=list.iterator();
        long start=System.currentTimeMillis();
        while(it.hasNext()){System.out.print(it.next()+" ");
        }
        System.out.println();
        long end=System.currentTimeMillis();
        System.out.println("iterator for"+list.size()+":"+(end-start)+"ms");
    }

    private static void initArray(){list1=new ArrayList<>();
        list2=new ArrayList<>();
        list3=new ArrayList<>();
        for(int i=0;i<10;i++){list1.add(random.nextInt());
        }
        for(int i=0;i<100;i++){list2.add(random.nextInt());
        }
        for(int i=0;i<1000;i++){list3.add(random.nextInt());
        }
    }
}

  • 输出(忽略对元素的输出)

    for for 10:1ms
foreach for 10:0ms
iterator for 10:2ms

for for 100:5ms
foreach for 100:4ms
iterator for 100:12ms

for for 1000:33ms
foreach for 1000:7ms
iterator for 1000:16ms
    10 100 1000
    for 1ms 5ms 33ms
    forEach 0ms 4ms 7ms
    Iterator 2ms 12ms 16ms
  • 结论

        for 的性能最不稳定，foreach 次之，Iterator 最好

  • 使用建议

    1. 在数据量不明确的情况下(可能 1w,10w 或其他)，建议使用 Iterator 进行遍历
    2. 在数据量明确且量级小的时候，优先使用 foreach
    3. 需要使用索引时，使用递增变量的开销比 for 的要小

LinkedList 的比较

  • 代码

    public class TextLinkedList {

    private static Random random;

    private static List<Integer> list1;

    private static List<Integer> list2;

    private static List<Integer> list3;

    public static void execute(){random=new Random();
        initList();
        testForWith10Object();
        testForEachWith10Object();
        testIteratorWith10Object();
        testForWith100Object();
        testForEachWith100Object();
        testIteratorWith100Object();
        testForWith1000Object();
        testForEachWith1000Object();
        testIteratorWith1000Object();}

    private static void testForWith10Object() {printFor(list1);
    }

    private static void testForEachWith10Object() {printForeach(list1);
    }

    private static void testIteratorWith10Object() {printIterator(list1);
    }

    private static void testForWith100Object() {printFor(list2);
    }

    private static void testForEachWith100Object() {printForeach(list2);
    }

    private static void testIteratorWith100Object() {printIterator(list2);
    }

    private static void testForWith1000Object() {printFor(list3);
    }

    private static void testForEachWith1000Object() {printForeach(list3);
    }

    private static void testIteratorWith1000Object() {printIterator(list3);
    }

    private static void printFor(List<Integer> list){System.out.println();
        System.out.print("data:");
        long start=System.currentTimeMillis();
        for(int i=0,size=list.size();i<size;i++){System.out.print(list.get(i));
        }
        System.out.println();
        long end=System.currentTimeMillis();
        System.out.println("for for"+list.size()+":"+(end-start)+"ms");
    }

    private static void printForeach(List<Integer> list){System.out.println();
        System.out.print("data:");
        long start=System.currentTimeMillis();
        for(int temp:list){System.out.print(temp+" ");
        }
        System.out.println();
        long end=System.currentTimeMillis();
        System.out.println("foreach for"+list.size()+":"+(end-start)+"ms");
    }

    private static void printIterator(List<Integer> list){System.out.println();
        System.out.print("data:");
        Iterator<Integer> it=list.iterator();
        long start=System.currentTimeMillis();
        while(it.hasNext()){System.out.print(it.next()+" ");
        }
        System.out.println();
        long end=System.currentTimeMillis();
        System.out.println("iterator for"+list.size()+":"+(end-start)+"ms");
    }


    private static void initList() {list1=new LinkedList<>();
        list2=new LinkedList<>();
        list3=new LinkedList<>();
        for(int i=0;i<10;i++){list1.add(random.nextInt());
        }
        for(int i=0;i<100;i++){list2.add(random.nextInt());
        }
        for(int i=0;i<1000;i++){list3.add(random.nextInt());
        }
    }
}

  • 输出(忽略对元素的输出)

    for for 10:0ms
foreach for 10:1ms
iterator for 10:0ms

for for 100:1ms
foreach for 100:0ms
iterator for 100:3ms

for for 1000:23ms
foreach for 1000:25ms
iterator for 1000:4ms
    10 100 1000
    for 0ms 1ms 23ms
    forEach 1ms 0ms 25ms
    Iterator 0ms 3ms 4ms
  • 结论

        foreach 的性能最不稳定，for 次之，Iterator 最好

  • 使用建议

    1. 尽量使用 Iterator 进行遍历
    2. 需要使用索引时，使用递增变量的开销比 for 的要小

HashSet 的比较

    注：因 Hash 遍历算法与其他类型不一致，所以取消了 for 循环的比较

  • 代码

    public class TextHash {

    private static Random random;

    private static Set<Integer> set1;

    private static Set<Integer> set2;

    private static Set<Integer> set3;

    public static void execute(){random=new Random();
        initHash();
        testIteratorWith10Object();
        testForEachWith10Object();
        testIteratorWith100Object();
        testForEachWith100Object();
        testIteratorWith1000Object();
        testForEachWith1000Object();}

    private static void testIteratorWith10Object() {printIterator(set1);
    }

    private static void testForEachWith10Object() {printForeach(set1);
    }

    private static void testIteratorWith100Object() {printIterator(set2);
    }

    private static void testForEachWith100Object() {printForeach(set2);
    }

    private static void testIteratorWith1000Object() {printIterator(set3);
    }

    private static void testForEachWith1000Object() {printForeach(set3);
    }

    private static void initHash() {set1=new HashSet<>();
        set2=new HashSet<>();
        set3=new HashSet<>();
        for(int i=0;i<10;i++){set1.add(random.nextInt());
        }
        for(int i=0;i<100;i++){set2.add(random.nextInt());
        }
        for(int i=0;i<1000;i++){set3.add(random.nextInt());
        }
    }

    private static void printIterator(Set<Integer> data){System.out.println();
        System.out.print("data:");
        long start=System.currentTimeMillis();
        Iterator<Integer> it=data.iterator();
        while (it.hasNext()){System.out.print(it.next()+" ");
        }
        System.out.println();
        long end=System.currentTimeMillis();
        System.out.println("iterator for"+data.size()+":"+(end-start)+"ms");
    }

    private static void printForeach(Set<Integer> data){System.out.println();
        System.out.print("data:");
        long start=System.currentTimeMillis();
        for(int temp:data){System.out.print(temp+" ");
        }
        System.out.println();
        long end=System.currentTimeMillis();
        System.out.println("foreach for"+data.size()+":"+(end-start)+"ms");
    }
}

  • 输出(忽略对元素的输出)

    iterator for 10:0ms
foreach for 10:0ms

iterator for 100:6ms
foreach for 100:0ms

iterator for 1000:30ms
foreach for 1000:9ms
    10 100 1000
    foreach 0ms 0ms 9ms
    Iterator 0ms 6ms 30ms
  • 结论

        foreach 性能遥遥领先于 Iterator

  • 使用建议

        以后就选 foreach 了，性能好，写起来也方便。

总结

  1. for 循环性能在三者的对比中总体落于下风，而且开销递增幅度较大。以后即使在需要使用索引时我宁愿使用递增变量也不会使用 for 了。
  2. Iterator 的性能在数组以及链表的表现都是最好的，应该是 JAVA 的设计者优化过了。在响应时间敏感的情况下(例如 web 响应)，优先考虑。
  3. foreach 的性能属于两者之间，写法简单，时间不敏感的情况下我会尽量选用。

    以上就是我对常见数据结构遍历机制的一点比较，虽然只是很初步，但是从中我也学到了很多东西，希望你们也有所收获。

    如果你喜欢本文章，可以收藏阅读，如果你对我的其他文章感兴趣，欢迎到我的博客查看。

  1. 列表项目
退出移动版