Re: [問題] deque vs vector

[tropical72 (藍影)]

※ 引述《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
推 james732:推！
推 johnhmj:除了release之外，更新VStudio的ServicePack也會有差異，
→ johnhmj:更新前與更新後編譯的程式，兩者是不一樣的。
→ johnhmj:不建議用release，它似乎是以編程人員的電腦來做優化的。
Service Pack 是泛指 SP1 嗎 ? 若是的話, SP1 ，
較像是 extension library 、原版 IDE 外掛，
除非 SP1 有改到 CL.exe 或 LINK.exe , 否則不太可能編出來不一樣，
頂多就再多了幾個不同 .dll 而已。
另我以為在早期 vc6 即使很多 bug, 乃受到愛戴的原因,
其中一個便是因為它 opt. 在當時做得夠快！

→ danielguo:release 可以選對哪種環境最佳化, debug 實在是慢到不行
推 purpose:以編程人員的電腦來做優化 -> 好像沒有吧
推 priv:怎麼可能是以編程人員的電腦為準
→ priv:用debug為了可以trace，基本上根本不會有任何高階optimize
→ priv:教人不要用release太扯了…
→ johnhmj:假如不想費時研究優化編譯選項，我覺得release玩玩就好。
→ danielguo:不, 真的在用的 code 都應該用 release. debug 純開發用
→ johnhmj:http://lmgtfy.com/?q=visual+studio+debug+release
→ danielguo:Visual Studio release 的預設並不會用奇怪的硬體設置
→ danielguo:C++ release 和 debug 速度差十倍也常有
→ danielguo:把 VS 打開進屬性頁, 請問除了 /arch 哪個選項會造成
→ danielguo:對某些處理器適用某些不適用的影響?
→ danielguo:(預設的 release)
→ priv:VS出那麼多年你有聽過微軟預設的release編出來
→ priv:結果某家CPU跑起來有問題的事嗎..
→ priv:要說的話微軟的optimize都是偏保守的
→ priv:不然以前intel也不會特別出一套ICC了
其實優化能改善的真算的不多，而且每家做 optimize 有限，畢竟都是從 asm 下去著手,
換個角度想，當然不會建議每個 compiler 、 每個參數都去跑，畢竟語言能差的,
效率比不到 100% , 差個 30~50 % 就差很多 , 再差多一點也多不過 5 倍,
但演算法動不動就差了幾百、幾千、幾萬倍，故較少人在比較這部份吧？

開發都以穩健為基礎 (所以通常穩健型的開發是用 debug mode 居多),
但程式發佈給別人如果還用 debug , 另一個人拿到快100倍的 release mode,
這可能誰都會心情不好唷.. 一樣的價, 為什麼別人的程式快了一百倍..
※ 編輯: tropical72      來自: 180.177.78.41        (10/05 17:37)
→ priv:可以milestone先給debug版然後...下一版改release
→ priv:程式變小又變快...好棒XD