JAVA遍历机制的性能的比较

mudiyouyou 发布于2019-08-16 18:01 / 3118人阅读

摘要：总结循环性能在三者的对比中总体落于下风，而且开销递增幅度较大。的性能在数组以及链表的表现都是最好的，应该是的设计者优化过了。

本文首发于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中元素也互不相同，所以我认为这个观点是正确的。

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

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

100

1000

元素都采用随机数生成

遍历进行操作都为输出当前元素的值

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

ArrayList的比较

代码

public class TextArray {

    private static Random random;

    private static List list1;

    private static List list2;

    private static List 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 list){
        System.out.println();
        System.out.print("data:");
        long start=System.currentTimeMillis();
        for(int i=0,length=list.size();i 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 list){
        System.out.println();
        System.out.print("data:");
        Iterator 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最好

使用建议

在数据量不明确的情况下(可能1w,10w或其他)，建议使用Iterator进行遍历

在数据量明确且量级小的时候，优先使用foreach

需要使用索引时，使用递增变量的开销比for的要小

LinkedList的比较

代码

public class TextLinkedList {

    private static Random random;

    private static List list1;

    private static List list2;

    private static List 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 list){
        System.out.println();
        System.out.print("data:");
        long start=System.currentTimeMillis();
        for(int i=0,size=list.size();i 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 list){
        System.out.println();
        System.out.print("data:");
        Iterator 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最好

使用建议

尽量使用Iterator进行遍历

需要使用索引时，使用递增变量的开销比for的要小

HashSet的比较

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

代码

public class TextHash {

    private static Random random;

    private static Set set1;

    private static Set set2;

    private static Set 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 data){
        System.out.println();
        System.out.print("data:");
        long start=System.currentTimeMillis();
        Iterator 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 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了，性能好，写起来也方便。

总结

for循环性能在三者的对比中总体落于下风，而且开销递增幅度较大。以后即使在需要使用索引时我宁愿使用递增变量也不会使用for了。

Iterator的性能在数组以及链表的表现都是最好的，应该是JAVA的设计者优化过了。在响应时间敏感的情况下(例如web响应)，优先考虑。

foreach的性能属于两者之间，写法简单，时间不敏感的情况下我会尽量选用。

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

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

列表项目

GPU服务器海外云主机 java的回调机制 java比较器的 java串的比较好 java比较3个数的

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/74894.html

带你了解集合世界的fail-fast机制和 CopyOnWriteArrayList 源码详解

摘要：体现的就是适配器模式。数组对象集合世界中的机制机制集合世界中比较常见的错误检测机制，防止在对集合进行遍历过程当中，出现意料之外的修改，会通过异常暴力的反应出来。而在增强循环中，集合遍历是通过进行的。前言学习情况记录时间：week 2 SMART子目标：Java 容器记录在学习Java容器知识点中，关于List的重点知识点。知识点概览：容器中的设计模式从Array...

young.li 2019-08-16 18:36 评论0 收藏0
NIO网络相关基础知识

摘要：操作系统是能够获取到事件操作完成的事件，基于回调函数机制和操作系统的操作控制实现事件检测机制。前面的文章NIO基础知识介绍了Java NIO的一些基本的类及功能说明，Java NIO是用来替换java 传统IO的，NIO的一些新的特性在网络交互方面会更加的明显。 Java 传统IO的弊端基于JVM来实现每个通道的轮询检查通道状态的方法是可行的，但仍然是有问题的，检查每个通道...

1fe1se 2019-08-15 14:30 评论0 收藏0
类的加载机制 - 收藏集 - 掘金

摘要：是现在广泛流行的代从开始学习系列之向提交代码掘金读完本文大概需要分钟。为了进行高效的垃圾回收，虚拟机把堆内存划分成新生代老年代和永久代中无永久代，使用实现三块区域。 React Native 开源项目 - 仿美团客户端 (Android、iOS 双适配) - Android - 掘金推荐 React Native 学习好项目，仿照美团客户端... 极简 GitHub 上手教程 - 工具...

Gilbertat 2019-08-14 18:40 评论0 收藏0