- 用c语言写一个大规模矩阵遍历的程序，在不同规模的数据下运行，比较按行遍历快还是按列遍历快。
1）本题老师的考察点：矩阵在计算机内存储的方式
2）解答本题时遇到的一些问题：
【1】在考虑矩阵时，考虑了数组，又想到了线性代数，刚开始还在纠结行列是不是要一致。
【2】直接从codeblocks粘贴代码过来简直太丑了，于是想到了我好久不用的csdn账号，顺便再发个原创博客。
3）代码说明：
【1】clock（）函数在头文件#include<time.h>中。
【2】clock（）函数的返回值类型为clock_t。
【3】clock_t是用来保存时间的数据类型，typedef long clock_t，即长整形。
【4】将MAX_ROW和MAX_COL设置成静态常量放在前面，赋值改变方便。
【5】C语言中指针分配空间用的是malloc，c++中用的是new，注意malloc分配完内存后记得free。
【6】第一次写这个题代码的时候是想着直接将矩阵每个元素的地址打印出来，后来发现打印的太多了，我真正输出的时间反而找不到了，不如只打印我的按行遍历和按列遍历的时间，方便直观。
4）代码如下：
```c
#include <stdio.h>
#include <stdlib.h>
#include<time.h>
int main()
{
const int MAX_ROW = 2048;
const int MAX_COL = 2048;
int (*a)[MAX_COL]=(int(*)[MAX_COL])malloc(sizeof(int)*MAX_ROW*MAX_COL);
clock_t start, finish;
start = clock();
for (int i = 0; i<MAX_ROW; i++)
for (int j = 0; j<MAX_COL; j++)
a[i][j] = 1;
finish = clock();
printf("The first travel time is %lf ms\n",(double)finish-start);
start = clock();
for (int i = 0; i<MAX_COL; i++)
for (int j = 0; j<MAX_ROW; j++)
a[j][i] = 1;
finish = clock();
printf("The second travel time is %lf ms\n",(double)finish-start);
return 0;
}
5）运行结果：
【0】【0】行数为512，列数为512执行结果：
【0】【1】行数为512，列数为1024执行结果：
【0】【2】行数为512，列数为2048执行结果：
【0】【3】行数为512，列数为4096执行结果：
【0】【4】行数为512，列数为8192执行结果：
【0】【5】行数为512，列数为16384执行结果：
【1】【0】行数为1024，列数为512执行结果：
【1】【1】行数为1024，列数为1024执行结果：
【1】【2】行数为1024，列数为2048执行结果：
【1】【3】行数为1024，列数为4096执行结果：
【1】【4】行数为1024，列数为8192执行结果：
【1】【5】行数为1024，列数为16384执行结果：
【2】【0】行数为2048，列数为512执行结果：
【2】【1】行数为2048，列数为1024执行结果：
【2】【2】行数为2048，列数为2048执行结果：
【2】【3】行数为2048，列数为4096执行结果：
【2】【4】行数为2048，列数为8192执行结果：
【2】【5】行数为2048，列数为16384执行结果：
【3】【0】行数为4096，列数为512执行结果：
【3】【1】行数为4096，列数为1024执行结果：
【3】【2】行数为4096，列数为2048执行结果：
【3】【3】行数为4096，列数为4096执行结果：
【3】【4】行数为4096，列数为8192执行结果：
【3】【5】行数为4096，列数为16384执行结果：
【4】【0】行数为8192，列数为512执行结果：
【4】【1】行数为8192，列数为1024执行结果：
【4】【2】行数为8192，列数为2048执行结果：
【4】【3】行数为8192，列数为4096执行结果：
【4】【4】行数为8192，列数为8192执行结果：
【4】【5】行数为8192，列数为16384执行结果：
【5】【0】行数为16384，列数为512执行结果：
【5】【1】行数为16384，列数为1024执行结果：
【5】【2】行数为16384，列数为2048执行结果：
【5】【3】行数为16384，列数为4096执行结果：
【5】【4】行数为16384，列数为8192执行结果：
【5】【5】行数为16384，列数为16384执行结果：
6）结果处理分析：
【0】不同行列维数下对应按行遍历和按列遍历时间如下所示：（单位均为ms）
行\列 512 1024 2048 4096 8192 16284
512 0\2 1\7 1\14 6\34 11\90 22\176
1024 1\4 2\13 5\34 10\83 22\179 45\365
2048 1\12 4\32 15\80 22\180 44\353 94\703
4096 5\25 11\68 23\151 43\346 93\720 193\1436
8192 11\63 21\143 43\289 88\701 185\1389 380\2854
16284 22\140 44\284 89\586 179\1399 387\2832 724\5651
【1】 分析固定行数时不同列数对应遍历时间图：
简单用matlab绘制的散点曲线图，代码如下：
```c
x=[512 1024 2048 4096 8192 16384];
y11=[0 1 1 6 11 22];
y12=[2 7 14 34 90 176];
y21=[1 2 5 10 22 45];
y22=[4 13 34 83 179 365];
y31=[1 4 15 22 44 94];
y32=[12 32 80 180 353 703];
y41=[5 11 23 43 93 193];
y42=[25 68 151 346 720 1436];
y51=[11 21 43 88 185 380];
y52=[63 143 289 701 1389 2854];
y61=[22 44 89 179 387 724];
y62=[140 284 586 1399 2832 5651];
plot(x,y11,x,y12,x,y21,x,y22,x,y31,x,y32,x,y41,x,y42,x,y51,x,y52,x,y61,x,y62)
运行结果如下：
图1.6.1 矩阵不同列维数对应按行遍历和按列遍历的时间
图1.6.1说明：
[1]图像横轴为矩阵列维数，分别为512,1024,2048,4096,8192,16384
[2]图像纵轴为遍历时间，单位为ms
[3]从下往上数依次为曲线1,2……12
[4]曲线1,3,5,7,9,11为矩阵行维数为512,1024,2048,4096,8192,16384时对应的按行遍历的时间
[5] 曲线2,4,6,8,10,12为矩阵行维数为512,1024,2048,4096,8192,16384时对应的按列遍历的时间
【2】 分区对比图
x=[512 1024 2048 4096 8192 16384];
y11=[0 1 1 6 11 22];
y12=[2 7 14 34 90 176];
subplot(2,3,1);
plot(x,y11,x,y12);
ylabel('矩阵行为512');
y21=[1 2 5 10 22 45];
y22=[4 13 34 83 179 365];
subplot(2,3,4);
plot(x,y21,x,y22);
ylabel('矩阵行为1024');
y31=[1 4 15 22 44 94];
y32=[12 32 80 180 353 703];
subplot(2,3,2);
plot(x,y31,x,y32);
ylabel('矩阵行为2048');
y41=[5 11 23 43 93 193];
y42=[25 68 151 346 720 1436];
subplot(2,3,5);
plot(x,y41,x,y42);
ylabel('矩阵行为4096');
y51=[11 21 43 88 185 380];
y52=[63 143 289 701 1389 2854];
subplot(2,3,3);
plot(x,y51,x,y52);
ylabel('矩阵行为8192');
y61=[22 44 89 179 387 724];
y62=[140 284 586 1399 2832 5651];
subplot(2,3,6);
plot(x,y61,x,y62);
ylabel('矩阵行为16384');
运行结果如下：
图1.6.2 矩阵不同列维数对应按行遍历和按列遍历的时间
图1.6.2说明：
[1]图像横轴为矩阵列维数，分别为512,1024,2048,4096,8192,16384
[2]图像纵轴为遍历时间，单位为ms
[3]第一列的两个图像分别是矩阵行维数为512和1024时对应的按行访问和按列访问的曲线图，其中斜率较小的按行遍历的曲线
[4]第一列的两个图像分别是矩阵行维数为2048和4096时对应的按行访问和按列访问的曲线图，其中斜率较小的按行遍历的曲线
[5]第一列的两个图像分别是矩阵行维数为8192和16384时对应的按行访问和按列访问的曲线图，其中斜率较小的按行遍历的曲线
【3】 分析固定列数时不同行数对应遍历时间图：
简单用matlab绘制的散点曲线图，代码如下：
x=[512 1024 2048 4096 8192 16384];
y11=[0 1 1 5 11 22];
y12=[2 4 12 25 63 140];
y21=[1 2 4 11 21 44];
y22=[7 13 32 68 143 284];
y31=[1 5 15 23 43 89];
y32=[14 34 80 151 289 586];
y41=[6 10 22 43 88 179];
y42=[34 83 180 346 701 1399];
y51=[11 22 44 93 185 387];
y52=[90 179 353 720 1389 2832];
y61=[22 45 94 193 380 724];
y62=[176 365 703 1436 2854 5651];
plot(x,y11,x,y12,x,y21,x,y22,x,y31,x,y32,x,y41,x,y42,x,y51,x,y52,x,y61,x,y62)
运行结果如下：
图1.6.3 矩阵不同行维数对应按行遍历和按列遍历的时间
图1.6.3说明：
[1]图像横轴为矩阵行维数，分别为512,1024,2048,4096,8192,16384
[2]图像纵轴为遍历时间，单位为ms
[3]从下往上数依次为曲线1,2……12
[4]曲线1,3,5,7,9,11为矩阵列维数为512,1024,2048,4096,8192,16384时对应的按行遍历的时间
[5] 曲线2,4,6,8,10,12为矩阵列维数为512,1024,2048,4096,8192,16384时对应的按列遍历的时间
【4】 分区对比图
x=[512 1024 2048 4096 8192 16384];
y11=[0 1 1 5 11 22];
y12=[2 4 12 25 63 140];
subplot(2,3,1);
plot(x,y11,x,y12);
ylabel('矩阵列为512');
y21=[1 2 4 11 21 44];
y22=[7 13 32 68 143 284];
subplot(2,3,4);
plot(x,y21,x,y22);
ylabel('矩阵列为1024');
y31=[1 5 15 23 43 89];
y32=[14 34 80 151 289 586];
subplot(2,3,2);
plot(x,y31,x,y32);
ylabel('矩阵列为2048');
y41=[6 10 22 43 88 179];
y42=[34 83 180 346 701 1399];
subplot(2,3,5);
plot(x,y41,x,y42);
ylabel('矩阵列为4096');
y51=[11 22 44 93 185 387];
y52=[90 179 353 720 1389 2832];
subplot(2,3,3);
plot(x,y51,x,y52);
ylabel('矩阵列为8192');
y61=[22 45 94 193 380 724];
y62=[176 365 703 1436 2854 5651];
subplot(2,3,6);
plot(x,y61,x,y62);
ylabel('矩阵列为16384');
运行结果如下：
图1.6.4 矩阵不同行维数对应按行遍历和按列遍历的时间
图1.6.4说明：
[1]图像横轴为矩阵行维数，分别为512,1024,2048,4096,8192,16384
[2]图像纵轴为遍历时间，单位为ms
[3]第一列的两个图像分别是矩阵列维数为512和1024时对应的按行访问和按列访问的曲线图，其中斜率较小的按行遍历的曲线
[4]第一列的两个图像分别是矩阵列维数为2048和4096时对应的按行访问和按列访问的曲线图，其中斜率较小的按行遍历的曲线
[5]第一列的两个图像分别是矩阵列维数为8192和16384时对应的按行访问和按列访问的曲线图，其中斜率较小的按行遍历的曲线
7）得出结论：
【1】按行遍历比按列遍历快。
【2】矩阵规模越大，按行遍历与按列遍历时间差异越显著。
8）理论解释：
【1】CPU高速缓存：维基百科中有以下的内容：CPU高速缓存（英语：CPU Cache，在本文中简称缓存）是用于减少处理器访问内存所需平均时间的部件。在金字塔式存储体系中它位于自顶向下的第二层，仅次于CPU寄存器。其容量远小于内存，但速度却可以接近处理器的频率。当处理器发出内存访问请求时，会先查看缓存内是否有请求数据。如果存在（命中），则不经访问内存直接返回该数据；如果不存在（失效），则要先把内存中的相应数据载入缓存，再将其返回处理器。
缓存从内存中抓取一般都是整个数据块，所以它的物理内存是连续的，几乎都是同行不同列的，而如果内循环以列的方式进行遍历的话，将会使整个缓存块无法被利用，而不得不从内存中读取数据，而从内存读取速度是远远小于从缓存中读取数据的。随着数组元素越来越多，按列读取速度也会越来越慢。
【2】分页调度：物理内存是以页的方式进行划分的，当一个二维数组很大是如 int[128][1024],假设一页的内存为4096个字节，而每一行正好占据内存的一页，如果以列的形式进行遍历，就会发生128*1024次的页面调度，而如果以行遍历则只有128次页面调度，而页面调度是有时间消耗的，因而调度次数越多，遍历的时间就越长。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
