vector與array效能問題

作者: NDark (溺於黑暗) 看板: C_and_CPP
標題: [問題] vector與array效能問題
時間: Mon Nov 16 14:54:56 2009








已獲得解答,外加一些測試結果比較請看最後面











原問題:

開發平台 VC++ ( 專案為clr專案,但此部分為un-managed )
不好意思我想詢問一個std::vector與c array效能問題.
我在google上查過這個問題,一般看到的說法都是表示兩者之間效能是一樣好的.
                                                 (不管陣列長度會變化這件事情)
但是在我自己的一個專案中測試卻發現c array的花費時間較短.不知道問題是出在哪裡?
說明如下:
1.
我宣告一個class,內含一個std::vector,如下-
class Class
{
public : std::vector< bool > m_vbParam ;
} ;

2.
我宣告一個上述類別的全域變數物件
Class gsObj ;





3.
[此物件已經resize完成,大小大約是10萬左右.(因此是一個10萬長度的bool vector)]
在一個全域函式中透過迴圈access此全域變數的vector,迴圈的index都沒有超過長度
void Func1( void )
{
    for( i = 0 ... )
    {
        gsObj.m_vbParam[ i ] ; // (操作取值及存值)
    }
}
計算開始及結束的時間












4.
在另一個全域函式中傳入一個C Array,然後作相同的事情
void Func2( bool *_cArray )
{
    for( i = 0 ... )
    {
        _cArray[ i ] ; // (操作取值及存值)
    }
}
計算開始及結束的時間










5.
將bool vector的內容複製給一個c array,並呼叫Func2()
bool *cArray = NULL ;
cArray = new bool[ gsObj.m_vbParam.size() ] ;

for( i = 0 ; i < gsObj.m_vbParam.size() ; i++ )
        cArray[ i ] = gsObj.m_vbParam[ i ] ;
                     // 這邊我本來想用memcpy,可是執行的時候會出錯,煩請指點
void Func2( cArray ) ;
delete [] cArray ;

6.比較Fun1. Fun2.的花費時間(不考慮取得記憶體,複製的時間)
        c array的時間 比 std vector快7倍左右.
  可能的原因有
A       global vs. local : Func1是去使用global變數,Func2是使用傳入的array ptr.
B       vector in class : Func1的global物件內部的vector,較array來的麻煩.
C       vector vs. array : 長度很長的index下,效能真的有差別.
D       其他.

雖然我覺得是不應該是這些原因,但結果確實如此.不知問題比較可能出在哪裡?


感謝holymars說明,我改用unsigned char vector,就有提升效能了.我分別用
幾種不同的函式參數,測試結果如下:
A.使用std::vector(原來的舊方法)
B.函式中使用全域物件內的std::vector< unsigned char >成員
        FuncB(){ gsObj.m_vParam[ ... ] ... }
C.函式呼叫時傳入std::vector的reference
        FuncC( std::vector< unsigned char >& _param ){ _param[ ... ] ... }
D.函式呼叫時傳入由std::vector轉型的unsigned char*
        FuncD( unsigned char* _param ){ _param[ ... ] ... }
E.先將std::vector用memcpy複製為unsigned char array.然後傳入
        FuncE( unsigned char* _param ){ _param[ ... ] ... }
陣列長度大約在十萬左右,迴圈兩層(遊走總數不超過陣列長度),
                       迴圈內共有三次取值,三次判斷,一次assign.
   花費時間      參考比例
A. 14.93 ms         7.35
B.  3.98 ms         1.96
C.  4.31 ms         2.12
D.  2.03 ms         1
E.  2.26 ms*        1.11

*E方法的時間包含記憶體宣告,複製過去,複製回來,記憶體釋放
--
"May the Balance be with U"(願平衡與你同在)

視窗介面遊戲設計教學( http://0rz.tw/V28It )，討論，分享。歡迎來信。
視窗程式設計（Windows CLR Form）遊戲架構設計（Game Application Framework）
遊戲工具設計（Game App. Tool Design ）
電腦圖學架構及研究（Computer Graphics）論文代讀(含投影片製作)

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.96.77.176
推 holymars:答案是vector不是一般的std::vector，是特化過的    11/16 15:09
→ holymars:為了節省空間，犧牲了效率                               11/16 15:09
→ holymars:vector是用一個bit一個bit去存bool的               11/16 15:10
→ holymars:喔對了　Effective C++裡面有告訴你不要用vector    11/16 15:11
→ holymars:因為它其實不符合作為一個STL容器的定義                  11/16 15:12
→ NDark:這樣的話.我應該改用其他類別vector來達到我目的?            11/16 15:15
推 holymars:對　你換成vector和int[]再試一次吧                 11/16 15:21
→ holymars:vector是個美麗的錯誤，就和Valarray一樣           11/16 15:22
→ NDark:了解了....我會試看看的, 3q                                11/16 15:30
→ NDark:我加一些測試結果...請勿推文                               11/16 16:08
→ NDark:完畢.謝謝                                                 11/16 16:29
※ 編輯: NDark           來自: 140.96.77.176        (11/16 16:30)