在多个线程中划分合并排序算法
Dividing a Merge Sort algorithm in multiple threads
我正计划构建一个在 Java 中使用多线程的合并排序算法，并且我浏览了 Internet 和 SO（例如 Multi-threading a merge sorting algorithm），但我似乎无法确定我的一些问题的答案。
首先，创建的最佳线程数是否与CPU的核心数相同？在考虑线程数时我是否应该考虑逻辑内核？
其次，在这样的算法中实现多线程的最佳方式是什么？我听说有不止一种方法可以做到这一点（比如从 "Thread" class 继承或使用实现 Runnable 等）。
此外，在这种情况下，就优化而言，使用 ArrayLists 或 LinkedLists 会是更好的选择吗？
关于实施的任何其他 notes/suggestions，我们将不胜感激。
干杯。
在 Java 8 中，有 Arrays.parallelSort() 如果您请求与 parallelStream 并行，流 API 也会使用它。如果您出于教育目的研究此内容，parallelSort 的来源应该非常有用。
...would the optimal number of threads created be the same as the number of cores of the CPU?
我想是的。合并排序应该是内存带宽限制，而不是 cpu 带宽限制。早期多线程的主要收益是利用每个内核的本地缓存，通常是 1 级和 2 级缓存。通常 3 级缓存在核心之间共享，因此如果合并过程与 3 级缓存的速度相比相对 CPU 绑定，那么唯一的好处是。一旦 运行 大小大到足以超过缓存限制，那么我不确定多线程是否能带来很多好处。
Microsoft 的 stable_sort 首先使用插入排序创建 32 个元素的排序组，可能是为了利用本地缓存。我不确定这对当前处理器是否真的有帮助，因为它基于 1994 年编写的代码。
我正计划构建一个在 Java 中使用多线程的合并排序算法，并且我浏览了 Internet 和 SO（例如 Multi-threading a merge sorting algorithm），但我似乎无法确定我的一些问题的答案。
首先，创建的最佳线程数是否与CPU的核心数相同？在考虑线程数时我是否应该考虑逻辑内核？
其次，在这样的算法中实现多线程的最佳方式是什么？我听说有不止一种方法可以做到这一点（比如从 "Thread" class 继承或使用实现 Runnable 等）。
此外，在这种情况下，就优化而言，使用 ArrayLists 或 LinkedLists 会是更好的选择吗？
关于实施的任何其他 notes/suggestions，我们将不胜感激。
干杯。
在 Java 8 中，有 Arrays.parallelSort() 如果您请求与 parallelStream 并行，流 API 也会使用它。如果您出于教育目的研究此内容，parallelSort 的来源应该非常有用。
...would the optimal number of threads created be the same as the number of cores of the CPU?
我想是的。合并排序应该是内存带宽限制，而不是 cpu 带宽限制。早期多线程的主要收益是利用每个内核的本地缓存，通常是 1 级和 2 级缓存。通常 3 级缓存在核心之间共享，因此如果合并过程与 3 级缓存的速度相比相对 CPU 绑定，那么唯一的好处是。一旦 运行 大小大到足以超过缓存限制，那么我不确定多线程是否能带来很多好处。
Microsoft 的 stable_sort 首先使用插入排序创建 32 个元素的排序组，可能是为了利用本地缓存。我不确定这对当前处理器是否真的有帮助，因为它基于 1994 年编写的代码。