资讯

精准传达 • 有效沟通

从品牌网站建设到网络营销策划，从策略到执行的一站式服务

网站建设 >

查看其它板块

java遍历机制性能的比较详解

缘由

让客户满意是我们工作的目标，不断超越客户的期望值来自于我们对这个行业的热爱。我们立志把好的技术通过有效、简单的方式提供给客户，将通过不懈努力成为客户在信息化领域值得信任、有价值的长期合作伙伴，公司提供的服务项目有：申请域名、虚拟空间、营销软件、网站建设、岳池网站维护、网站推广。

近段时间在写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 list1;

  private static List list2;

  private static List list3;

  public static void execute(){
    random=new Random();
    initArray();
    testForWith20Object();
    testForEachWith20Object();
    testIteratorWith20Object();
    testForWith200Object();
    testForEachWith200Object();
    testIteratorWith200Object();
    testForWith2000Object();
    testForEachWith2000Object();
    testIteratorWith2000Object();
  }

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

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

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

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

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

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

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

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

  private static void testIteratorWith2000Object() {
    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

101001000
for1ms5ms33ms
forEach0ms4ms7ms
Iterator2ms12ms16ms

结论

    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();
    testForWith20Object();
    testForEachWith20Object();
    testIteratorWith20Object();
    testForWith200Object();
    testForEachWith200Object();
    testIteratorWith200Object();
    testForWith2000Object();
    testForEachWith2000Object();
    testIteratorWith2000Object();
  }

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

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

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

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

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

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

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

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

  private static void testIteratorWith2000Object() {
    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

101001000
for0ms1ms23ms
forEach1ms0ms25ms
Iterator0ms3ms4ms

结论

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();
    testIteratorWith20Object();
    testForEachWith20Object();
    testIteratorWith200Object();
    testForEachWith200Object();
    testIteratorWith2000Object();
    testForEachWith2000Object();
  }

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

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

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

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

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

  private static void testForEachWith2000Object() {
    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

101001000
foreach0ms0ms9ms
Iterator0ms6ms30ms

结论

foreach性能遥遥领先于Iterator

使用建议

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

总结

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

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

好了，以上就是这篇文章的全部内容了，希望本文的内容对大家的学习或者工作具有一定的参考学习价值，谢谢大家对创新互联的支持。


新闻标题：java遍历机制性能的比较详解
本文来源：http://cdkjz.cn/article/jeedpj.html
返回首页 了解更多建站资讯

相关资讯

多年建站经验

多一份参考，总有益处

联系快上网，免费获得专属《策划方案》及报价

咨询相关问题或预约面谈，可以通过以下方式与我们联系

大客户专线   成都：13518219792   座机：028-86922220

在线咨询 提交需求
友情链接 交换友情链接
四川平武网站建设成都网站设计成都品牌官网设计公司成都做网站注册域名四川成都seo网站优化绵阳梓潼做网站宜宾网站营销推广成都全网营销推广百度关键词排名

成都网站建设公司地址：成都市青羊区太升南路288号锦天国际A座10层 建设咨询028-86922220

成都快上网科技有限公司-四川网站建设设计公司 | 蜀ICP备19037934号 Copyright 2020,ALL Rights Reserved cdkjz.cn | 成都网站建设 | © Copyright 2020版权所有.

专家团队为您提供成都网站建设,成都网站设计,成都品牌网站设计,成都营销型网站制作等服务,成都建网站就找快上网！ | 成都网站建设哪家好？ | 网站建设地图