現代機器上的合併排序優於QuickSort？

既然現代機器都是多核的，並且我們支持帶有SSE指令的Windows和Linux機器上的SIMD指令，例如，我應該切換到在我的C/C++代碼中合併排序並忘記QuickSort？理論上，這樣做的原因是合併排序會更好地並行化，並更加節省地使用內存/磁盤，因此比QuickSort的內存密集型操作更快，但我不知道。實踐經驗表明什麼？現代機器上的合併排序優於QuickSort？

我不想在每次排序時進行配置文件和測試。我想要使用一種標準方法。目前該方法是QuickSort，因爲這是默認的庫排序例程。我想知道是否有其他人切換到MergeSort並通過進行切換獲得更好的結果。

UPDATE ------------

Graham.Reeds回答How big is the performance gap between std::sort and std::stable_sort in practice?表明，上述傳言我的猜測是正確的，並切換到歸併/ stablesort可能是正確的。

來源

2012-12-12 Tyler Durden

，當然，這裏還有內省排序：http://en.wikipedia.org/wiki/Introsort – NPE

很難當談到性能一概而論。測量並觀察。 –

事情的真相與過去一樣。一切都取決於您的應用程序的數據和特定需求。這並沒有改變。 –

得到了很多非的答案後，我花了幾個小時，做我自己的研究。這樣做的結果是，是的，歸併排序（和其他相關排序）都將是顯著更快，因爲大量使用更少的內存，以及更好的並行/多核開發。此外，英特爾還有一個名爲IPP的標準高性能庫，可爲x86機器實現合併類型排序。通過切換到這個庫，它看起來像我可以大大提高排序性能（和其他向量類型操作）爲我做的編程類型。

來源

2012-12-14 00:01:01

事實是你必須自己配置文件，看看它如何運行你的應用程序，數據，環境等，這是本質上，答案是這樣的對SO的所有分析/性能/優化的問題99％。

來源

2012-12-12 15:56:13 djechlin

我不認爲有一個明確的答案。在某些情況下，可並行蠻力排序可能會更快。分析你的特殊情況總是很重要的。例如，如果您有多個內核和SIMD，請考慮雙聲道排序。

來源

2012-12-12 15:57:26 JasonD

我應該切換在我的C/C++代碼歸併排序，忘記了快速排序？

很抱歉這樣說，但這個問題聽起來像是一個嘗試過早優化。

理論上，這樣做的原因是合併排序會更好地並行化並更加節省地使用內存/磁盤，因此比QuickSort的內存密集型操作更快，但我不知道。實踐經驗表明什麼？

實際上，您應該總是首先進行分析，然後根據結果確定優化領域。

很可能您甚至可能不必更改您使用的排序算法，除非您通過足夠大的數據集來處理結果（或處理流程中足夠關鍵的區域，重要）。

我通常使用std :: sort，如果這還不夠（還沒有發生std::sort），我優化了我的應用程序流和算法。

來源

2012-12-12 16:13:43 utnapistim

有並行排序軟件包是通過在處理器核心的數量可擴展的，並且被設計以利用/在每個處理器上優化處理。我知道TBB（線程構建模塊）有一個parallel_sort函數，它是一個平均時間複雜度爲0（n log n）的比較排序。

你也可以實現一些穿入快速排序。在TBB中使用parallel_for可以輕鬆地將遞歸函數轉換爲並行性，或者您可以查看Cilk Plus，網上有很多線程示例。

來源

2012-12-12 17:34:53

現代機器上的合併排序優於QuickSort？

回答

相關問題