0

マルチスレッドを使用して Mergesort のバージョンを実装しようとしています。まず最初に、ここには 10 億のスレッド (ギブまたはテイク...) があることを知っています。スレッドを並列に使用するとプロセスが高速化されることを示しようとしています。ただし、私が抱えている問題は、コードが表示されず、速度がまったく向上しないことです。実際には、その逆です。

1 つのスレッドで、私の時間は数万です。2 スレッドで私の時間は数十万に増加し、4 スレッドで私の時間は 7 桁に達します。私の最初の考えは、join() メソッドをいじって、それが適切な場所にあることを確認することでしたが、成功しませんでした。

コマンドライン引数の例は次のようになります。

java working 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

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 に答える