高效地排序許多字符串並行演示

Question

我遇到一個問題，我有一個海量信息列表（287,843項）必須排序顯示。哪個更有效率，使用自組織的紅黑二叉樹來保持排序或構建數組然後排序？我的鑰匙是字符串，如果有幫助的話。該算法應該使用多個處理器核心。

謝謝！

Answer 1

這真的取決於你的設置的細節。如果您有多核計算機，則可以使用parallel version of quicksort來非常快速地對字符串進行排序，其中每個遞歸調用與其他調用並行執行。有了很多內核，這可以使用已經快速的快速排序並使其速度更快。其他排序算法（如合併排序）也可以並行化，但並行快速排序具有需要較少額外內存的優勢。既然你知道你在排序字符串，你可能也想看看parallel radix sort，這可能會非常快。

大多數二叉搜索樹不能輕易實現多線程化，因爲重新平衡操作通常需要一次更改樹的多個部分，因此平衡紅/黑樹可能不是最好的方法。但是，您可能希望查看concurrent skiplist，這是一種可以並行高效工作的數據結構。有一些更新的二進制搜索樹設計用於並行性，有時甚至勝過跳過列表（here is one such data structure），但我預計現有的實現和這些較新的結構的討論將會減少。

如果元素沒有頻繁變化，或者你只需​​要排序一次，那麼只用一次並行快速排序就可能是最好的選擇。如果元素頻繁變化，那麼像並行跳過列表這樣的併發數據結構可能會是更好的選擇。

希望這會有所幫助！

Answer 2

假設您正在從文件或某個其他數據源讀取該列表，將所有內容讀入數組，然後對其進行排序似乎是正確的。如果您擁有某種圖形用戶界面，則在GUI中處於「等待完成」狀態時，在線程中進行讀取和排序似乎更加可行。只有當你要做大量的刪除/插入操作時，保持值的樹纔是可行的，這會使數組在這種情況下更少用。

說到多核排序，我認爲合併排序是最容易並行化的。但是，在我看來，這不是專家，所以不要讓我的話得到明確的答案。