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

2023-08-22 12:06:05 62

缘由

近段时间在写leetcode的LemonadeChange时候，发现了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的比较

代码

publicclassTextArray{

privatestaticRandomrandom;

privatestaticListlist1;

privatestaticListlist2;

privatestaticListlist3;

publicstaticvoidexecute(){
random=newRandom();
initArray();
testForWith10Object();
testForEachWith10Object();
testIteratorWith10Object();
testForWith100Object();
testForEachWith100Object();
testIteratorWith100Object();
testForWith1000Object();
testForEachWith1000Object();
testIteratorWith1000Object();
}

privatestaticvoidtestForWith10Object(){
printFor(list1);
}

privatestaticvoidtestForWith100Object(){
printFor(list2);
}

privatestaticvoidtestForWith1000Object(){
printFor(list3);
}

privatestaticvoidtestForEachWith10Object(){
printForeach(list1);
}

privatestaticvoidtestForEachWith100Object(){
printForeach(list2);
}

privatestaticvoidtestForEachWith1000Object(){
printForeach(list3);
}

privatestaticvoidtestIteratorWith10Object(){
printIterator(list1);
}

privatestaticvoidtestIteratorWith100Object(){
printIterator(list2);
}

privatestaticvoidtestIteratorWith1000Object(){
printIterator(list3);
}

privatestaticvoidprintFor(Listlist){
System.out.println();
System.out.print("data:");
longstart=System.currentTimeMillis();
for(inti=0,length=list.size();ilist){
System.out.println();
System.out.print("data:");
longstart=System.currentTimeMillis();
for(inttemp:list){
System.out.print(temp+"");
}
System.out.println();
longend=System.currentTimeMillis();
System.out.println("foreachfor"+list.size()+":"+(end-start)+"ms");
}

privatestaticvoidprintIterator(Listlist){
System.out.println();
System.out.print("data:");
Iteratorit=list.iterator();
longstart=System.currentTimeMillis();
while(it.hasNext()){
System.out.print(it.next()+"");
}
System.out.println();
longend=System.currentTimeMillis();
System.out.println("iteratorfor"+list.size()+":"+(end-start)+"ms");
}

privatestaticvoidinitArray(){
list1=newArrayList<>();
list2=newArrayList<>();
list3=newArrayList<>();
for(inti=0;i<10;i++){
list1.add(random.nextInt());
}
for(inti=0;i<100;i++){
list2.add(random.nextInt());
}
for(inti=0;i<1000;i++){
list3.add(random.nextInt());
}
}
}

输出(忽略对元素的输出)

forfor10:1ms
foreachfor10:0ms
iteratorfor10:2ms

forfor100:5ms
foreachfor100:4ms
iteratorfor100:12ms

forfor1000:33ms
foreachfor1000:7ms
iteratorfor1000: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的比较

代码

publicclassTextLinkedList{

privatestaticRandomrandom;

privatestaticListlist1;

privatestaticListlist2;

privatestaticListlist3;

publicstaticvoidexecute(){
random=newRandom();
initList();
testForWith10Object();
testForEachWith10Object();
testIteratorWith10Object();
testForWith100Object();
testForEachWith100Object();
testIteratorWith100Object();
testForWith1000Object();
testForEachWith1000Object();
testIteratorWith1000Object();
}

privatestaticvoidtestForWith10Object(){
printFor(list1);
}

privatestaticvoidtestForEachWith10Object(){
printForeach(list1);
}

privatestaticvoidtestIteratorWith10Object(){
printIterator(list1);
}

privatestaticvoidtestForWith100Object(){
printFor(list2);
}

privatestaticvoidtestForEachWith100Object(){
printForeach(list2);
}

privatestaticvoidtestIteratorWith100Object(){
printIterator(list2);
}

privatestaticvoidtestForWith1000Object(){
printFor(list3);
}

privatestaticvoidtestForEachWith1000Object(){
printForeach(list3);
}

privatestaticvoidtestIteratorWith1000Object(){
printIterator(list3);
}

privatestaticvoidprintFor(Listlist){
System.out.println();
System.out.print("data:");
longstart=System.currentTimeMillis();
for(inti=0,size=list.size();ilist){
System.out.println();
System.out.print("data:");
longstart=System.currentTimeMillis();
for(inttemp:list){
System.out.print(temp+"");
}
System.out.println();
longend=System.currentTimeMillis();
System.out.println("foreachfor"+list.size()+":"+(end-start)+"ms");
}

privatestaticvoidprintIterator(Listlist){
System.out.println();
System.out.print("data:");
Iteratorit=list.iterator();
longstart=System.currentTimeMillis();
while(it.hasNext()){
System.out.print(it.next()+"");
}
System.out.println();
longend=System.currentTimeMillis();
System.out.println("iteratorfor"+list.size()+":"+(end-start)+"ms");
}


privatestaticvoidinitList(){
list1=newLinkedList<>();
list2=newLinkedList<>();
list3=newLinkedList<>();
for(inti=0;i<10;i++){
list1.add(random.nextInt());
}
for(inti=0;i<100;i++){
list2.add(random.nextInt());
}
for(inti=0;i<1000;i++){
list3.add(random.nextInt());
}
}
}

输出(忽略对元素的输出)

forfor10:0ms
foreachfor10:1ms
iteratorfor10:0ms

forfor100:1ms
foreachfor100:0ms
iteratorfor100:3ms

forfor1000:23ms
foreachfor1000:25ms
iteratorfor1000:4ms

	10	100	1000
for	0ms	1ms	23ms
forEach	1ms	0ms	25ms
Iterator	0ms	3ms	4ms

结论

foreach的性能最不稳定，for次之，Iterator最好

使用建议

尽量使用Iterator进行遍历
需要使用索引时，使用递增变量的开销比for的要小

HashSet的比较

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

代码

publicclassTextHash{

privatestaticRandomrandom;

privatestaticSetset1;

privatestaticSetset2;

privatestaticSetset3;

publicstaticvoidexecute(){
random=newRandom();
initHash();
testIteratorWith10Object();
testForEachWith10Object();
testIteratorWith100Object();
testForEachWith100Object();
testIteratorWith1000Object();
testForEachWith1000Object();
}

privatestaticvoidtestIteratorWith10Object(){
printIterator(set1);
}

privatestaticvoidtestForEachWith10Object(){
printForeach(set1);
}

privatestaticvoidtestIteratorWith100Object(){
printIterator(set2);
}

privatestaticvoidtestForEachWith100Object(){
printForeach(set2);
}

privatestaticvoidtestIteratorWith1000Object(){
printIterator(set3);
}

privatestaticvoidtestForEachWith1000Object(){
printForeach(set3);
}

privatestaticvoidinitHash(){
set1=newHashSet<>();
set2=newHashSet<>();
set3=newHashSet<>();
for(inti=0;i<10;i++){
set1.add(random.nextInt());
}
for(inti=0;i<100;i++){
set2.add(random.nextInt());
}
for(inti=0;i<1000;i++){
set3.add(random.nextInt());
}
}

privatestaticvoidprintIterator(Setdata){
System.out.println();
System.out.print("data:");
longstart=System.currentTimeMillis();
Iteratorit=data.iterator();
while(it.hasNext()){
System.out.print(it.next()+"");
}
System.out.println();
longend=System.currentTimeMillis();
System.out.println("iteratorfor"+data.size()+":"+(end-start)+"ms");
}

privatestaticvoidprintForeach(Setdata){
System.out.println();
System.out.print("data:");
longstart=System.currentTimeMillis();
for(inttemp:data){
System.out.print(temp+"");
}
System.out.println();
longend=System.currentTimeMillis();
System.out.println("foreachfor"+data.size()+":"+(end-start)+"ms");
}
}

输出(忽略对元素的输出)

iteratorfor10:0ms
foreachfor10:0ms

iteratorfor100:6ms
foreachfor100:0ms

iteratorfor1000:30ms
foreachfor1000:9ms

	10	100	1000
foreach	0ms	0ms	9ms
Iterator	0ms	6ms	30ms

结论

foreach性能遥遥领先于Iterator

使用建议

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

总结

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

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

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

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

热门推荐

随机推荐