ACM___________________________

MiYu原创, 转帖请注明 : 转载自 ______________白白の屋    

做ACM题目的时候 , 经常使用到  fill, memset  , for 操作对 数据进行初始化操作, 在测试数据不大,而且数组范围也不大的情况下,

这几种操作的时间差距不是很明显.  但是!!!!   因为测试数据的数量有时候非常大!!因此对数据初始化 操作的 选择也变得非常重要. 

于是就对3种操作进行了一个小测试.......................... 测试如下:

 测试系统 及 配置:        

 测试方案 :     开了3亿的数组, 对每个函数调用三次

 测试结果 :

    fill  :                                  G++                                                                 C++

  memset  :                           G++                                                                C++

     for :                            G++                                                      C++

 从上面的 数据对比可以看到 ,  除去误差外, 2种编译器对数据的处理时间 基本是一致的, 对于第一次处理 , 都额外花费了500MS 左右的时间, 因为

 尽管一开始申请了3亿的静态数组空间, 但是系统并不会全部把它给你, 只是代表你有权使用它,  这就要感谢操作系统的 内存管理机制了.   所以第一次

处理都花费了额外的时间来分配内存.  这也是为什么ACM 中很多题, 明明开了1000000 或更大一点的数组  但是内存开销却没超过 1000KB 的原因.

现在我们看后面的数据, 可以看到 memset 的时间优势非常明显,  是 fill 和 for 的2.5倍左右 !!!.   但是 . 我不得不说明其局限性, 因为 memset 是

每字节赋值的, 所以一般情况下, 仅能用与对 0 或 -1 的赋值,   (  memset 在每个字节的末尾填充 设定值 ). 对于每个变量的其他确定性的赋值就显得

力不从心了.  这时候就要用到 fill 或 for 循环赋值了, 原来一直觉得 fill 会很慢, 所以就一直没用,  现在测试了一下才知道, 原来速度是基本一样的, 现在做题可以

偷下懒了,   

 忘记附代码了 ....

代码

/*
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   : 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;
}