Q

什麼排序算法適合這種「流式」條件？

2012-03-09 77 views 5 likes

5

我有一個緩衝區接收數據，這意味着數據就像'流'，並在'IO'有延遲。我現在的做法是當緩衝區已滿時，使用qsort對緩衝區進行排序並將結果寫入磁盤。但是在執行qsort時存在明顯的延遲，所以我正在尋找其他一些排序算法，這些排序算法可能會在數據添加到緩衝區時開始排序，以減少總體消耗的時間。什麼排序算法適合這種「流式」條件？

不知道有沒有說清楚，如果需要留下任何意見，感謝

2012-03-09 Mickey Shine

+2

插入排序。真的;-)然而，「O（n lg n）」排序可以很快地對大量數據進行排序......並且如果它「大多數排序」則不一定更快（在這種情況下，快速排序實際上可能非常墮落！）。 ..所以建立一個快速的性能分析可能是值得的。 – 2012-03-09 13:39:14

A

回答

5

堆排序可將數據永久保存在部分排序條件中，因此可與插入排序相比較。但是它比O（n ）的插入排序快得多並且具有O（n log n）的最壞情況。

這是怎麼回事？據推測，在某些時候，你必須停止閱讀流，存儲你已經排序，並開始閱讀一組新的數據？

2012-03-09 13:55:37 Borodin

+0

+1堆排序，你不需要它被完全排序，以便在寫入之間進行緩衝 – 2012-03-09 15:06:39

+0

是的，在我的情況下，我必須停止從流中讀取並對緩衝區進行排序並將結果寫入磁盤，然後再次開始讀取並且重複，直到流結束 – 2012-03-09 23:48:04

+0

然後堆排序是你想要的。從流中讀取數據到堆中，直到必須停止爲止，然後從堆中讀取並寫入磁盤，直到它爲空。從堆中讀取的數據按排序順序排列。 – Borodin 2012-03-10 09:52:59

2

我認爲合併排序或樹排序可以有很大的幫助。看看why on wikipedia。

當您可以在合理的大塊中剪切大量輸入時，合併排序更合適。
當您一次插入小塊時，樹狀排序更合適。

你想要實現一個在線排序算法，即在流線型接收數據時運行的算法。通過網絡搜索online algorithms，您可能會發現其他不錯的算法。

在你的情況下，我會使用樹排序。它沒有比快速排序更好的複雜性（大多數情況下都是O(nlog n)，在很少的情況下都是O(n²)）。但它會攤銷每個輸入的成本。這意味着添加最後一個數據後，您必須等待的延遲時間不是訂單O(nlog n)，而是O(log n)

2012-03-09 13:42:44 UmNyobe

0

您可以嘗試使用我的Link Array結構。順序添加隨機數據並保持排序應該是可以的（查看錶中的數字）。這是Skip list方式的變化，但有更簡單的實現和邏輯（儘管跳躍列表的表現應該會更好）

2012-03-10 12:56:27 Maksee

相關問題