多线程JAVA排序多线程合并排序的速度
我已经在JAVA中实现了一个多线程的MergeSort,并用不同数量的线程测试了算法的运行时间。我在双核处理器上运行代码,算法在4或8个线程中运行最快。这对我来说没有意义-我有两个核心。这是我的源代码
public static void parallelMergeSort(int[] a, int NUM_THREADS)
{
if(NUM_THREADS <= 1)
{
mergeSort(a);
return;
}
int mid = a.length / 2;
int[] left = Arrays.copyOfRange(a, 0, mid);
int[] right = Arrays.copyOfRange(a, mid, a.length);
Thread leftSorter = mergeSortThread(left, NUM_THREADS);
Thread rightSorter = mergeSortThread(right, NUM_THREADS);
leftSorter.start();
rightSorter.start();
try {
leftSorter.join();
rightSorter.join();
} catch (InterruptedException e) {
e.printStackTrace();
}
merge(left, right, a);
}
private static Thread mergeSortThread(int[] a, int NUM_THREADS)
{
return new Thread()
{
@Override
public void run()
{
parallelMergeSort(a, NUM_THREADS / 2);
}
};
}
public static void mergeSort(int[] a)
{
if(a.length <= 1) return;
int mid = a.length / 2;
int[] left = Arrays.copyOfRange(a, 0, mid);
int[] right = Arrays.copyOfRange(a, mid, a.length);
mergeSort(left);
mergeSort(right);
merge(left, right, a);
}
private static void merge(int[] a, int[] b, int[] r)
{
int i = 0, j = 0, k = 0;
while(i < a.length && j < b.length)
{
if(a[i] < b[j])
r[k++] = a[i++];
else
r[k++] = b[j++];
}
while(i < a.length)
r[k++] = a[i++];
while(j < b.length)
r[k++] = b[j++];
}
我测试了使用不同数量的线程运行它,以毫秒为单位得到了以下结果:
Serial Sort Run Time: 5368.
Parallel Sort Run Time with 2 Threads: 3202.
Parallel Sort Run Time with 4 Threads: 2408.
Parallel Sort Run Time with 8 Threads: 2544.
Parallel Sort Run Time with 16 Threads: 2738.
Parallel Sort Run Time with 32 Threads: 2909.
Parallel Sort Run Time with 64 Threads: 3078.
Parallel Sort Run Time with 128 Threads: 3777.
为什么这个算法在双核cpu上有4个线程时运行得最快
# 1 楼答案
这可能只是一个拙劣基准测试的产物。例如,如果您的基准测试没有适当考虑JVM预热效应,那么结果将不可靠
除此之外,“超阅读”的解释是合理的:
资料来源:"What Intel Processors Have Hyper Threading
然而,HT(显然)在处理器上可用的事实并不意味着它实际上已启用。这将取决于BIOS设置等