对于我的类(class)，我必须在多线程中实现合并排序算法，并将其时间与单线程版本进行比较。我知道它应该更快，但我得到的时间却说不然。对于大小超过 1000000 的数组，多线程版本变得更快，即使如此，也没有显着差异。 我提供我正在使用的代码。难道我做错了什么？我在多线程方面没有太多经验
public Sorter() {
public void mergeSortMultiThread(int[] array, int start, int end){
if(start < end){
// Find the middle point
int m = (start+end)/2;
Thread t1 = new Thread(() -> mergeSortSequence(array, start, m));
t1.start();
mergeSortSequence(array , m+1, end);
try {
t1.join();
} catch (InterruptedException e) {
e.printStackTrace();
}
// Merge the sorted halves
merge(array, start, m, end);
}
}
public void mergeSortSnngleThread(int[] array, int start, int end){
if(start < end){
// Find the middle point
int m = (start+end)/2;
// Sort first and second halves
mergeSortSequence(array, start, m);
mergeSortSequence(array , m+1, end);
// Merge the sorted halves
merge(array, start, m, end);
}
}
private void merge(int arr[], int l, int m, int r)
{
// Find sizes of two subarrays to be merged
int n1 = m - l + 1;
int n2 = r - m;
/* Create temp arrays */
int L[] = new int [n1];
int R[] = new int [n2];
/*Copy data to temp arrays*/
for (int i=0; i<n1; ++i)
L[i] = arr[l + i];
for (int j=0; j<n2; ++j)
R[j] = arr[m + 1+ j];
/* Merge the temp arrays */
// Initial indexes of first and second subarrays
int i = 0, j = 0;
// Initial index of merged subarry array
int k = l;
while (i < n1 && j < n2)
{
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}
/* Copy remaining elements of L[] if any */
while (i < n1)
{
arr[k] = L[i];
i++;
k++;
}
/* Copy remaining elements of R[] if any */
while (j < n2)
{
arr[k] = R[j];
j++;
k++;
}
}
}
最佳答案
你犯了两个基本错误:
首先是线程的创建，创建线程在时间上是昂贵的，因此最好使用线程池或标准java api:
ExecutorService.另一个基本错误是您使用的线程数量，当您进行递归调用时，您不断增加处理器中的线程数量，您必须意识到，从一定数量的线程开始，工作并没有真正并行化，因为处理器没有足够的内核来同时执行这项工作，但是多线程管理引入的过载确实会降低性能。
这个答案可以帮助您了解如何利用多线程:Multithreaded merge sort, adding additional threads
关于java - 合并排序算法在多线程上速度较慢，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/48445015/