Re: [問題] deque vs vector

[pracinverse (改)]

※ 引述《pracinverse (改)》之銘言：
: STL源碼剖析提到deque的複雜度較vector高，所以使用Algorithm 的sort()時，vector會比較怏。
: 可是我使用VC2005測試發現，deque 使用sort()反而比Vector快，這是為什麼呢？

補上程式碼:

#define MAX 100000

void main()
{
    deque<int>  d;
    vector<int> v;

    srand(time(NULL));
    for(int i = 0; i < MAX; ++i)
        d.push_back(rand()%100);

    v.assign(d.begin(), d.end());

    DWORD dwStart = GetTickCount();
    sort(d.begin(), d.end());
    DWORD dwEnd = GetTickCount();
    cout << "deque sort: " << dwEnd - dwStart << endl;

    dwStart = GetTickCount();
    sort(v.begin(), v.end());
    dwEnd = GetTickCount();
    cout << "vector sort: " << dwEnd - dwStart << endl;

}

我換用vc++ 2008 express，結果還是一樣，

vector所花的時間比較久

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 111.240.177.35
→ james732:在我的電腦裡，vector比deque快很多耶？
→ james732:程式與結果請看：http://codepad.org/1Dc53ToI
→ james732:(為什麼debug與release可以差這麼多...??)
→ james732:我的是visual studio 2010
→ diabloevagto:http://codepad.org/nwyInUKE
→ diabloevagto:我的release快好多＝ ＝vector都是0...
→ james732:MAX是十萬的話，vector跑出來都是0
→ james732:所以我才會再加一個0上去 XD
→ diabloevagto:C::B_SVN7452+TDM 4.5.2
→ diabloevagto:我還特地對了一下...還是少看一了0...＝.＝
→ diabloevagto:多一個0之後vector還是只需要一半的時間
→ diabloevagto:我覺得用vector會比較快會不會是因為讀值比較快？
→ diabloevagto:不用像que需要從頭跑
→ tropical72:release 不是 0 就是 16m(ts) ,那是因為根本沒編進去
推 james732:沒編進去的意思是？
→ tropical72:這份測試碼最後沒做輸出,沒做其它功能,vs最後opt.應都
→ tropical72:會整個拿掉.. (還有 release 測時很麻煩..)
→ diabloevagto:我測試release是141跟62，那應該就有編進去吧
→ tropical72:嗯,抱歉,剛trace asm,d大給的code是有編進去的.
→ diabloevagto:我猜應該是有sort就邊進去
→ tropical72:嗯嗯,原po應都沒開opt.vc debug mode的確deque快一點.
推 VictorTom:VC的話要不要用QueryPerformanceCounter試試? 應該可以
→ VictorTom:比GetTickCount更精確一點吧...@_@"
→ diabloevagto:我開了o3在10萬會16跟0，100萬是140跟60
→ diabloevagto:debug之下
→ tropical72:借james來改 http://codepad.org/1Dc53ToI vc參考一下
→ tropical72:耶..我該說清楚些,一般指release/debug mode指的是編譯
→ tropical72:器(IDE)預設的參數,自己開了o2,o3,的確該另當別論。
→ diabloevagto:原來是這樣，長知識了，感謝T大！
→ tropical72:!! 沒 po 到,補上 http://codepad.org/raJwLlUT
→ diabloevagto:話說t大的deque跟vector也差太多了吧...
→ tropical72:我第一次不小心po到james的,第二次才po到我改的code XD
→ diabloevagto:嗯...我看code好像沒差多少？怎麼速度差這麼多
→ diabloevagto:抱歉我傻了＝ ＝那個_DEBUG在vs跟cb的不同...
→ loveme00835:deque的迭代器分類跟vector是同樣的，inplace sort時
推 loveme00835:間差少不需太意外...最佳化就看它索引計算怎麼加速，
→ loveme00835:value_type用內建型態來測受影響太大
→ angleevil:我後來去goodle vector deque.找到回答這篇的答案
→ angleevil:http://www.gotw.ca/gotw/054.htm
→ angleevil:請用sort關鍵字去搜尋.之後就會看到作者的測試數據
→ angleevil:此外,我是覺得要測試的話,不要用release.有點沒意義
→ angleevil:他會最佳化的是asm那部分. 那就跟演算法脫鉤了