如何在C＃中使用多線程實現分而治之算法？

Question

我是C＃和多線程的新手。如何在C＃中使用多線程編寫分割和征服算法（如合併排序或快速排序）的程序？

Answer 1

您可能想了解一下ThreadPool。基本上，你要做的是。創建一個是線程安全的，並執行以下步驟的方法：

1. 除以輸入數據
2. 計劃使用ThreadPool的方法
3. 無障礙等待輸入數據的每個部分新工作所有產生的線程來完成
4. 執行合併步驟

線程池將由.NET進行管理，所以你不必擔心產生新的線程和的東西，你會的，但是，NE編輯自己同步的東西。要做到這一點的一個好方法是：

1. 創建的WaitHandle S（如ManualResetEvent），您要產卵
2. 通行證等待之一，工作數據到生成的處理沿着每個線程一個條目列表螺紋（重要！沒有通過一個等待句柄兩個線程=>問題）
3. 使用WaitHandle.WaitAll等待所有等待句柄設置
4. 在線程中，在成功或錯誤
5. 設置等待句柄a之後檢查單線程的成功或錯誤ll線程已返回

但是，IIIRC，Windows上有64個等待句柄的限制，但我不太確定。你必須嘗試。

Answer 2

如果您只是想在線程環境中使用排序例程，那麼Thorsten會很好地闡述它。我建議你使用遞歸算法，因爲它已經被分解成可以傳遞給線程池的方法調用。請記住，線程池有一個限制，如果您用線程填充池，並阻止等待另一個線程變爲可用，則可以掛起應用程序。

如果您的目標是對多個內核進行排序並進行高效合併，那麼您將從並行排序算法中獲得最佳性能。快速排序和合並排序是順序的，並且由於線程開銷，即使使用線程池，也可能在多線程時實際運行速度較慢。還要注意，非遞歸排序算法比其遞歸等價算法更快，因爲所有這些方法調用都會有額外的堆棧活動。對非常大的數據集進行遞歸（線程化或非線程化）排序可能會導致堆棧崩潰。

也許你可以問社區示例應用程序的想法來學習線程。我的建議是一個網站爬蟲。很多有用的東西，從那個學習！