如有錯誤歡迎指正!
今天(9月7日)上午《計算機作業系統》課上老師提出一個問題:
按行遍歷和按列遍歷哪一個運行時間更短一些?
我周圍的同學大部分認為按行遍歷更快一些,可能是受到C語言寫for回圈時習慣于先回圈行再回圈列的影響,
之前看過一篇文章,里面提到了按行遍歷和按列遍歷哪個快取決于使用的語言型別,同時,在做深圳杯大作業的時候,通過查閱資料偶然發現了MATLAB中優化代碼運行時間的其中一個方法是for回圈要用按列遍歷,下面用程式檢驗一下,
v1:C語言版本,分別輸出不同大小矩陣、不同遍歷方式下的運行時間,
#include<stdio.h>
#include<time.h>
int a[20005][20005]={0};
int main()
{
double s1,s2;
int i,j;
s1=clock();
for(i=1;i<=10;i++){
for(j=1;j<=10;j++){
a[i][j]=1;
}
}
s2=clock();
printf("10*10陣列按行遍歷運行時間:%.12f s\n",(s2-s1)/CLOCKS_PER_SEC);
s1=clock();
for(i=1;i<=10;i++){
for(j=1;j<=10;j++){
a[j][i]=1;
}
}
s2=clock();
printf("10*10陣列按列遍歷運行時間:%.12f s\n\n",(s2-s1)/CLOCKS_PER_SEC);
s1=clock();
for(i=1;i<=100;i++){
for(j=1;j<=100;j++){
a[i][j]=1;
}
}
s2=clock();
printf("100*100陣列按行遍歷運行時間:%.12f s\n",(s2-s1)/CLOCKS_PER_SEC);
s1=clock();
for(i=1;i<=100;i++){
for(j=1;j<=100;j++){
a[j][i]=1;
}
}
s2=clock();
printf("100*100陣列按列遍歷運行時間:%.12f s\n\n",(s2-s1)/CLOCKS_PER_SEC);
s1=clock();
for(i=1;i<=500;i++){
for(j=1;j<=500;j++){
a[i][j]=1;
}
}
s2=clock();
printf("500*500陣列按行遍歷運行時間:%.12f s\n",(s2-s1)/CLOCKS_PER_SEC);
s1=clock();
for(i=1;i<=500;i++){
for(j=1;j<=500;j++){
a[j][i]=1;
}
}
s2=clock();
printf("500*500陣列按列遍歷運行時間:%.12f s\n\n",(s2-s1)/CLOCKS_PER_SEC);
s1=clock();
for(i=1;i<=1000;i++){
for(j=1;j<=1000;j++){
a[i][j]=1;
}
}
s2=clock();
printf("1000*1000陣列按行遍歷運行時間:%.12f s\n",(s2-s1)/CLOCKS_PER_SEC);
s1=clock();
for(i=1;i<=1000;i++){
for(j=1;j<=1000;j++){
a[j][i]=1;
}
}
s2=clock();
printf("1000*1000陣列按列遍歷運行時間:%.12f s\n\n",(s2-s1)/CLOCKS_PER_SEC);
s1=clock();
for(i=1;i<=2000;i++){
for(j=1;j<=2000;j++){
a[i][j]=1;
}
}
s2=clock();
printf("2000*2000陣列按行遍歷運行時間:%.12f s\n",(s2-s1)/CLOCKS_PER_SEC);
s1=clock();
for(i=1;i<=2000;i++){
for(j=1;j<=2000;j++){
a[j][i]=1;
}
}
s2=clock();
printf("2000*2000陣列按列遍歷運行時間:%.12f s\n\n",(s2-s1)/CLOCKS_PER_SEC);
s1=clock();
for(i=1;i<=3000;i++){
for(j=1;j<=3000;j++){
a[i][j]=1;
}
}
s2=clock();
printf("3000*3000陣列按行遍歷運行時間:%.12f s\n",(s2-s1)/CLOCKS_PER_SEC);
s1=clock();
for(i=1;i<=3000;i++){
for(j=1;j<=3000;j++){
a[j][i]=1;
}
}
s2=clock();
printf("3000*3000陣列按列遍歷運行時間:%.12f s\n\n",(s2-s1)/CLOCKS_PER_SEC);
s1=clock();
for(i=1;i<=4000;i++){
for(j=1;j<=4000;j++){
a[i][j]=1;
}
}
s2=clock();
printf("4000*4000陣列按行遍歷運行時間:%.12f s\n",(s2-s1)/CLOCKS_PER_SEC);
s1=clock();
for(i=1;i<=4000;i++){
for(j=1;j<=4000;j++){
a[j][i]=1;
}
}
s2=clock();
printf("4000*4000陣列按列遍歷運行時間:%.12f s\n\n",(s2-s1)/CLOCKS_PER_SEC);
s1=clock();
for(i=1;i<=5000;i++){
for(j=1;j<=5000;j++){
a[i][j]=1;
}
}
s2=clock();
printf("5000*5000陣列按行遍歷運行時間:%.12f s\n",(s2-s1)/CLOCKS_PER_SEC);
s1=clock();
for(i=1;i<=5000;i++){
for(j=1;j<=5000;j++){
a[j][i]=1;
}
}
s2=clock();
printf("5000*5000陣列按列遍歷運行時間:%.12f s\n\n",(s2-s1)/CLOCKS_PER_SEC);
s1=clock();
for(i=1;i<=6000;i++){
for(j=1;j<=6000;j++){
a[i][j]=1;
}
}
s2=clock();
printf("6000*6000陣列按行遍歷運行時間:%.12f s\n",(s2-s1)/CLOCKS_PER_SEC);
s1=clock();
for(i=1;i<=6000;i++){
for(j=1;j<=6000;j++){
a[j][i]=1;
}
}
s2=clock();
printf("6000*6000陣列按列遍歷運行時間:%.12f s\n\n",(s2-s1)/CLOCKS_PER_SEC);
s1=clock();
for(i=1;i<=7000;i++){
for(j=1;j<=7000;j++){
a[i][j]=1;
}
}
s2=clock();
printf("7000*7000陣列按行遍歷運行時間:%.12f s\n",(s2-s1)/CLOCKS_PER_SEC);
s1=clock();
for(i=1;i<=7000;i++){
for(j=1;j<=7000;j++){
a[j][i]=1;
}
}
s2=clock();
printf("7000*7000陣列按列遍歷運行時間:%.12f s\n\n",(s2-s1)/CLOCKS_PER_SEC);
s1=clock();
for(i=1;i<=8000;i++){
for(j=1;j<=8000;j++){
a[i][j]=1;
}
}
s2=clock();
printf("8000*8000陣列按行遍歷運行時間:%.12f s\n",(s2-s1)/CLOCKS_PER_SEC);
s1=clock();
for(i=1;i<=8000;i++){
for(j=1;j<=8000;j++){
a[j][i]=1;
}
}
s2=clock();
printf("8000*8000陣列按列遍歷運行時間:%.12f s\n\n",(s2-s1)/CLOCKS_PER_SEC);
s1=clock();
for(i=1;i<=9000;i++){
for(j=1;j<=9000;j++){
a[i][j]=1;
}
}
s2=clock();
printf("9000*9000陣列按行遍歷運行時間:%.12f s\n",(s2-s1)/CLOCKS_PER_SEC);
s1=clock();
for(i=1;i<=9000;i++){
for(j=1;j<=9000;j++){
a[j][i]=1;
}
}
s2=clock();
printf("9000*9000陣列按列遍歷運行時間:%.12f s\n\n",(s2-s1)/CLOCKS_PER_SEC);
s1=clock();
for(i=1;i<=10000;i++){
for(j=1;j<=10000;j++){
a[i][j]=1;
}
}
s2=clock();
printf("10000*10000陣列按行遍歷運行時間:%.12f s\n",(s2-s1)/CLOCKS_PER_SEC);
s1=clock();
for(i=1;i<=10000;i++){
for(j=1;j<=10000;j++){
a[j][i]=1;
}
}
s2=clock();
printf("10000*10000陣列按列遍歷運行時間:%.12f s\n\n",(s2-s1)/CLOCKS_PER_SEC);
s1=clock();
for(i=1;i<=12000;i++){
for(j=1;j<=12000;j++){
a[i][j]=1;
}
}
s2=clock();
printf("12000*12000陣列按行遍歷運行時間:%.12f s\n",(s2-s1)/CLOCKS_PER_SEC);
s1=clock();
for(i=1;i<=12000;i++){
for(j=1;j<=12000;j++){
a[j][i]=1;
}
}
s2=clock();
printf("12000*12000陣列按列遍歷運行時間:%.12f s\n\n",(s2-s1)/CLOCKS_PER_SEC);
s1=clock();
for(i=1;i<=14000;i++){
for(j=1;j<=14000;j++){
a[i][j]=1;
}
}
s2=clock();
printf("14000*14000陣列按行遍歷運行時間:%.12f s\n",(s2-s1)/CLOCKS_PER_SEC);
s1=clock();
for(i=1;i<=14000;i++){
for(j=1;j<=14000;j++){
a[j][i]=1;
}
}
s2=clock();
printf("14000*14000陣列按列遍歷運行時間:%.12f s\n\n",(s2-s1)/CLOCKS_PER_SEC);
s1=clock();
for(i=1;i<=16000;i++){
for(j=1;j<=16000;j++){
a[i][j]=1;
}
}
s2=clock();
printf("16000*16000陣列按行遍歷運行時間:%.12f s\n",(s2-s1)/CLOCKS_PER_SEC);
s1=clock();
for(i=1;i<=16000;i++){
for(j=1;j<=16000;j++){
a[j][i]=1;
}
}
s2=clock();
printf("16000*16000陣列按列遍歷運行時間:%.12f s\n\n",(s2-s1)/CLOCKS_PER_SEC);
s1=clock();
for(i=1;i<=18000;i++){
for(j=1;j<=18000;j++){
a[i][j]=1;
}
}
s2=clock();
printf("18000*18000陣列按行遍歷運行時間:%.12f s\n",(s2-s1)/CLOCKS_PER_SEC);
s1=clock();
for(i=1;i<=18000;i++){
for(j=1;j<=18000;j++){
a[j][i]=1;
}
}
s2=clock();
printf("18000*18000陣列按列遍歷運行時間:%.12f s\n\n",(s2-s1)/CLOCKS_PER_SEC);
s1=clock();
for(i=1;i<=20000;i++){
for(j=1;j<=20000;j++){
a[i][j]=1;
}
}
s2=clock();
printf("20000*20000陣列按行遍歷運行時間:%.12f s\n",(s2-s1)/CLOCKS_PER_SEC);
s1=clock();
for(i=1;i<=20000;i++){
for(j=1;j<=20000;j++){
a[j][i]=1;
}
}
s2=clock();
printf("20000*20000陣列按列遍歷運行時間:%.12f s\n\n",(s2-s1)/CLOCKS_PER_SEC);
return 0;
}
運行結果:
10*10陣列按行遍歷運行時間:0.000000000000 s
10*10陣列按列遍歷運行時間:0.000000000000 s
100*100陣列按行遍歷運行時間:0.000000000000 s
100*100陣列按列遍歷運行時間:0.000000000000 s
500*500陣列按行遍歷運行時間:0.002000000000 s
500*500陣列按列遍歷運行時間:0.000000000000 s
1000*1000陣列按行遍歷運行時間:0.001000000000 s
1000*1000陣列按列遍歷運行時間:0.003000000000 s
2000*2000陣列按行遍歷運行時間:0.008000000000 s
2000*2000陣列按列遍歷運行時間:0.023000000000 s
3000*3000陣列按行遍歷運行時間:0.011000000000 s
3000*3000陣列按列遍歷運行時間:0.064000000000 s
4000*4000陣列按行遍歷運行時間:0.018000000000 s
4000*4000陣列按列遍歷運行時間:0.117000000000 s
5000*5000陣列按行遍歷運行時間:0.025000000000 s
5000*5000陣列按列遍歷運行時間:0.181000000000 s
6000*6000陣列按行遍歷運行時間:0.037000000000 s
6000*6000陣列按列遍歷運行時間:0.263000000000 s
7000*7000陣列按行遍歷運行時間:0.042000000000 s
7000*7000陣列按列遍歷運行時間:0.372000000000 s
8000*8000陣列按行遍歷運行時間:0.055000000000 s
8000*8000陣列按列遍歷運行時間:0.469000000000 s
9000*9000陣列按行遍歷運行時間:0.067000000000 s
9000*9000陣列按列遍歷運行時間:0.602000000000 s
10000*10000陣列按行遍歷運行時間:0.074000000000 s
10000*10000陣列按列遍歷運行時間:0.728000000000 s
12000*12000陣列按行遍歷運行時間:0.127000000000 s
12000*12000陣列按列遍歷運行時間:1.052000000000 s
14000*14000陣列按行遍歷運行時間:0.176000000000 s
14000*14000陣列按列遍歷運行時間:1.429000000000 s
16000*16000陣列按行遍歷運行時間:0.203000000000 s
16000*16000陣列按列遍歷運行時間:1.870000000000 s
18000*18000陣列按行遍歷運行時間:0.251000000000 s
18000*18000陣列按列遍歷運行時間:2.383000000000 s
20000*20000陣列按行遍歷運行時間:0.274000000000 s
20000*20000陣列按列遍歷運行時間:2.927000000000 s
當陣列大小較小時,按行遍歷和按列遍歷的時間差不多;隨著陣列大小的增大,二者的運行時間均有增長,但是增長幅度不同,顯然按行遍歷的增長幅度要小于按列遍歷,當陣列大小在10000*10000以上時,按列遍歷的運行時間超過1秒,在OJ中提交會TLE,而按行遍歷的運行時間仍在可接受范圍內,
v2:MATLAB R2019b版本,分別輸出不同大小矩陣、不同遍歷方式下的運行時間,
a=zeros(20000,20000);
%10*10
disp('10*10按行遍歷:')
tic
for i=1:10
for j=1:10
a(i,j)=1;
end
end
toc
disp('10*10按列遍歷:')
tic
for j=1:10
for i=1:10
a(i,j)=1;
end
end
toc
%100*100
disp('100*100按行遍歷:')
tic
for i=1:100
for j=1:100
a(i,j)=1;
end
end
toc
disp('100*100按列遍歷:')
tic
for j=1:100
for i=1:100
a(i,j)=1;
end
end
toc
%500*500
disp('500*500按行遍歷:')
tic
for i=1:500
for j=1:500
a(i,j)=1;
end
end
toc
disp('500*500按列遍歷:')
tic
for j=1:500
for i=1:500
a(i,j)=1;
end
end
toc
%1000*1000
disp('1000*1000按行遍歷:')
tic
for i=1:1000
for j=1:1000
a(i,j)=1;
end
end
toc
disp('1000*1000按列遍歷:')
tic
for j=1:1000
for i=1:1000
a(i,j)=1;
end
end
toc
%2000*2000
disp('2000*2000按行遍歷:')
tic
for i=1:2000
for j=1:2000
a(i,j)=1;
end
end
toc
disp('2000*2000按列遍歷:')
tic
for j=1:2000
for i=1:2000
a(i,j)=1;
end
end
toc
%3000*3000
disp('3000*3000按行遍歷:')
tic
for i=1:3000
for j=1:3000
a(i,j)=1;
end
end
toc
disp('3000*3000按列遍歷:')
tic
for j=1:3000
for i=1:3000
a(i,j)=1;
end
end
toc
%4000*4000
disp('4000*4000按行遍歷:')
tic
for i=1:4000
for j=1:4000
a(i,j)=1;
end
end
toc
disp('4000*4000按列遍歷:')
tic
for j=1:4000
for i=1:4000
a(i,j)=1;
end
end
toc
%5000*5000
disp('5000*5000按行遍歷:')
tic
for i=1:5000
for j=1:5000
a(i,j)=1;
end
end
toc
disp('5000*5000按列遍歷:')
tic
for j=1:5000
for i=1:5000
a(i,j)=1;
end
end
toc
%6000*6000
disp('6000*6000按行遍歷:')
tic
for i=1:6000
for j=1:6000
a(i,j)=1;
end
end
toc
disp('6000*6000按列遍歷:')
tic
for j=1:6000
for i=1:6000
a(i,j)=1;
end
end
toc
%7000*7000
disp('7000*7000按行遍歷:')
tic
for i=1:7000
for j=1:7000
a(i,j)=1;
end
end
toc
disp('7000*7000按列遍歷:')
tic
for j=1:7000
for i=1:7000
a(i,j)=1;
end
end
toc
%8000*8000
disp('8000*8000按行遍歷:')
tic
for i=1:8000
for j=1:8000
a(i,j)=1;
end
end
toc
disp('8000*8000按列遍歷:')
tic
for j=1:8000
for i=1:8000
a(i,j)=1;
end
end
toc
%9000*9000
disp('9000*9000按行遍歷:')
tic
for i=1:9000
for j=1:9000
a(i,j)=1;
end
end
toc
disp('9000*9000按列遍歷:')
tic
for j=1:9000
for i=1:9000
a(i,j)=1;
end
end
toc
%10000*10000
disp('10000*10000按行遍歷:')
tic
for i=1:10000
for j=1:10000
a(i,j)=1;
end
end
toc
disp('10000*10000按列遍歷:')
tic
for j=1:10000
for i=1:10000
a(i,j)=1;
end
end
toc
%12000*12000
disp('12000*12000按行遍歷:')
tic
for i=1:12000
for j=1:12000
a(i,j)=1;
end
end
toc
disp('12000*12000按列遍歷:')
tic
for j=1:12000
for i=1:12000
a(i,j)=1;
end
end
toc
%14000*14000
disp('14000*14000按行遍歷:')
tic
for i=1:14000
for j=1:14000
a(i,j)=1;
end
end
toc
disp('14000*14000按列遍歷:')
tic
for j=1:14000
for i=1:14000
a(i,j)=1;
end
end
toc
%16000*16000
disp('16000*16000按行遍歷:')
tic
for i=1:16000
for j=1:16000
a(i,j)=1;
end
end
toc
disp('16000*16000按列遍歷:')
tic
for j=1:16000
for i=1:16000
a(i,j)=1;
end
end
toc
%18000*18000
disp('18000*18000按行遍歷:')
tic
for i=1:18000
for j=1:18000
a(i,j)=1;
end
end
toc
disp('18000*18000按列遍歷:')
tic
for j=1:18000
for i=1:18000
a(i,j)=1;
end
end
toc
%20000*20000
disp('20000*20000按行遍歷:')
tic
for i=1:20000
for j=1:20000
a(i,j)=1;
end
end
toc
disp('20000*20000按列遍歷:')
tic
for j=1:20000
for i=1:20000
a(i,j)=1;
end
end
toc
運行結果:
10*10按行遍歷:
歷時 0.001160 秒,
10*10按列遍歷:
歷時 0.002137 秒,
100*100按行遍歷:
歷時 0.002139 秒,
100*100按列遍歷:
歷時 0.001247 秒,
500*500按行遍歷:
歷時 0.005005 秒,
500*500按列遍歷:
歷時 0.002314 秒,
1000*1000按行遍歷:
歷時 0.013177 秒,
1000*1000按列遍歷:
歷時 0.008198 秒,
2000*2000按行遍歷:
歷時 0.055286 秒,
2000*2000按列遍歷:
歷時 0.031675 秒,
3000*3000按行遍歷:
歷時 0.111594 秒,
3000*3000按列遍歷:
歷時 0.054623 秒,
4000*4000按行遍歷:
歷時 0.159790 秒,
4000*4000按列遍歷:
歷時 0.031501 秒,
5000*5000按行遍歷:
歷時 0.253966 秒,
5000*5000按列遍歷:
歷時 0.040411 秒,
6000*6000按行遍歷:
歷時 0.347891 秒,
6000*6000按列遍歷:
歷時 0.051451 秒,
7000*7000按行遍歷:
歷時 0.474733 秒,
7000*7000按列遍歷:
歷時 0.065348 秒,
8000*8000按行遍歷:
歷時 0.614065 秒,
8000*8000按列遍歷:
歷時 0.082403 秒,
9000*9000按行遍歷:
歷時 0.748270 秒,
9000*9000按列遍歷:
歷時 0.101840 秒,
10000*10000按行遍歷:
歷時 0.951146 秒,
10000*10000按列遍歷:
歷時 0.126003 秒,
12000*12000按行遍歷:
歷時 1.470136 秒,
12000*12000按列遍歷:
歷時 0.201293 秒,
14000*14000按行遍歷:
歷時 1.947979 秒,
14000*14000按列遍歷:
歷時 0.222194 秒,
16000*16000按行遍歷:
歷時 2.618715 秒,
16000*16000按列遍歷:
歷時 0.296784 秒,
18000*18000按行遍歷:
歷時 5.445383 秒,
18000*18000按列遍歷:
歷時 2.052443 秒,
20000*20000按行遍歷:
歷時 7.020740 秒,
20000*20000按列遍歷:
歷時 2.864608 秒,
運行結果和C語言版本基本類似,只是按列遍歷更優,注意到當陣列大小增長(超過10000*10000)時,按行遍歷的運行時間增長得更快,超過了C語言在相同大小陣列的按列遍歷運行時間,
一般來說,像C語言、C++、Java等語言,按行遍歷要快于按列遍歷(陣列在記憶體中按行存盤);像MATLAB、Fortran等語言,按列遍歷要快于按行遍歷(陣列在記憶體中按列存盤),
轉載請註明出處,本文鏈接:https://www.uj5u.com/qita/70806.html
標籤:其他
下一篇:資料結構——順序表習題解(II)
