Re: [問題] deque vs vector

看板C_and_CPP作者 (改)時間14年前 (2011/10/05 08:36), 編輯推噓3(3推 0噓 39→)
留言42則, 6人參與, 最新討論串2/3 (看更多)
※ 引述《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
→
10/05 09:07, , 1F
在我的電腦裡，vector比deque快很多耶？
10/05 09:07, 1F
→
10/05 09:10, , 2F
程式與結果請看：http://codepad.org/1Dc53ToI
10/05 09:10, 2F
→
10/05 09:11, , 3F
(為什麼debug與release可以差這麼多...??)
10/05 09:11, 3F
→
10/05 09:12, , 4F
我的是visual studio 2010
10/05 09:12, 4F
→
10/05 09:18, , 5F
10/05 09:18, 5F
→
10/05 09:19, , 6F
我的release快好多＝ ＝vector都是0...
10/05 09:19, 6F
→
10/05 09:20, , 7F
MAX是十萬的話，vector跑出來都是0
10/05 09:20, 7F
→
10/05 09:21, , 8F
所以我才會再加一個0上去 XD
10/05 09:21, 8F
→
10/05 09:22, , 9F
C::B_SVN7452+TDM 4.5.2
10/05 09:22, 9F
→
10/05 09:23, , 10F
我還特地對了一下...還是少看一了0...＝.＝
10/05 09:23, 10F
→
10/05 09:25, , 11F
多一個0之後vector還是只需要一半的時間
10/05 09:25, 11F
→
10/05 09:25, , 12F
我覺得用vector會比較快會不會是因為讀值比較快？
10/05 09:25, 12F
→
10/05 09:26, , 13F
不用像que需要從頭跑
10/05 09:26, 13F
→
10/05 09:41, , 14F
release 不是 0 就是 16m(ts) ,那是因為根本沒編進去
10/05 09:41, 14F
推
10/05 09:45, , 15F
沒編進去的意思是？
10/05 09:45, 15F
→
10/05 09:48, , 16F
這份測試碼最後沒做輸出,沒做其它功能,vs最後opt.應都
10/05 09:48, 16F
→
10/05 09:48, , 17F
會整個拿掉.. (還有 release 測時很麻煩..)
10/05 09:48, 17F
→
10/05 09:52, , 18F
我測試release是141跟62，那應該就有編進去吧
10/05 09:52, 18F
→
10/05 09:53, , 19F
嗯,抱歉,剛trace asm,d大給的code是有編進去的.
10/05 09:53, 19F
→
10/05 09:55, , 20F
我猜應該是有sort就邊進去
10/05 09:55, 20F
→
10/05 09:59, , 21F
嗯嗯,原po應都沒開opt.vc debug mode的確deque快一點.
10/05 09:59, 21F
推
10/05 10:00, , 22F
VC的話要不要用QueryPerformanceCounter試試? 應該可以
10/05 10:00, 22F
→
10/05 10:01, , 23F
比GetTickCount更精確一點吧...@_@"
10/05 10:01, 23F
→
10/05 10:02, , 24F
我開了o3在10萬會16跟0，100萬是140跟60
10/05 10:02, 24F
→
10/05 10:02, , 25F
debug之下
10/05 10:02, 25F
→
10/05 10:08, , 26F
借james來改 http://codepad.org/1Dc53ToI vc參考一下
10/05 10:08, 26F
→
10/05 10:09, , 27F
耶..我該說清楚些,一般指release/debug mode指的是編譯
10/05 10:09, 27F
→
10/05 10:10, , 28F
器(IDE)預設的參數,自己開了o2,o3,的確該另當別論。
10/05 10:10, 28F
→
10/05 10:11, , 29F
原來是這樣，長知識了，感謝T大！
10/05 10:11, 29F
→
10/05 10:11, , 30F
!! 沒 po 到,補上 http://codepad.org/raJwLlUT
10/05 10:11, 30F
→
10/05 10:12, , 31F
話說t大的deque跟vector也差太多了吧...
10/05 10:12, 31F
→
10/05 10:14, , 32F
我第一次不小心po到james的,第二次才po到我改的code XD
10/05 10:14, 32F
→
10/05 10:16, , 33F
嗯...我看code好像沒差多少？怎麼速度差這麼多
10/05 10:16, 33F
→
10/05 10:18, , 34F
抱歉我傻了＝ ＝那個_DEBUG在vs跟cb的不同...
10/05 10:18, 34F
→
10/05 13:33, , 35F
deque的迭代器分類跟vector是同樣的，inplace sort時
10/05 13:33, 35F
推
10/05 13:35, , 36F
間差少不需太意外...最佳化就看它索引計算怎麼加速，
10/05 13:35, 36F
→
10/05 13:43, , 37F
value_type用內建型態來測受影響太大
10/05 13:43, 37F
→
10/05 16:27, , 38F
我後來去goodle vector deque.找到回答這篇的答案
10/05 16:27, 38F
→
10/05 16:27, , 39F
10/05 16:27, 39F
→
10/05 16:28, , 40F
請用sort關鍵字去搜尋.之後就會看到作者的測試數據
10/05 16:28, 40F
→
10/05 16:29, , 41F
此外,我是覺得要測試的話,不要用release.有點沒意義
10/05 16:29, 41F
→
10/05 16:29, , 42F
他會最佳化的是asm那部分. 那就跟演算法脫鉤了
10/05 16:29, 42F
‣ 更多 pracinverse 的文章
文章代碼(AID): #1EYwQfKH (C_and_CPP)
討論串 (同標題文章)
本文引述了以下文章的的內容：
以下文章回應了本文：
完整討論串 (本文為第 2 之 3 篇)：
排序： 最新先 | 最舊先 | 留言數
在新視窗開啟完整討論串 (共3篇)
‣ 更多 pracinverse 的文章
文章代碼(AID): #1EYwQfKH (C_and_CPP)