使用多线程加速 Java MergeSort

Question

我正在尝试使用多线程实现合并排序的版本。首先，我知道这里有十亿条线索(给予或接受......)，而我读了一些但无济于事!我试图证明并行使用线程可以加快进程的速度。然而，我遇到的问题是我的代码没有显示和加速，事实上，恰恰相反。

对于一个线程，我的时间是几十万。如果使用 2 个线程，我的时间会增加到几十万，如果使用 4 个线程，我的时间将接近 7 位数。我最初的想法是尝试使用 join() 方法并确保它位于正确的位置，并且已经这样做了，但没有成功。

任何帮助将不胜感激，示例命令行参数类似于；

java工作16 4(对于4个线程)。

对于整个过程中缺乏评论表示歉意!

import java.util.*;

class working
{
  private static int sizeVector;
  private static int noThreads;
  static void sort(int[] input)
  {
    mergeSort(input, 0, input.length - 1, noThreads);
  }

  static void mergeSort(int[] array, int low, int high, int noThreadsUp)
  {
    //private int noThreadsUp;
    if (low < high)
    {
      int mid = (low+high)/2;
      if (noThreadsUp > 1)
      {
        NewThread td = new NewThread(array, low, mid, noThreadsUp/2);
        td.start();
        /*try{
        td.join();
        }catch(Exception e){}*/
        mergeSort(array, mid+1, high, noThreadsUp/2);
                try{
        td.join();//UNSURE WHERE THIS SHOULD BE
        }catch(Exception e){}
        merge(array, low, mid, high);

      }
      else
      {
      mergeSort(array, low, mid, noThreadsUp/2); 
      mergeSort(array, mid+1, high, noThreadsUp/2);
      merge(array, low, mid, high);
      }
    }
  }

  static void merge(int[] array, int low, int mid, int high)
  {
    int[] temp = new int[high - low + 1];
    int left = low;
    int right = mid+1;
    int k = 0;
    while (left <= mid && right <= high)
    {
      if(array[left] < array[right])
      {
        temp[k] = array[left];
        left = left+1;
      }
      else
      {
        temp[k] = array[right];
        right = right + 1;
      }
      k = k + 1;
    }
    if (left <= mid)
    {
      while(left <= mid)
      {
        temp[k] = array[left];
        left = left + 1;
        k = k + 1;
      }
    }
    else if (right <= high)
    {
      while(right <= high)
      {
        temp[k] = array[right];
        right = right + 1;
        k = k + 1;
      }
    }
    for (int m = 0; m < temp.length; m++)
    {
      array[low+m] = temp[m];

  }
}
  static int[] readInputArray()
  {

    int[] a = new int[sizeVector];
    for (int i = 0; i < sizeVector; i++)
    {
      Random generator = new Random();
      a[i] = generator.nextInt();
    }
    return a;
  }

  static void printArray(int[] array)
  {
    for(int i = 0; i<array.length; i++)
      System.out.println(array[i]);
  }

  public static void main(String[] args)
  {
    sizeVector = Integer.parseInt(args[0]);
    noThreads = Integer.parseInt(args[1]);
    int[] inputArray = readInputArray();
    System.out.println("INPUT ARRAY: ");
    printArray(inputArray);
    long startTime = System.nanoTime();
    sort(inputArray);
    long endTime = System.nanoTime();
    long finalTime = endTime - startTime;

    System.out.println("SORTED ARRAY: ");
    printArray(inputArray);      
    System.out.println("Time: " + finalTime);
  }

static class NewThread extends Thread 
  {
    private int low;
    private int mid;
    private int[] array;
    private int noThreadsDown;
    //private int threads;
    public NewThread(int[] array, int low, int mid, int noThreadsDown) 
    {
      this.low = low;//Ensure using the right start
      this.mid = mid;//Ensure using the right end
      this.array = array;
      this.noThreadsDown = noThreadsDown;
      //this.threads = threads;
    }
    public void run() 
    {

      mergeSort(array, low, mid, noThreadsDown/2);
      System.out.println(noThreadsDown);
    }
  }//End NewThread
}

Answer 1

最好使用 java 7 中的 RecurssionAcition 类，它分为左右两部分。

Sum left  = new Sum(array, low, mid);
Sum right = new Sum(array, mid, high);
left.fork();
long rightAns = right.compute();
long leftAns   = left.join();
return leftAns + rightAns;