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;
}