我正在尝试确定停止分割合并排序实现的合理阈值。
但是,我得到的结果是阈值应该在 107 < x < 108 之间,考虑到 java 使用的默认阈值,这是荒谬的大约是 8192。它基本上告诉我,分割几乎总是不好的,阈值越高越好,因为它执行的分割更少。
它当前所做的工作是对大小为 108 的 float 组进行排序,随机范围为 0
到 1000
。每个测试的阈值都重复使用相同的随机数组。
public class ParallelMergeSort extends SortStrategy {
@Override
public long sort(float[] a, int cores, int threshold) {
System.gc();
long start = System.nanoTime();
RecursiveAction mainTask = new SortTask(a, 0, a.length - 1);
SortTask.threshold = threshold;
ForkJoinPool pool = new ForkJoinPool(cores);
pool.invoke(mainTask);
return System.nanoTime() - start;
}
private static class SortTask extends RecursiveAction {
private float[] a;
private int left, right;
private static int threshold;
SortTask(float[] a, int left, int right) {
this.a = a;
this.left = left;
this.right = right;
}
@Override
protected void compute() {
if (left < right) {
if ((right - left) < threshold) {
Arrays.sort(a, left, right + 1);
} else {
int mid = (left + right)/2;
invokeAll(
new SortTask(a, left, mid),
new SortTask(a, mid + 1, right)
);
// Merge
int n1 = mid - left + 1;
int n2 = right - mid;
float a1[] = new float[n1];
float a2[] = new float[n2];
// Fill sub arrays
for (int i = 0; i < n1; ++i)
a1[i] = a[left + i];
for (int j = 0; j < n2; ++j)
a2[j] = a[mid + 1 + j];
// Sort and merge
int l = 0, r = 0, o = left;
while (l < a1.length && r < a2.length) {
if (a1[l] <= a2[r])
a[o++] = a1[l++];
else
a[o++] = a2[r++];
}
// Merge remaining
while (l < a1.length)
a[o++] = a1[l++];
while (r < a2.length)
a[o++] = a2[r++];
}
}
}
}
}
我知道由于 JIT,JVM 可能不可靠,但它应该只影响前几次迭代,不是吗?寻求有关算法的建议或为什么我的结果与我的预期相差甚远。
最佳答案
最佳阈值是允许与系统中的内核数量一样多的线程并行运行的阈值。
如果您的系统有 cores
个核心,则阈值应为 test 应初始化
SortTask.threshold = cores > 0 ? (a.length + cores - 1) / cores : a.length;
速度提升将小于核心数量,因为最后几个合并阶段无法并行运行。
由于您要对包含 108 个元素的数组进行排序,因此最佳阈值确实介于 107 和 108 之间,除非您有超过 10 个核心。
关于java - 并行合并排序基准测试 - 确定找到的阈值,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/55923017/