java - 快速並行排序將無符號整數按順序排列？

我的任務是對大量無符號，64位，隨機排列的生成整數（超過5E7個元素）。至少在隨機數據的情況下，您可以指示我使用並行排序算法，該算法可能會呈現幾乎線性的加速？java - 快速並行排序將無符號整數按順序排列？

我正在使用Java，以防它在快速排序方面有什麼區別。

編輯：請注意，這個問題主要關注能夠實現接近線性加速的並行排序。（意思是，當執行內核的數量從P增長到2P，通過並行排序所花費的時間下降到55 - 計算的50％的P內核執行）

2012-03-20 coderodde

你想實施或已經實施的東西？以前，可能是合併排序？ – Nim 2012-03-20 15:01:56

順便說一句 - 這個問題可能會有所幫助：http://stackoverflow.com/questions/2210185/correctly-multithreaded-quicksort-or-mergesort-algo-in-java – Nim 2012-03-20 15:02:57

當搜索更好的性能，它可能是有用的知道什麼樣的表現你現在有，你的目標是什麼。你可以在「Arrays.sort（）」花費多長時間後發佈一些數字，並且你想達到什麼樣的速度？ – 2012-03-20 15:04:03

那麼，如果你有很多內存可以使用Bucketsort。另一種算法與並行順利是Quicksort

來源

2012-03-20 15:02:18 nist

從上Quicksort維基百科的文章，

像歸併排序，快速排序，也可以由於並行其分而治之的性質。單獨的就地分區操作難以並行化，但是一旦被分割，列表的不同部分可以被並行排序。下面是一個簡單的的方法：如果我們有處理器，我們可以在O（n）平均時間內將元素列表劃分爲子列表，然後在平均時間中對這些列表中的每一個進行排序。忽略O（n）預處理和合並時間，這是線性加速。如果拆分是盲目的，忽略這些值，合併天真地花費O（n）。如果基於連續的的拆分分區發揮重要作用，那麼並行化並且天真地花費O（n）是非常棘手的。給定 O（log n）或更多處理器，總體上只需要O（n）時間，，而具有線性加速的方法將總體上達到O（log n）時間。

很明顯mergesort是另一種選擇。我認爲快速排序提供更好的平均情況下的性能。

來源

2012-03-20 15:02:33 smessing

快速排序和合並排序都很容易並行化。 Oracle有一個基於分叉/連接的整數合併排序here，您可以使用它（如果不是那樣，那麼至少可以作爲靈感）。

來源

2012-03-20 15:03:04 gustafc

這些「容易並行化」的Merge-/Quicksort版本是「天真」並行的，因爲它們各自的Merge-/Partition例程畢竟是串行，並且不會根據我的測試提供良好的結果。 – coderodde 2012-03-20 15:13:44

假設你有幾臺電腦（amazon集羣上的5臺電腦吧？），你想要升序排序。將你的數組拆分成更小的塊，以便它適合每臺機器。假設你有n個塊/數組。讓每臺機器快速調整其大塊。這種排序將並行（或多或少取決於塊大小和機器速度等）。

當完成sorintg時，讓機器合併大塊;在一個時間（你建立一個合併樹）

2機：

您可以通過兩種方式做到這一點。合併將再次平行進行。問題是數組將因合併而變大，並且必須緩存到磁盤，因此當您再次合併時，機器會從磁盤讀取數據。所以一些懲罰在這裏。
您一次可以做n臺機器。有一臺協調器機器可以從所有其他機器的陣列中獲取最小值。通過這種方式，協調器機器通過從每個其他排序數組中獲取最小數量來構建整個排序後的數組。

來源

2012-03-20 15:10:38 Adrian

Bitonic sort是針對並行機器的算法。這裏有一個sequential Java version和一個parallel C++ version來幫助你開始。

來源

2012-04-28 18:17:23 shams

java - 快速並行排序將無符號整數按順序排列？

回答

相關問題