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<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:2msfor for 100:5ms
foreach for 100:4ms
iterator for 100:12msfor 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:0msfor for 100:1ms
foreach for 100:0ms
iterator for 100:3msfor 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:0msiterator for 100:6ms
foreach for 100:0msiterator 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的性能属于两者之间,写法简单,时间不敏感的情况下我会尽量选用。
以上就是我对常见数据结构遍历机制的一点比较,虽然只是很初步,但是从中我也学到了很多东西,希望你们也有所收获。
好了,以上就是这篇文章的全部内容了,希望本文的内容对大家的学习或者工作具有一定的参考学习价值,谢谢大家对的支持。