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

网友投稿 274 2023-01-05


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();

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 list){

System.out.println();

System.out.print("data:");

long start=System.currentTimeMillis();

for(int i=0,length=list.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 list){

System.out.println();

System.out.print("data:");

long start=System.currentTimeMillis();

for(int temp:list){

System.out.print(temp+" ");

}

System.out.println();

lohEXcGdng 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<10http://;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 list1;

private static List list2;

private static List 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 list){

System.out.println();

System.out.print("data:");

long start=System.currentTimeMillis();

for(int i=0,size=list.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 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

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 set1;

private static Set set2;

private static Set 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 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

10

100

1000

foreach

0ms

0ms

9ms

Iterator

0ms

6ms

30ms

结论

foreach性能遥遥领先于Iterator

使用建议

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

总结

for循环性能在三者的对比中总体落于下风,而且开销递增幅度较大。以后即使在需要使用索引时我宁愿使用递增变量也不会使用for了。

Iterator的性能在数组以及链表的表现都是最好的,应该是JAVA的设计者优化过了。在响应时间敏感的情况下(例如web响应),优先考虑。

foreach的性能属于两者之间,写法简单,时间不敏感的情况下我会尽量选用。

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

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

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 list){

System.out.println();

System.out.print("data:");

long start=System.currentTimeMillis();

for(int temp:list){

System.out.print(temp+" ");

}

System.out.println();

lohEXcGdng 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<10http://;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 list1;

private static List list2;

private static List 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 list){

System.out.println();

System.out.print("data:");

long start=System.currentTimeMillis();

for(int i=0,size=list.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 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

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 set1;

private static Set set2;

private static Set 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 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

10

100

1000

foreach

0ms

0ms

9ms

Iterator

0ms

6ms

30ms

结论

foreach性能遥遥领先于Iterator

使用建议

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

总结

for循环性能在三者的对比中总体落于下风,而且开销递增幅度较大。以后即使在需要使用索引时我宁愿使用递增变量也不会使用for了。

Iterator的性能在数组以及链表的表现都是最好的,应该是JAVA的设计者优化过了。在响应时间敏感的情况下(例如web响应),优先考虑。

foreach的性能属于两者之间,写法简单,时间不敏感的情况下我会尽量选用。

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

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

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 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

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 set1;

private static Set set2;

private static Set 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 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

10

100

1000

foreach

0ms

0ms

9ms

Iterator

0ms

6ms

30ms

结论

foreach性能遥遥领先于Iterator

使用建议

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

总结

for循环性能在三者的对比中总体落于下风,而且开销递增幅度较大。以后即使在需要使用索引时我宁愿使用递增变量也不会使用for了。

Iterator的性能在数组以及链表的表现都是最好的,应该是JAVA的设计者优化过了。在响应时间敏感的情况下(例如web响应),优先考虑。

foreach的性能属于两者之间,写法简单,时间不敏感的情况下我会尽量选用。

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

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


版权声明:本文内容由网络用户投稿,版权归原作者所有,本站不拥有其著作权,亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容,请联系我们jiasou666@gmail.com 处理,核实后本网站将在24小时内删除侵权内容。

上一篇:做接口测试需要多久(做接口测试需要多久时间)
下一篇:api接口自动化框架(java接口自动化框架有哪些)
相关文章

 发表评论

暂时没有评论,来抢沙发吧~