Flask接口签名sign原理与实例代码浅析
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
private static List
private static List
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
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 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 System.out.println(); System.out.print("data:"); 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 private static List private static List 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 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 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 System.out.println(); System.out.print("data:"); 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 private static Set private static Set 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 System.out.println(); System.out.print("data:"); long start=System.currentTimeMillis(); 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 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
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
System.out.println();
System.out.print("data:");
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
private static List
private static List
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
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 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 System.out.println(); System.out.print("data:"); 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 private static Set private static Set 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 System.out.println(); System.out.print("data:"); long start=System.currentTimeMillis(); 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 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
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
System.out.println();
System.out.print("data:");
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
private static Set
private static Set
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
System.out.println();
System.out.print("data:");
long start=System.currentTimeMillis();
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
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小时内删除侵权内容。
发表评论
暂时没有评论,来抢沙发吧~