使用的ExecutorService以归并排序多线程版本 [英] Using ExecutorService with a multithreaded version of Merge Sort
问题描述
我在作业问题的工作，我要创建的合并排序一个多线程版本。我能实现它，但我不能够停止线程的创建。我看着使用ExecutorService的限制创建线程，但我无法弄清楚如何在我目前的code实现它。
I am working on a homework problem where I have to create a Multithreaded version of Merge Sort. I was able to implement it, but I am not able to stop the creation of threads. I looked into using an ExecutorService to limit the creation of threads but I cannot figure out how to implement it within my current code.
下面是我目前的多线程合并排序。我们都需要实现特定的战略格局，这样是我的的sort（）方法得来的。
Here is my current Multithreaded Merge Sort. We are required to implement a specific strategy pattern so that is where my sort() method comes from.
@Override
public int[] sort(int[] list) {
int array_size = list.length;
list = msort(list, 0, array_size-1);
return list;
}
int[] msort(int numbers[], int left, int right) {
final int mid;
final int leftRef = left;
final int rightRef = right;
final int array[] = numbers;
if (left<right) {
mid = (right + left) / 2;
//new thread
Runnable r1 = new Runnable(){
public void run(){
msort(array, leftRef, mid);
}
};
Thread t1 = new Thread(r1);
t1.start();
//new thread
Runnable r2 = new Runnable(){
public void run(){
msort(array, mid+1, rightRef);
}
};
Thread t2 = new Thread(r2);
t2.start();
//join threads back together
try {
t1.join();
t2.join();
} catch (InterruptedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
merge(numbers, leftRef, mid, mid+1, rightRef);
}
return numbers;
}
void merge(int numbers[], int startA, int endA, int startB, int endB) {
int finalStart = startA;
int finalEnd = endB;
int indexC = 0;
int[] listC = new int[numbers.length];
while(startA <= endA && startB <= endB){
if(numbers[startA] < numbers[startB]){
listC[indexC] = numbers[startA];
startA = startA+1;
}
else{
listC[indexC] = numbers[startB];
startB = startB +1;
}
indexC++;
}
if(startA <= endA){
for(int i = startA; i < endA; i++){
listC[indexC]= numbers[i];
indexC++;
}
}
indexC = 0;
for(int i = finalStart; i <= finalEnd; i++){
numbers[i]=listC[indexC];
indexC++;
}
}
任何指针将受到欢迎。
Any pointers would be gratefully received.
推荐答案
继@ mcdowella的评论，我也觉得fork / join框架是你最好的选择，如果你想限制并行运行的线程数。
Following @mcdowella's comment, I also think that the fork/join framework is your best bet if you want to limit the number of threads that run in parallel.
我知道，这不会给你的功课任何帮助，因为你可能不能使用fork / join框架中java7目录。然而，它是要学习的东西，是不是;？）
I know that this won't give you any help on your homework, because you are probably not allowed to use the fork/join framework in Java7. However it is about to learn something, isn't it?;)
由于我评论，我觉得您的合并方法是错误的。我不能精确定位的失败，但我已经改写了。我强烈建议你写一个测试用例的所有边缘的情况下，可以认为合并方法的过程中发生的，如果你确认它的工作原理，植物就回到你的多线程code。
As I commented, I think your merge method is wrong. I can't pinpoint the failure, but I have rewritten it. I strongly suggest you to write a testcase with all the edge cases that can happen during that merge method and if you verified it works, plant it back to your multithreaded code.
@lbalazscs也给你的提示，叉/加入排序中提到的javadoc，但是我没有别的事情做 - 那么我会告诉你的解决方案，如果你有java7目录来实现它。
@lbalazscs also gave you the hint that the fork/join sort is mentioned in the javadocs, however I had nothing else to do- so I will show you the solution if you'd implemented it with Java7.
public class MultithreadedMergeSort extends RecursiveAction {
private final int[] array;
private final int begin;
private final int end;
public MultithreadedMergeSort(int[] array, int begin, int end) {
this.array = array;
this.begin = begin;
this.end = end;
}
@Override
protected void compute() {
if (end - begin < 2) {
// swap if we only have two elements
if (array[begin] > array[end]) {
int tmp = array[end];
array[end] = array[begin];
array[begin] = tmp;
}
} else {
// overflow safe method to calculate the mid
int mid = (begin + end) >>> 1;
// invoke recursive sorting action
invokeAll(new MultithreadedMergeSort(array, begin, mid),
new MultithreadedMergeSort(array, mid + 1, end));
// merge both sides
merge(array, begin, mid, end);
}
}
void merge(int[] numbers, int startA, int startB, int endB) {
int[] toReturn = new int[endB - startA + 1];
int i = 0, k = startA, j = startB + 1;
while (i < toReturn.length) {
if (numbers[k] < numbers[j]) {
toReturn[i] = numbers[k];
k++;
} else {
toReturn[i] = numbers[j];
j++;
}
i++;
// if we hit the limit of an array, copy the rest
if (j > endB) {
System.arraycopy(numbers, k, toReturn, i, startB - k + 1);
break;
}
if (k > startB) {
System.arraycopy(numbers, j, toReturn, i, endB - j + 1);
break;
}
}
System.arraycopy(toReturn, 0, numbers, startA, toReturn.length);
}
public static void main(String[] args) {
int[] toSort = { 55, 1, 12, 2, 25, 55, 56, 77 };
ForkJoinPool pool = new ForkJoinPool();
pool.invoke(new MultithreadedMergeSort(toSort, 0, toSort.length - 1));
System.out.println(Arrays.toString(toSort));
}
请注意，您的线程池的建设活动并行的线程数限制为你的处理器的内核数量。
Note that the construction of your threadpool limits the number of active parallel threads to the number of cores of your processor.
ForkJoinPool pool = new ForkJoinPool();
据它的Javadoc：
According to it's javadoc:
创建一个具有并行性等于ForkJoinPool java.lang.Runtime.availableProcessors，使用默认的线程 工厂，没有UncaughtExceptionHandler的，和非异步后进先出处理 模式。
Creates a ForkJoinPool with parallelism equal to java.lang.Runtime.availableProcessors, using the default thread factory, no UncaughtExceptionHandler, and non-async LIFO processing mode.
还要注意如何我的合并方法不同于你的，因为我觉得那是你的主要问题。至少你的分拣工作，如果我用我代替你的合并方法。
Also notice how my merge method differs from yours, because I think that is your main problem. At least your sorting works if I replace your merge method with mine.
这篇关于使用的ExecutorService以归并排序多线程版本的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
