java - 合并排序算法在多线程上速度较慢

Question

对于我的类(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++;
    }
}

}

Answer 1

你犯了两个基本错误:

• 首先是线程的创建，创建线程在时间上是昂贵的，因此最好使用线程池或标准java api:ExecutorService .

• 另一个基本错误是您使用的线程数量，当您进行递归调用时，您不断增加处理器中的线程数量，您必须意识到，从一定数量的线程开始，工作并没有真正并行化，因为处理器没有足够的内核来同时执行这项工作，但是多线程管理引入的过载确实会降低性能。

这个答案可以帮助您了解如何利用多线程:Multithreaded merge sort, adding additional threads