多線程合併排序

Question

有人可以給我一個鏈接或提供給我一個多線程合併排序的java代碼嗎？

最好使用執行者！

非常感謝！

Answer 1

我建議多線程mergesort與常規mergesort非常相似，但是，當遞歸調用mergesort列表的每一半時，請設置您的算法以在新線程中調用每個合併。然後您可以等到兩個線程都完成後，再將兩個列表合併在一起，然後返回。簡單！

你說在你的問題中，你想使用Executor - 我建議java.util.concurrent包將用於此，特別是Future界面。

資源：

• Mergesort
• Java Threads
• Concurrent Programming with J2SE 5.0

Answer 2

這裏是使用Java7 ForkJoin框架的一個示例： http://www.ibm.com/developerworks/java/library/j-jtp03048.html

您可以通過使用測試版在這裏使用的Java6這個框架： http://gee.cs.oswego.edu/dl/concurrency-interest/

Answer 3

這是我用2個線程歸併的版本，它可以很容易地擴展到n個線程（只是分割原始陣列分成n子陣列）。對於一千萬個數字，它比單線程數據快25％左右。

import java.util.Random; 

public class MergeSortThreaded { 

    public static void finalMerge(int[] a, int[] b) { 
     int[] result = new int[a.length + b.length]; 
     int i=0; 
     int j=0; 
     int r=0; 
     while (i < a.length && j < b.length) { 
      if (a[i] <= b[j]) { 
       result[r]=a[i]; 
       i++; 
       r++; 
      } else { 
       result[r]=b[j]; 
       j++; 
       r++; 
      } 
      if (i==a.length) { 
       while (j<b.length) { 
        result[r]=b[j]; 
        r++; 
        j++; 
       } 
      } 
      if (j==b.length) { 
       while (i<a.length) { 
        result[r]=a[i]; 
        r++; 
        i++; 
       } 
      } 
     } 
    } 

    public static void main(String[] args) throws InterruptedException { 
     Random rand = new Random(); 
     int[] original = new int[10000000]; 
     for (int i=0; i<original.length; i++) { 
      original[i] = rand.nextInt(1000); 
     } 

     long startTime = System.currentTimeMillis(); 
     int[] subArr1 = new int[original.length/2]; 
     int[] subArr2 = new int[original.length - original.length/2]; 
     System.arraycopy(original, 0, subArr1, 0, original.length/2); 
     System.arraycopy(original, original.length/2, subArr2, 0, original.length - original.length/2); 

     Worker runner1 = new Worker(subArr1); 
     Worker runner2 = new Worker(subArr2); 
     runner1.start(); 
     runner2.start(); 
     runner1.join(); 
     runner2.join(); 
     finalMerge (runner1.getInternal(), runner2.getInternal()); 
     long stopTime = System.currentTimeMillis(); 
     long elapsedTime = stopTime - startTime; 
     System.out.println("2-thread MergeSort takes: " + (float)elapsedTime/1000 + " seconds"); 
    } 

} 

class Worker extends Thread { 
    private int[] internal; 

    public int[] getInternal() { 
     return internal; 
    } 

    public void mergeSort(int[] array) { 
     if (array.length > 1) { 
      int[] left = leftHalf(array); 
      int[] right = rightHalf(array); 

      mergeSort(left); 
      mergeSort(right); 

      merge(array, left, right); 
     } 
    } 

    public int[] leftHalf(int[] array) { 
     int size1 = array.length/2; 
     int[] left = new int[size1]; 
     for (int i = 0; i < size1; i++) { 
      left[i] = array[i]; 
     } 
     return left; 
    } 

    public int[] rightHalf(int[] array) { 
     int size1 = array.length/2; 
     int size2 = array.length - size1; 
     int[] right = new int[size2]; 
     for (int i = 0; i < size2; i++) { 
      right[i] = array[i + size1]; 
     } 
     return right; 
    } 

    public void merge(int[] result, int[] left, int[] right) { 
     int i1 = 0; 
     int i2 = 0; 

     for (int i = 0; i < result.length; i++) { 
      if (i2 >= right.length || (i1 < left.length && left[i1] <= right[i2])) { 
       result[i] = left[i1]; 
       i1++; 
      } else { 
       result[i] = right[i2]; 
       i2++; 
      } 
     } 
    } 

    Worker(int[] arr) { 
     internal = arr; 
    } 

    public void run() { 
     mergeSort(internal); 
    } 
} 

Answer 4

我嘗試過使用連接方法。它基本上爲每個子問題生成線程，並等待生成的線程使用連接完成。

讓我知道您的意見。

package com.kayan.dsAlgo; 

    public class MergeSorter implements Runnable{ 


private int[] arr; 
private int Size; 
private int left; 
private int right; 
private int[] resultArr ; 

public MergeSorter(int[] arr, int i, int j) { 
    this.arr = arr; 
    this.Size = arr.length; 
    //this.resultArr = new int[j-i+1]; 
    this.left = i; 
    this.right = j; 
} 



@Override 
public void run() { 

    System.out.println("Starting new thread left :"+this.left+" right "+this.right); 

    sort(); 

} 

public static void main(String[] args) { 

    int arr[] ={3,6,4,2,1,10} ; 
    MergeSorter mr = new MergeSorter(arr,0,arr.length-1); 

    Thread t = new Thread(mr); 
    t.start(); 
    //mr.run(); 

try { 
     t.join(); 
    } catch (InterruptedException e) { 
     // TODO Auto-generated catch block 
     e.printStackTrace(); 
    } 

for (int i :mr.resultArr) 
     System.out.print(i+" "); 
    //int res[]= mr.sort(0,arr.length-1); 

} 






private void sort() { 

    if(left==right && left >=0) 
    { 
     this.resultArr = new int[]{arr[left]}; 
     return; 
    } 
    if(left>right) return; 

    int rightLimit = this.left+(right-left)/2; 
    //int leftArr[] = sort(left,rightLimit); 

    MergeSorter mleft = new MergeSorter(arr,left,rightLimit); 
    Thread t1 = new Thread(mleft); 
    t1.start(); 

    int leftlimit = 1 + rightLimit;    
    //int rightArr[] = sort(leftlimit , right); 

    MergeSorter mright= new MergeSorter(arr,leftlimit,right); 
    Thread t2 = new Thread(mright); 
     t2.start(); 


     try { 
     t1.join(); 
     t2.join(); 
    } catch (InterruptedException e) { 
     // TODO Auto-generated catch block 
     e.printStackTrace(); 
    } 

     merge(mleft.resultArr,mright.resultArr); 



} 



private int[] merge(int[] left, int[] right) { 
    resultArr = new int[left.length+right.length]; 

    int r=0; 
    int i=0; 
    int j=0; 
    while(i<left.length && j <right.length) 
    { 
     if(i<left.length && j<right.length && left[i] < right[j]) 
      resultArr[r++] = left[i++]; 

     else if(j<right.length && i<left.length && right[j] < left[i]) 
      resultArr[r++] = right[j++]; 
    } 


    while(i<left.length) 
    { 
     resultArr[r++] = left[i++]; 
    }   

    while(j<right.length) 
    { 
     resultArr[r++] = right[j++]; 
    }   


    //System.out.println("resultArr "+resultArr); 
    return resultArr; 
} 



}