使用多线程进行合并排序 [英] Merge-sort using Multi-threading
问题描述
我尝试使用多线程并行化合并排序，这是我的代码(如果执行不当，请原谅，我不在乎程序的空间复杂性).我正在实现排序数组.我的问题是:此过程是否会真正减少对大型数组进行排序所需的时间?需要进行哪些修改才能使其高效使用?
import java.io.IOException;
import java.util.Arrays;
import java.util.Random;
import java.util.Scanner;
public class Merge {
public static int[] inputArray;
public static int[] arr1;
public static int[] arr2;
public static int[] arr3;
public static int t1_status=0;
public static int t2_status=0;
public static void main(String[] args) throws IOException{
System.out.println("Enter the length of the array");
Scanner in =new Scanner(System.in);
int arraySize=in.nextInt();
inputArray = new int[arraySize];
Random rand=new Random();
for(int i=0;i<arraySize;i++)
{
inputArray[i]=rand.nextInt(100);
}
//diving the original array into two subarrays
arr1=Arrays.copyOfRange(inputArray, 0, inputArray.length/2);
arr2=Arrays.copyOfRange(inputArray, (inputArray.length)/2,inputArray.length);
//printing the original array
System.out.print("The original array is array is ");
for(int h:inputArray)
{
System.out.println(h);
}
Thread t1=new Thread(new Runnable(){
public void run()
{
mergeSort(arr1);
System.out.println("t1 started");
}
});
Thread t2=new Thread(new Runnable(){
public void run()
{
mergeSort(arr2);
System.out.println("t2 started");
}
});
//starting threads
t1.start();
t2.start();
try {
t1.join();
t2.join();
}
catch (InterruptedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
if(t1.isAlive())
{
t1_status=1;
}
if(t2.isAlive())
{
t2_status=1;
}
t1.stop();
t2.stop();
arr3=new int[inputArray.length];
merge(arr3,arr1,arr2);//merging arr1 and arr2.At this point both arr1 and arr2 are sorted.
System.out.println("The sorted array is ");
for(int m:arr3)
{
System.out.print(m);
System.out.print(" ");
}
System.out.println(" ");
}
static void mergeSort(int[] A)
{
if (A.length > 1)
{
int q = A.length/2;
int[] leftArray = Arrays.copyOfRange(A, 0, q);
int[] rightArray = Arrays.copyOfRange(A,q,A.length);
mergeSort(leftArray);
mergeSort(rightArray);
merge(A,leftArray,rightArray);
}
}
//merge function
static void merge(int[] a, int[] l, int[] r) {
int totElem = l.length + r.length;
int i,li,ri;
i = li = ri = 0;
while ( i < totElem) {
if ((li < l.length) && (ri<r.length)) {
if (l[li] < r[ri]) {
a[i] = l[li];
i++;
li++;
}
else {
a[i] = r[ri];
i++;
ri++;
}
}
else {
if (li >= l.length) {
while (ri < r.length) {
a[i] = r[ri];
i++;
ri++;
}
}
if (ri >= r.length) {
while (li < l.length) {
a[i] = l[li];
li++;
i++;
}
}
}
}
if(t1_status==1){arr1=a;}
else if(t2_status==1){arr2=a;}
else{arr3=a;}
}
}
请参阅Collections.parallelSort()和Fork/Join框架javadoc.
足够小的数组在单线程上按传统排序，但是当足够大(我认为是8192)时，parallelSort将使用ForkJoinPool默认池(与核心数量一样多的线程)进行分治. >
仅使用2个线程可能会使速度加倍，但不会更多.
仅供参考，启动器线程也应该工作，而不仅仅是坐在那里加入.例如，它可以占用第二个线程的工作.然后只加入一次.
I tried to parallelize merge-sort using multi-threading.Here is my code (please forgive if it poorly implemented.I did not care about the space-complexity of the program). I am achieving the sorted array.My question is:Will this process actually reduce the time taken to sort an array of large size?What all modifications are needed to make it efficient and is it o any use?
import java.io.IOException;
import java.util.Arrays;
import java.util.Random;
import java.util.Scanner;
public class Merge {
public static int[] inputArray;
public static int[] arr1;
public static int[] arr2;
public static int[] arr3;
public static int t1_status=0;
public static int t2_status=0;
public static void main(String[] args) throws IOException{
System.out.println("Enter the length of the array");
Scanner in =new Scanner(System.in);
int arraySize=in.nextInt();
inputArray = new int[arraySize];
Random rand=new Random();
for(int i=0;i<arraySize;i++)
{
inputArray[i]=rand.nextInt(100);
}
//diving the original array into two subarrays
arr1=Arrays.copyOfRange(inputArray, 0, inputArray.length/2);
arr2=Arrays.copyOfRange(inputArray, (inputArray.length)/2,inputArray.length);
//printing the original array
System.out.print("The original array is array is ");
for(int h:inputArray)
{
System.out.println(h);
}
Thread t1=new Thread(new Runnable(){
public void run()
{
mergeSort(arr1);
System.out.println("t1 started");
}
});
Thread t2=new Thread(new Runnable(){
public void run()
{
mergeSort(arr2);
System.out.println("t2 started");
}
});
//starting threads
t1.start();
t2.start();
try {
t1.join();
t2.join();
}
catch (InterruptedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
if(t1.isAlive())
{
t1_status=1;
}
if(t2.isAlive())
{
t2_status=1;
}
t1.stop();
t2.stop();
arr3=new int[inputArray.length];
merge(arr3,arr1,arr2);//merging arr1 and arr2.At this point both arr1 and arr2 are sorted.
System.out.println("The sorted array is ");
for(int m:arr3)
{
System.out.print(m);
System.out.print(" ");
}
System.out.println(" ");
}
static void mergeSort(int[] A)
{
if (A.length > 1)
{
int q = A.length/2;
int[] leftArray = Arrays.copyOfRange(A, 0, q);
int[] rightArray = Arrays.copyOfRange(A,q,A.length);
mergeSort(leftArray);
mergeSort(rightArray);
merge(A,leftArray,rightArray);
}
}
//merge function
static void merge(int[] a, int[] l, int[] r) {
int totElem = l.length + r.length;
int i,li,ri;
i = li = ri = 0;
while ( i < totElem) {
if ((li < l.length) && (ri<r.length)) {
if (l[li] < r[ri]) {
a[i] = l[li];
i++;
li++;
}
else {
a[i] = r[ri];
i++;
ri++;
}
}
else {
if (li >= l.length) {
while (ri < r.length) {
a[i] = r[ri];
i++;
ri++;
}
}
if (ri >= r.length) {
while (li < l.length) {
a[i] = l[li];
li++;
i++;
}
}
}
}
if(t1_status==1){arr1=a;}
else if(t2_status==1){arr2=a;}
else{arr3=a;}
}
}
See the Collections.parallelSort() and the Fork/Join framework javadoc.
The small enough arrays are sorted as legacy on single thread, but when large enough (8192, I think), the parallelSort will divide and conquer, with the ForkJoinPool default pool (as many threads as there are cores).
Using only 2 threads is probably doubling your speed, but not more.
FYI, the launcher thread should work too, not just sit there joining. It can take the job of the 2nd thread for instance. Then only join once.
这篇关于使用多线程进行合并排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
