高效遍历Java容器

通过本文,你可以更深入的学习 Java 语言中 forEach 语法的知识,以及它和 C 语言形式的 for 循环、 Steam API 的对比。

简介

Java 程序员经常使用容器,比如 ArrayList 和 HashSet。Java 8 中的 lambda 语法和 steaming API 可以让我们更方便的使用容器。大部分情况下,我们仅仅处理几千个元素,也不会去考虑性能问题。但是,在一些极端场景下,如果我们需要遍历上百万个元素,性能问题就凸显出来了。

本文将采用 JMH 计算每块代码的运行时间。

forEach vs. C Style vs. Stream API

遍历是一个基本的功能。所有编程语言都提供了简单的语法,让程序员去遍历容器。Steam API 以一种非常直接的形式来遍历容器。

public List<Integer> streamSingleThread(BenchMarkState state){
    List<Integer> result = new ArrayList<>(state.testData.size());
    state.testData.stream().forEach(item -> {
        result.add(item);
    });
    return result;
}
public List<Integer> streamMultiThread(BenchMarkState state){
    List<Integer> result = new ArrayList<>(state.testData.size());
    state.testData.stream().parallel().forEach(item -> {
        result.add(item);
    });
    return result;
}

forEach 循环也很简单:

public List<Integer> forEach(BenchMarkState state){
  List<Integer> result = new ArrayList<>(state.testData.size());
  for(Integer item : state.testData){
    result.add(item);
  }
  return result;
}

C 语言形式的 for 循环啰嗦一些,不过依然很紧凑:

public List<Integer> forCStyle(BenchMarkState state){
  int size = state.testData.size();
  List<Integer> result = new ArrayList<>(size);
  for(int j = 0; j < size; j ++){
    result.add(state.testData.get(j));
  }
  return result;
}

以下是性能报告:

Benchmark                               Mode  Cnt   Score   Error  Units
TestLoopPerformance.forCStyle           avgt  200  18.068 ± 0.074  ms/op
TestLoopPerformance.forEach             avgt  200  30.566 ± 0.165  ms/op
TestLoopPerformance.streamMultiThread   avgt  200  79.433 ± 0.747  ms/op
TestLoopPerformance.streamSingleThread  avgt  200  37.779 ± 0.485  ms/op

使用 C 语言形式的 for 循环,JVM 每次仅仅增加一个数字,然后直接从内存里读出数据。这使得它非常迅速。但是 forEach 就大不一样,根据 StackOverFlow 的这篇回答(https://stackoverflow.com/questions/85190/how-does-the-java-for-each-loop-work/85206#85206),和 Oracle 的文章(https://docs.oracle.com/javase/1.5.0/docs/guide/language/foreach.html),JVM 需要把 forEach 转换成一个 iterator,然后每个元素都调用一次 hasNext() 方法。这就是 forEach 比 C 语言的形式慢一些的原因。

哪一个是遍历 Set 最高效的方法呢?

我们先定义测试数据集:

@State(Scope.Benchmark)
public static class BenchMarkState {
    @Setup(Level.Trial)
    public void doSetup() {
        for(int i = 0; i < 500000; i++){
            testData.add(Integer.valueOf(i));
        }
    }
    @TearDown(Level.Trial)
    public void doTearDown() {
        testData = new HashSet<>(500000);
    }
    public Set<Integer> testData = new HashSet<>(500000);
}

Java 中的 Set 也支持 Steam API 和 forEach 循环。参考之前的测试,如果我们把 Set 转换成 ArrayList,然后遍历 ArrayList,或许性能会好一些?

public List<Integer> forCStyle(BenchMarkState state){
    int size = state.testData.size();
    List<Integer> result = new ArrayList<>(size);
    Integer[] temp = (Integer[]) state.testData.toArray(new Integer[size]);
    for(int j = 0; j < size; j ++){
        result.add(temp[j]);
    }
    return result;
}

如果把 iterator 和 C 语言形式结合起来呢?

public List<Integer> forCStyleWithIteration(BenchMarkState state){
    int size = state.testData.size();
    List<Integer> result = new ArrayList<>(size);
    Iterator<Integer> iteration = state.testData.iterator();
        for(int j = 0; j < size; j ++){
            result.add(iteration.next());
        }
    return result;
}

或者,简单的遍历怎么样?

public List<Integer> forEach(BenchMarkState state){
    List<Integer> result = new ArrayList<>(state.testData.size());
    for(Integer item : state.testData) {
        result.add(item);
    }
    return result;
}

这个主意不错,不过它的效率也不高,因为初始化一个新的 ArrayList 同样需要消耗资源。

Benchmark                                   Mode  Cnt  Score   Error  Units
TestLoopPerformance.forCStyle               avgt  200  6.013 ± 0.108  ms/op
TestLoopPerformance.forCStyleWithIteration  avgt  200  4.281 ± 0.049  ms/op
TestLoopPerformance.forEach                 avgt  200  4.498 ± 0.026  ms/op

HashMap (使用 HashMap<E,Object> 的 HashSet) 不是为遍历所有元素设计的。遍历一个 HashMap 最快的方法是把 Iterator 和 C 语言形式结合起来,这样 JVM 就不会去调用 hasNext()。

结论

Foreach 和 Steam API 用来处理集合是很方便的。你可以更快的写代码。不过,如果你的系统很稳定,性能是一个主要的考量,你应该考虑一下重写你的循环。

如果觉得本文对你有帮助的话,欢迎大家随手点赞、转发。

原文发布于微信公众号 - Java团长(javatuanzhang)

原文发表时间:2018-08-19

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏林欣哲

HashMap解析

1173
来自专栏趣谈编程

可以管理时间的二叉堆

面试官:写一个堆排吧 我心想:堆排是什么鬼 理解堆排,首先要理解二叉堆。理解了二叉堆的“下沉”操作,基本上就可以理解堆排了。今天我们来看一看什么是堆,以及堆...

2176
来自专栏云霄雨霁

设计模式----迭代器模式

1860
来自专栏程序你好

Java集合循环性能比较

Java开发人员通常处理ArrayList和HashSet等集合。Java 8附带了lambda和streaming API,帮助我们轻松处理集合。在大多数情况...

1515
来自专栏数据魔术师

基础算法 | 数据结构之线性表&顺序表&链表(上)

各位,起床了起床了 小编又来送干货了 今天讲的是数据结构 全文字数:1185字 阅读时间:10分钟 数据结构?啥玩意? * 内容提要: *预备知识 *顺序表(S...

4216
来自专栏zaking's

用js来实现那些数据结构13(树01-二叉搜索树的实现)

  前一篇文章我们学会了第一个非顺序数据结构hashMap,那么这一篇我们来学学树,包括树的概念和一些相关的术语以及二叉搜索树的实现。唉?为什么不是树的实现,不...

45410
来自专栏计算机视觉与深度学习基础

Leetcode 228. Summary Ranges

Given a sorted integer array without duplicates, return the summary of its rang...

1998
来自专栏Android知识点总结

看得见的数据结构Android版之表的数组实现(数据结构篇)

841
来自专栏小狼的世界

Leetcode刷题记录:构建最大数二叉树

给定一个不含重复数字的数组,最大二叉树构建规则如下: 1、根是数组中最大的数字 2、左边的子树是最大数字左边的内容 3、右边的子树是最大数字右边的内容

1102
来自专栏数据结构与算法

2952 细胞分裂 2

2952 细胞分裂 2 时间限制: 2 s 空间限制: 16000 KB 题目等级 : 钻石 Diamond 题目描述 Description 著...

3566

扫码关注云+社区

领取腾讯云代金券