Re: [問題] deque vs vector
※ 引述《pracinverse (改)》之銘言：
: ※ 引述《pracinverse (改)》之銘言：
: : STL源碼剖析提到deque的複雜度較vector高，所以使用Algorithm 的sort()時，vector會比較怏。
: : 可是我使用VC2005測試發現，deque 使用sort()反而比Vector快，這是為什麼呢？
: 我換用vc++ 2008 express，結果還是一樣，
: vector所花的時間比較久
恕刪。
往下說之前，我希望你能知道「編譯參數」是幹嘛的，
簡而言之，它是告訴你手邊的 compiler ，我的原始碼請幫我做過
「xxxx」程序的動作，再生成執行檔，其中 「xxxx」有很多可能含義
最快速度 最小空間 完全不優化
加快浮點運算(較不準確) 產生asm
這些都有可能，就看編譯參數是怎麼下的，慶幸的是，
VC 這部份做得很讚，Alt + F7, 切到「組態屬性」-> 「C/C++」，
幾乎所有編譯時之相關參數都在裡面。
上一帖推文中雖給了很多實際數據，我想提一下為何會有此情況發生，
不確定是否所有 compiler 實際上都是這麼做，但就我所知 VS 它是這麼做。
以下討論之範圍，暫定此份 source code
http://codepad.org/raJwLlUT
---
一般而言，在 VC 之 IDE 底下，會有分 Debug / Release 專案模式，
除了預設之編譯參數不同外
( 編譯參數可以講很久，最大差別在於 Debug 專案模式較以穩建式的開發，
所有的優化功能都關掉，也多做了一些檢查的動作。 )
最大的差別在於，執行時，調用之動態連結檔 (.dll) 不一樣，
以 VC 2008 而言，上述程式碼於 debug mode 用到之 dll 為
ntdll.dll kernel32.dll msvcp90d.dll msvcr90d.dll
而在 release mode 底下,常用之兩個動態連結檔為
ntdll.dll kernel32.dll msvcp90.dll msvcr90.dll
於是在函式在執行速度上會有所差異。而你測得的結果，只能說明了，
在 debug mode , 不開任何優化情況下, deque sort 速度小勝 vector sort 速度；
在 vc release mode 預設編譯參數下 (有開o2),
vector sort 速度 大勝 deque sort 速度 (應算是大勝吧 ?)。
這是我手邊環境測得之結果 http://ppt.cc/iXik , 但 , 它的確也只能供參考。
因不同 compiler , 出來的結果未必會一模一樣, 甚至糟一點的狀況是 (不是此狀況),
在 A compiler, method 1 > method 2;
在 B compiler, method 2 > method 1;
還有更糟的嗎？有，在同一個 compiler 底下，即使都關了優化(或同時開啟優化)，
method1 ?? method2 效率上並不明顯有所差異，意即效率都關係著參數怎麼下，
這也是為何一些在講究一點點點點效率差異的文章，必須列出編譯參數之因。
至於其它的東西，實在與 compiler 本身實做與本質有太大之影響，
於此不再深入探討。
希望上述解釋，能解決您的問題。
若發表有誤，或其他意見，也請各位版友不吝指教，
謝謝收聽。
--
No matter how gifted you are,
alone, can not change the world.
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 180.177.78.41
推
10/05 11:23, , 1F
10/05 11:23, 1F
推
10/05 14:31, , 2F
10/05 14:31, 2F
→
10/05 14:32, , 3F
10/05 14:32, 3F
→
10/05 14:34, , 4F
10/05 14:34, 4F
Service Pack 是泛指 SP1 嗎 ? 若是的話, SP1 ，
較像是 extension library 、原版 IDE 外掛，
除非 SP1 有改到 CL.exe 或 LINK.exe , 否則不太可能編出來不一樣，
頂多就再多了幾個不同 .dll 而已。
另我以為在早期 vc6 即使很多 bug, 乃受到愛戴的原因,
其中一個便是因為它 opt. 在當時做得夠快！
→
10/05 14:39, , 5F
10/05 14:39, 5F
推
10/05 14:41, , 6F
10/05 14:41, 6F
推
10/05 14:57, , 7F
10/05 14:57, 7F
→
10/05 14:58, , 8F
10/05 14:58, 8F
→
10/05 14:59, , 9F
10/05 14:59, 9F
→
10/05 15:13, , 10F
10/05 15:13, 10F
→
10/05 15:15, , 11F
10/05 15:15, 11F
→
10/05 15:16, , 12F
10/05 15:16, 12F
→
10/05 15:18, , 13F
10/05 15:18, 13F
→
10/05 15:18, , 14F
10/05 15:18, 14F
→
10/05 15:22, , 15F
10/05 15:22, 15F
→
10/05 15:23, , 16F
10/05 15:23, 16F
→
10/05 15:23, , 17F
10/05 15:23, 17F
→
10/05 16:14, , 18F
10/05 16:14, 18F
→
10/05 16:14, , 19F
10/05 16:14, 19F
→
10/05 16:15, , 20F
10/05 16:15, 20F
→
10/05 16:15, , 21F
10/05 16:15, 21F
其實優化能改善的真算的不多，而且每家做 optimize 有限，畢竟都是從 asm 下去著手,
換個角度想，當然不會建議每個 compiler 、 每個參數都去跑，畢竟語言能差的,
效率比不到 100% , 差個 30~50 % 就差很多 , 再差多一點也多不過 5 倍,
但演算法動不動就差了幾百、幾千、幾萬倍，故較少人在比較這部份吧？
開發都以穩健為基礎 (所以通常穩健型的開發是用 debug mode 居多),
但程式發佈給別人如果還用 debug , 另一個人拿到快100倍的 release mode,
這可能誰都會心情不好唷.. 一樣的價, 為什麼別人的程式快了一百倍..
※ 編輯: tropical72 來自: 180.177.78.41 (10/05 17:37)
→
10/05 18:06, , 22F
10/05 18:06, 22F
→
10/05 18:06, , 23F
10/05 18:06, 23F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 3 之 3 篇)：