首页 > 程序开发 > 软件开发 > C++ >

[C++]二维数组还是一维数组?

2014-09-24

记得刚学习C++那会这个问题曾困扰过我,后来慢慢形成了不管什么时候都用一维数组的习惯,再后来知道了在一维数组中提出首列元素地址进行二维调用的办法。可从来没有细想过这个问题,最近自己写了点代码测试下,虽

记得刚学习C++那会这个问题曾困扰过我,后来慢慢形成了不管什么时候都用一维数组的习惯,再后来知道了在一维数组中提出首列元素地址进行二维调用的办法。可从来没有细想过这个问题,最近自己写了点代码测试下,虽然还是有些不明就里,不过结果挺有意思。
为了避免编译器优化过度,用的是写操作,int,测试分为不同大小的空间,同样大小空间不同的行和列数。分别记录逐行写入,逐列写入,按间隔写入,空间申请和释放的时间。
测试代码
一维数组的申请和释放
1 // Create
2 int *m = new int[n_row * n_col];
3
4 // Free
5 delete [] m;
二维数组的申请和释放
复制代码
1 // Create
2 int **m = new int*[n_row];
3 for ( int i = 0; i < n_row; ++i )
4 m[i] = new int[n_col];
5
6 // Free
7 for ( int i = 0; i < n_row; ++i )
8 delete [] m[i];
9 delete [] m;
复制代码
逐行写入
复制代码
1 for ( int i = 0; i < n_row; ++i )
2 {
3 for ( int j = 0; j < n_col; ++j )
4 {
5 matrix[i * n_col + j] = answer;
6 // matrix[i][j] = answer;
7 }
8 }
复制代码
逐列写入
复制代码
1 for ( int j = 0; j < n_col; ++j )
2 {
3 for ( int i = 0; i < n_row; ++i )
4 {
5 matrix[i * n_col + j] = answer;
6 // matrix[i][j] = answer;
7 }
8 }
复制代码
按间隔写入
复制代码
1 for ( int i = 0; i < n_row; ++i )
2 {
3 for ( int j = 0; j < n_col; ++j )
4 {
5 int row = i * 7 % n_row;
6 int col = j * 11 % n_col;
7 matrix[i * n_col + j] = answer;
8 // matrix[i][j] = answer;
9 }
10 }
复制代码
不是很确定这种测试是否很合理,不过大体上能体现我要测的东西了。需要注意的是逐行写入中为了简便我用的是写入一个叫answer的变量,其实情况应该更泛化,否则用memset或者std::fill也许会更快?逐列写入的代码本科课程级别的典型反面代码例子,这里也仅仅是为了测试。
仅仅从编译的角度来看主要的差别在下面两句:
1 matrix[i * n_col + j] = answer;
2 matrix[i][j] = answer;
来看一下对应的汇编代码:
复制代码
1 ; matrix[i * n_col + j] = answer;
2 mov edx, DWORD PTR _i$3[ebp]
3 imul edx, DWORD PTR _n_col$[ebp]
4 add edx, DWORD PTR _j$2[ebp]
5 mov eax, DWORD PTR _matrix$[ebp]
6 mov ecx, DWORD PTR _answer$[ebp]
7 mov DWORD PTR [eax+edx*4], ecx
复制代码
复制代码
1 ; matrix[i][j] = answer;
2 mov ecx, DWORD PTR _i$4[ebp]
3 mov edx, DWORD PTR _matrix$[ebp]
4 mov eax, DWORD PTR [edx+ecx*4]
5 mov ecx, DWORD PTR _j$3[ebp]
6 mov edx, DWORD PTR _answer$[ebp]
7 mov DWORD PTR [eax+ecx*4], edx
复制代码
都是6条指令,体系学得不好,所以也看不出哪个更快。这里用的是Visual Studio编译,因为本人gcc用得不熟,不知道怎么生成这么直观的汇编和C++对应,效率上而言Linux下还是比Windows高一些,不过为了统一,之后的测试也基于Windows。当然上面的是没有优化的编译,如果开了优化(VS /O2),汇编指令大概也都是4、5条的样子,因为/O2优化后的汇编代码结构不是很直观,这里就不贴了。(另一方面也是由于我的汇编水平很弱,看不出什么)
除了直接使用一维和二维数组,也可以对一维数组进行二维索引,方法是把一维数组中所有对应第一列的元素的地址单独作为一个指针数组,这样本质上还是一维数组,但是实现了形式上的二维数组调用,这种办法空间申请的代码如下:
1 // Create
2 int **m = new int*[n_row];
3 int *block = new int[n_row * n_col];
4 for ( int i = 0; i < n_row; ++i )
5 m[i] = &block[i * n_col];
6 return m;
释放的代码和二维数组相同。
用一维数组模拟二维调用的优点是既保证了内存空间的连续性,又保持了二维调用的代码易维护的优点。不过需要注意的是,由于是二维索引,汇编代码和二维数组还是一样的。
相关文章
最新文章
热点推荐