JAva fork/joinフレームワークの下での集計並べ替えと高速並べ替え
4722 ワード
前言 Fork/JoinフレームワークはJava 7が提供する同時実行タスクのためのフレームワークであり、その主な思想は大タスクをいくつかの小タスクに分割し、最終的に各小タスクの結果をまとめて大タスクの結果を得るフレームワークである. データ構造に精通している友人は、その集計ソートも同様の考え方であることをすぐに考えることができるかもしれないので、fork/joinフレームワークで並列(単一CPU下では同時)の集計ソートを実現できるかどうかを自然に考え、この考えに基づいて、ついでにソートアルゴリズムを書いた.
集計ソート 次はコード です.実は上のこのコードはまだ多くの問題があります.例えば、結果を返さないタスクに使用して、RecursiveActionを継承したほうがいいですが、初めての試みなので、置いておきましょう.
クイックソート実際に考えてみると、早列もfork/joinフレームワークで実現できるようです. 次はコード です.
集計ソート
public class MergeSortTask extends RecursiveTask{
// task RecursiveAction
private int[] array;
private int left;
private int right;
public static void main(String[] args) {
int[] a = {4,2,1,4,7,5,3,8,2,7,1,78,89,6,5,4,8,5};
ForkJoinPool forkJoinPool = new ForkJoinPool();
MergeSortTask task = new MergeSortTask(a, 0, a.length-1);
Future result = forkJoinPool.submit(task);
try {
result.get();
for (int n : a) {
System.out.print(n + " ");
}
} catch (InterruptedException e) {
e.printStackTrace();
} catch (ExecutionException e) {
e.printStackTrace();
}
}
public MergeSortTask(int[] array, int left, int right) {
this.array = array;
this.left = left;
this.right = right;
}
@Override
protected Void compute() {
boolean isNeedSplit = right - left >= 1;
if (isNeedSplit) {
int mid = (left + right)/2;
MergeSortTask mergeSortTask1 = new MergeSortTask(array, left, mid);
MergeSortTask mergeSortTask2 = new MergeSortTask(array, mid+1, right);
mergeSortTask1.fork();
mergeSortTask2.fork();
mergeSortTask1.join();
mergeSortTask2.join();
merge(array, left, mid, right);
}else {
int mid = (left+right)/2;
merge(array, left, mid, right);
}
return null;
}
public static void merge(int a[], int left, int mid, int right) {
int len = right - left + 1;
int temp[] = new int[len];
int i = left;
int j = mid + 1;
int index = 0;
while(i<=mid && j <= right) {
temp[index++] = a[i] <= a[j] ? a[i++] : a[j++];
}
while (i <= mid) {
temp[index++] = a[i++];
}
while (j<=right) {
temp[index++] = a[j++];
}
for (int k = 0; k クイックソート
public class QuickSortTask extends RecursiveAction{
private int[] array;
private int left;
private int right;
public QuickSortTask(int[] array, int left, int right) {
this.array = array;
this.left = left;
this.right = right;
}
@Override
protected void compute() {
int pivot = partition(array, left, right);
QuickSortTask task1 = null;
QuickSortTask task2 = null;
if (pivot - left > 1) {
task1 = new QuickSortTask(array, left, pivot-1);
task1.fork();
}
if (right - pivot > 1) {
task2 = new QuickSortTask(array, pivot+1, right);
task2.fork();
}
if (task1 != null && !task1.isDone()) {
task1.join();
}
if (task2 != null && !task2.isDone()) {
task2.join();
}
}
public static int partition(int[] a, int left, int right) {
int pivot = a[left];
while (left < right) {
while (left < right && a[right] >= pivot) {
right--;
}
swap(a, left, right);
while (left < right && a[left] <= pivot) {
left++;
}
swap(a, left, right);
}
return left;
}
public static void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
public static void main(String[] args) {
int[] a = {4,2,1,4,7,5,3,8,2,7,1,78,89,6,5,4,8,5};
ForkJoinPool forkJoinPool = new ForkJoinPool();
QuickSortTask task = new QuickSortTask(a, 0, a.length-1);
Future result = forkJoinPool.submit(task);
try {
result.get();
for (int n : a) {
System.out.print(n + " ");
}
} catch (InterruptedException e) {
e.printStackTrace();
} catch (ExecutionException e) {
e.printStackTrace();
}
}
}