0

我正在尝试使用多线程实现 Mergesort 的一个版本。首先，我知道这里有十亿个线程（给予或接受......），我读过一些无济于事！我试图证明并行使用线程可以加快进程。然而，我遇到的问题是我的代码没有显示和加速，事实上，恰恰相反。

用一根线，我的时间是几十万。用两个，我的时间增加到几十万，然后用 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
}
4

2 回答 2

2

最好使用 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;
于 2013-12-29T06:02:49.903 回答
0

这里有一些有效的代码。

public class TestMergeSort{

    public static void main(String[] args){

        // Threaded merge sort (and printing)
        int[] toSort = {191,2,3,5,6,7,5,3,21,3,4};
        printArr(toSort);  
        concurrentMergeSort(toSort); 
        printArr(toSort);  
    }

    public static void concurrentMergeSort(int[] toSort){
        int[] tmpArray = new int[toSort.length];

        try{
            // Start the mergesort
            ConcurrentMergeSort sort = new ConcurrentMergeSort(toSort, tmpArray, 0, toSort.length - 1);
            sort.start();
            sort.join();

        } catch(InterruptedException e){
            e.printStackTrace();
        }

    }

    public static void printArr(int[] a){
        for(int i = 0; i < a.length; i++){
            System.out.print(a[i] + " ,");
        }
        System.out.println();
    }
}



public class ConcurrentMerge extends Thread{
    private int[] a;
    private int[] tmpArray;
    private int leftPos;
    private int rightPos;
    private int rightEnd;

    public ConcurrentMerge(int[] a, int[] tmpArray, int leftPos, int rightPos, int rightEnd){
        this.a = a;
        this.tmpArray = tmpArray;
        this.leftPos = leftPos;
        this.rightPos = rightPos;
        this.rightEnd = rightEnd; 
    }

    public void run(){
        int leftEnd = rightPos - 1;
        int tmpPos  = leftPos;
        int numElements = rightEnd - leftPos + 1;

        // Main loop
        while( leftPos <= leftEnd && rightPos <= rightEnd )
            if( a[ leftPos ] <= a[ rightPos ] )
                tmpArray[ tmpPos++ ] = a[ leftPos++ ];
            else
                tmpArray[ tmpPos++ ] = a[ rightPos++ ];

        // Copy rest of the left half
        while( leftPos <= leftEnd )  
            tmpArray[ tmpPos++ ] = a[ leftPos++ ];

        // Copy rest of the right half
        while( rightPos <= rightEnd ) 
            tmpArray[ tmpPos++ ] = a[ rightPos++ ];

        // Copy tmpArray back
        for( int i = 0; i < numElements; i++){
            a[ rightEnd ] = tmpArray[ rightEnd-- ];
        }
    }

}


import java.util.Arrays;

public class ConcurrentMergeSort extends Thread{

    private int[] a;
    private int[] tmpArray;
    private int left;
    private int right;

    public ConcurrentMergeSort(int[] a, int[] tmpArray, int left, int right){
        this.a = a;
        this.tmpArray = tmpArray;
        this.left = left;
        this.right = right; 
    }

    public void run(){
        if(this.left < this.right){
            try{
                int center = ( this.left + this.right ) / 2;
                ConcurrentMergeSort p = new ConcurrentMergeSort(this.a, this.tmpArray, this.left, center);
                ConcurrentMergeSort q = new ConcurrentMergeSort(this.a, this.tmpArray, center + 1, this.right);
                ConcurrentMerge r = new ConcurrentMerge(this.a, this.tmpArray, this.left, center + 1, this.right);

                // Sort
                p.start();
                q.start();
                p.join();
                q.join();

                // Merge
                r.start();
                r.join();
            }
            catch(InterruptedException e){
                e.printStackTrace();
            }
        }
    }

    public int[] getA(){
        return this.a;
    }

}
于 2014-05-14T21:56:47.353 回答