什麼是從並行轉換到順序評估的乾淨方式？

Question

在分而治之算法，是有意義的劃分問題件發送到獨立的線程，如果

1. 每一塊足夠大且
2. 有尚未運行非常多的線程。

簡單的例子：在歸併排序，給出50000000元素的列表，它是有道理的上半年發送給一個線程，第二到另一個，等過幾次，但在某些時候（大概過在一臺典型的PC上最多四次分裂，我會想象），線程開銷超過任何收益。編寫代碼以實現從分裂線程轉換到不這樣做的最佳方式是什麼？

Answer 1

「將前半部分發送到一個線程而將第二部分發送到另一個線程是有意義的」 - 否，因爲每個線程的確切時間可能會有所不同。結果，一個線程完成，然後單獨繼續，從而降低並行性。

所以要求是：

1. 每一塊足夠大並有許多人，讓處理器的負載平衡

2. 不會有非常多線程運行，但因爲很多線程只消耗內存，不會提高性能。

因此，工件數！=線數。這意味着應該使用線程池。將工作分解成塊是獨立於選擇線程池的大小。一塊越大，切換越少，但平衡性越差。根據經驗，應該有> 100個，每個執行1到1000毫秒。線程池的一側是可用處理器的數量，如果工作做I/O，則乘以某個因子。

Answer 2

您正面臨的問題可以通過使用Java的Fork/Join Framework來解決。 Here is an example。 ForkJoinPool不會產生許多線程，而是在有些人正在等待時重用它們。 FJP的創建正是爲了解決分歧和征服問題。