ACM___________________________

MiYu原創(chuàng), 轉(zhuǎn)帖請注明 : 轉(zhuǎn)載自 ______________白白の屋    

做ACM題目的時候 , 經(jīng)常使用到  fill, memset  , for 操作對 數(shù)據(jù)進(jìn)行初始化操作, 在測試數(shù)據(jù)不大,而且數(shù)組范圍也不大的情況下,

這幾種操作的時間差距不是很明顯.  但是!!!!   因為測試數(shù)據(jù)的數(shù)量有時候非常大!!因此對數(shù)據(jù)初始化 操作的 選擇也變得非常重要. 

于是就對3種操作進(jìn)行了一個小測試.......................... 測試如下:

 測試系統(tǒng) 及 配置:        

 測試方案 :     開了3億的數(shù)組, 對每個函數(shù)調(diào)用三次

 測試結(jié)果 :

    fill  :                                  G++                                                                 C++

  memset  :                           G++                                                                C++

     for :                            G++                                                      C++

 從上面的 數(shù)據(jù)對比可以看到 ,  除去誤差外, 2種編譯器對數(shù)據(jù)的處理時間 基本是一致的, 對于第一次處理 , 都額外花費了500MS 左右的時間, 因為

 盡管一開始申請了3億的靜態(tài)數(shù)組空間, 但是系統(tǒng)并不會全部把它給你, 只是代表你有權(quán)使用它,  這就要感謝操作系統(tǒng)的 內(nèi)存管理機(jī)制了.   所以第一次

處理都花費了額外的時間來分配內(nèi)存.  這也是為什么ACM 中很多題, 明明開了1000000 或更大一點的數(shù)組  但是內(nèi)存開銷卻沒超過 1000KB 的原因.

現(xiàn)在我們看后面的數(shù)據(jù), 可以看到 memset 的時間優(yōu)勢非常明顯,  是 fill 和 for 的2.5倍左右 !!!.   但是 . 我不得不說明其局限性, 因為 memset 是

每字節(jié)賦值的, 所以一般情況下, 僅能用與對 0 或 -1 的賦值,   (  memset 在每個字節(jié)的末尾填充 設(shè)定值 ). 對于每個變量的其他確定性的賦值就顯得

力不從心了.  這時候就要用到 fill 或 for 循環(huán)賦值了, 原來一直覺得 fill 會很慢, 所以就一直沒用,  現(xiàn)在測試了一下才知道, 原來速度是基本一樣的, 現(xiàn)在做題可以

偷下懶了,   

 忘記附代碼了 ....

代碼

/*
MiYu原創(chuàng), 轉(zhuǎn)帖請注明 : 轉(zhuǎn)載自 ______________白白の屋
          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原創(chuàng), 轉(zhuǎn)帖請注明 : 轉(zhuǎn)載自 ______________白白の屋
          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;
}