当前位置： 移动技术网 > IT编程>开发语言>Java > java遍历机制性能的比较详解

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

2019年07月19日  | 移动技术网IT编程  | 我要评论

缘由

近段时间在写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最好

使用建议

  • 在数据量不明确的情况下(可能1w,10w或其他)，建议使用iterator进行遍历
  • 在数据量明确且量级小的时候，优先使用foreach
  • 需要使用索引时，使用递增变量的开销比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最好

使用建议

  • 尽量使用iterator进行遍历
  • 需要使用索引时，使用递增变量的开销比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了，性能好，写起来也方便。

总结

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

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

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

您可能感兴趣的文章:

如对本文有疑问， 点击进行留言回复！！

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网