|
Posted on 2010-09-02 10:47 MiYu 阅读(1849) 评论(9) 编辑 收藏 引用 所属分类: C/C++ 、 ACM_资料
MiYu原创, 转帖请注明 : 转载自 ______________白白の屋 做ACM题目的时候 , 经常使用到 fill, memset , for 操作对 数据进行初始化操作, 在测试数据不大,而且数组范围也不大的情况下, 这几种操作的时间差距不是很明显. 但是!!!! 因为测试数据的数量有时候非常大!!因此对数据初始化 操作的 选择也变得非常重要. 于是就对3种操作进行了一个小测试.......................... 测试如下: 测试系统 及 配置: ![](http://images.cnblogs.com/cnblogs_com/miyu/22211111_25953684.jpg) 测试方案 : 开了3亿的数组, 对每个函数调用三次 测试结果 : fill : G++ C++ memset : G++ C++ for : G++ C++ ![](http://images.cnblogs.com/cnblogs_com/miyu/for_6.jpg) 从上面的 数据对比可以看到 , 除去误差外, 2种编译器对数据的处理时间 基本是一致的, 对于第一次处理 , 都额外花费了500MS 左右的时间, 因为 尽管一开始申请了3亿的静态数组空间, 但是系统并不会全部把它给你, 只是代表你有权使用它, 这就要感谢操作系统的 内存管理机制了. 所以第一次 处理都花费了额外的时间来分配内存. 这也是为什么ACM 中很多题, 明明开了1000000 或更大一点的数组 但是内存开销却没超过 1000KB 的原因.![](http://www.cnblogs.com/Emoticons/baimantou/201937664.gif) 现在我们看后面的数据, 可以看到 memset 的时间优势非常明显, 是 fill 和 for 的2.5倍左右 !!!. 但是 . 我不得不说明其局限性, 因为 memset 是 每字节赋值的, 所以一般情况下, 仅能用与对 0 或 -1 的赋值, ( memset 在每个字节的末尾填充 设定值 ). 对于每个变量的其他确定性的赋值就显得 力不从心了. 这时候就要用到 fill 或 for 循环赋值了, 原来一直觉得 fill 会很慢, 所以就一直没用, 现在测试了一下才知道, 原来速度是基本一样的, 现在做题可以 偷下懒了, ![](http://www.cnblogs.com/Emoticons/baimantou/105104147.gif) 忘记附代码了 ....![](http://www.cnblogs.com/Emoticons/baimantou/134950908.gif) 代码/* MiYu原创, 转帖请注明 : 转载自 ______________白白の屋 http://www.cnblog.com/MiYu Author By : MiYu Test : 1 Program : fill */
#include <iostream> #include <algorithm> #include <ctime> using namespace std; const int M = 300000000; int a[M]; int main () { time_t beg = clock(); fill ( a,a+M,0 ); fill ( a,a+M,0xff ); fill ( a,a+M,0 ); time_t end = clock(); cout << "fill operator Cost 1:"; cout << end - beg << " MS" << endl; beg = clock(); fill ( a,a+M,0 );fill ( a,a+M,0xff );fill ( a,a+M,0 ); end = clock(); cout << "fill operator Cost 2:"; cout << end - beg << " MS" << endl; beg = clock(); fill ( a,a+M,0 );fill ( a,a+M,0xff );fill ( a,a+M,0 ); end = clock(); cout << "fill operator Cost 3:"; cout << end - beg << " MS" << endl; beg = clock(); fill ( a,a+M,0 );fill ( a,a+M,0xff );fill ( a,a+M,0 ); end = clock(); cout << "fill operator Cost 4:"; cout << end - beg << " MS" << endl; beg = clock(); fill ( a,a+M,0 );fill ( a,a+M,0xff );fill ( a,a+M,0 ); end = clock(); cout << "fill operator Cost 5:"; cout << end - beg << " MS" << endl; beg = clock(); fill ( a,a+M,0 );fill ( a,a+M,0xff );fill ( a,a+M,0 ); end = clock(); cout << "fill operator Cost 6:"; cout << end - beg << " MS" << endl; beg = clock(); fill ( a,a+M,0 );fill ( a,a+M,0xff );fill ( a,a+M,0 ); end = clock(); cout << "fill operator Cost 7:"; cout << end - beg << " MS" << endl; system ( "pause" ); return 0; }
代码 /* MiYu原创, 转帖请注明 : 转载自 ______________白白の屋 http://www.cnblog.com/MiYu Author By : MiYu Test : 1 Program : memset */
#include <iostream> #include <algorithm> #include <ctime> using namespace std; const int M = 300000000; int a[M]; int main () { time_t beg,end; beg = clock(); memset ( a, 0, sizeof (a) );memset ( a, 0, sizeof (a) );memset ( a, 0, sizeof (a) ); end = clock(); cout << "memset operator Cost 1: "; cout << end - beg << " MS" << endl; beg = clock(); memset ( a, 0, sizeof (a) );memset ( a, 0, sizeof (a) );memset ( a, 0, sizeof (a) ); end = clock(); cout << "memset operator Cost 2: "; cout << end - beg << " MS" << endl; beg = clock(); memset ( a, 0, sizeof (a) );memset ( a, 0, sizeof (a) );memset ( a, 0, sizeof (a) ); end = clock(); cout << "memset operator Cost 3: "; cout << end - beg << " MS" << endl; beg = clock(); memset ( a, 0, sizeof (a) );memset ( a, 0, sizeof (a) );memset ( a, 0, sizeof (a) ); end = clock(); cout << "memset operator Cost 4: "; cout << end - beg << " MS" << endl; beg = clock(); memset ( a, 0, sizeof (a) );memset ( a, 0, sizeof (a) );memset ( a, 0, sizeof (a) ); end = clock(); cout << "memset operator Cost 5: "; cout << end - beg << " MS" << endl; beg = clock(); memset ( a, 0, sizeof (a) );memset ( a, 0, sizeof (a) );memset ( a, 0, sizeof (a) ); end = clock(); cout << "memset operator Cost 6: "; cout << end - beg << " MS" << endl; beg = clock(); memset ( a, 0, sizeof (a) );memset ( a, 0, sizeof (a) );memset ( a, 0, sizeof (a) ); end = clock(); cout << "memset operator Cost 7: "; cout << end - beg << " MS" << endl;
system ( "pause" ); return 0; }
代码/* MiYu原创, 转帖请注明 : 转载自 ______________白白の屋 http://www.cnblog.com/MiYu Author By : MiYu Test : 1 Program : for */
#include <iostream> #include <algorithm> #include <ctime> using namespace std; const int M = 300000000; int a[M]; int main () { time_t beg,end; int i; beg = clock(); for ( i = 0; i != M; ++ i ) a[i] = 0; for ( i = 0; i != M; ++ i ) a[i] = 0; for ( i = 0; i != M; ++ i ) a[i] = 0; end = clock(); cout << "for operator Cost 1: "; cout << end - beg << " MS" << endl; beg = clock(); for ( i = 0; i != M; ++ i ) a[i] = 0; for ( i = 0; i != M; ++ i ) a[i] = 0; for ( i = 0; i != M; ++ i ) a[i] = 0; end = clock(); cout << "for operator Cost 2: "; cout << end - beg << " MS" << endl; beg = clock(); for ( i = 0; i != M; ++ i ) a[i] = 0; for ( i = 0; i != M; ++ i ) a[i] = 0; for ( i = 0; i != M; ++ i ) a[i] = 0; end = clock(); cout << "for operator Cost 3: "; cout << end - beg << " MS" << endl; beg = clock(); for ( i = 0; i != M; ++ i ) a[i] = 0; for ( i = 0; i != M; ++ i ) a[i] = 0; for ( i = 0; i != M; ++ i ) a[i] = 0; end = clock(); cout << "for operator Cost 4: "; cout << end - beg << " MS" << endl; beg = clock(); for ( i = 0; i != M; ++ i ) a[i] = 0; for ( i = 0; i != M; ++ i ) a[i] = 0; for ( i = 0; i != M; ++ i ) a[i] = 0; end = clock(); cout << "for operator Cost 5: "; cout << end - beg << " MS" << endl; beg = clock(); for ( i = 0; i != M; ++ i ) a[i] = 0; for ( i = 0; i != M; ++ i ) a[i] = 0; for ( i = 0; i != M; ++ i ) a[i] = 0; end = clock(); cout << "for operator Cost 6: "; cout << end - beg << " MS" << endl; beg = clock(); for ( i = 0; i != M; ++ i ) a[i] = 0; for ( i = 0; i != M; ++ i ) a[i] = 0; for ( i = 0; i != M; ++ i ) a[i] = 0; end = clock(); cout << "for operator Cost 7: "; cout << end - beg << " MS" << endl; system ( "pause" ); return 0; }
Feedback
# re: fill memset for 小测试 回复 更多评论
2010-09-02 10:48 by
还插表情,够辛苦的。
# re: fill memset for 小测试 回复 更多评论
2010-09-02 17:21 by
我认为单纯的从代码层次看或者比较还不是很清楚的说明什么。
也许编译器在处理代码的时候都自己做了很多优化工作,最终殊途同归了?
但不保证每个编译器都是这样的。
反编译到汇编层次分析,才更说服力。
# re: fill memset for 小测试 回复 更多评论
2010-09-02 23:19 by
好像clock理解错了吧。 end - begin 应该说的的clock tick而不是MS,要MS 应该还要除以CLK_PER_SEC(还是CLOCK_PER_SEC,忘了自己查查)。
# re: fill memset for 小测试 回复 更多评论
2010-09-03 10:18 by
@大渊献 呃, 没啥, 做题累了 ........
# re: fill memset for 小测试 回复 更多评论
2010-09-03 10:19 by
@糨糊 表示汇编还没学过.... T.T 路还好长啊....
# re: fill memset for 小测试 回复 更多评论
2010-09-03 10:23 by
@chaogu 因为 用的编译器 的CLK_TCK宏, 本身就已经是1000, 所以没有除了, 因为除的话得到的就是 S 了
# re: fill memset for 小测试 回复 更多评论
2010-09-03 23:48 by
可以直接用 MSVC的 __stosd
VC CRT的memset实现就是使用指令: rep stosd
在一些CPU上该指令要比直接用 mov + 循环控制 要快(对现在主流的CPU这也许是是最快的内存清0方法,如果不使用SSE指令的话)。
另外,for循环好像也可以优化,使用 rep stosd指令。
# re: fill memset for 小测试 回复 更多评论
2010-09-10 22:30 by
受教了 ``
|