1

我想使用java的fork join模型来实现双音排序。所以这里是排序器的代码

import java.util.concurrent.RecursiveAction;

public class BitonicSortTask extends RecursiveAction
{
    private final int array[];
    private final int low;
    private final int high;
    private final int dir;

    public BitonicSortTask(int array[],int low,int high,int dir)
    {
        this.array = array;
        this.low = low;
        this.high = high;
        this.dir= dir;
    }

    @Override
    protected void compute()
    {
        if(high>1)
        {
            int temp = high/2;
            BitonicSortTask left = new BitonicSortTask(array, low, temp,1);
            BitonicSortTask right = new BitonicSortTask(array, temp+1,high,0);
            invokeAll(left, right);
            BitonicMerge(array, low, high, dir);
        }
    }

    private void BitonicMerge(int[] array,int low,int high,int dir)
    {
        if(high>1)
        {
            int temp = high/2;
            for (int i=low; i<low+temp; i++)
                compAndSwap(array,i, i+temp, dir);
            BitonicMerge(array, low, temp, dir);
            BitonicMerge(array, temp+1, high, dir);
        }
    }

    private void compAndSwap(int a[],int i,int j,int dir)
    {
        if ( (a[i] > a[j] && dir == 1)||(a[i] < a[j] && dir == 0))
        {
            int temp = a[i];
            a[i] = a[j];
            a[j] = temp;
        }
    }   
}

和主要（测试类）

import java.util.Arrays;
import java.util.concurrent.ForkJoinPool;

public class BitonicSortTest
{
    public static void main(String[] args)
    {
        int l=0;
        int h=999;
        int a[] = new int[10];
        for(int i=0; i<10; i++)
        {
            a[i] = (int) (i*Math.round(Math.random()));
        }
        BitonicSortTask task = new BitonicSortTask(a, l, h, 1);
        ForkJoinPool fjp= new ForkJoinPool();
        fjp.invoke(task);
        System.out.println(Arrays.toString(a));
    }
}

但是每当我运行这段代码时，我都会得到

Exception in thread "main" java.lang.NoClassDefFoundError: Could not 
initialize class java.util.concurrent.locks.AbstractQueuedSynchronizer$Node

能否请您告诉我造成这种情况的原因以及如何解决。

4

2 回答 2

3

问题是您将导入范围缩小到编译器没有警告您的程度。要正确使用 Fork/Join-Framework，您必须使用通配符导入。

你的类 BitonicSortTask.java 需要

import java.util.*;
import java.util.concurrent.*;

你的课程 BitonicSortTest.java 需要

import java.util.concurrent.*;

然后您的程序将正常运行。

于 2017-04-18T19:28:03.637 回答
3

问题是您的排序算法已损坏。这导致 aStackOverFlowError并且因为堆栈已用尽，这通常被误报告为ClassDefNotFoundError.

您的测试也有一个问题，它声明 h=999 应该是要排序的数组的大小（即a.length）

在修复算法时，我参考了以下示例：

算法所需的更改很简单

  1. 在计算时temp，请考虑这high是排序双方的新内容。
  2. 计算时temp使用它来计算low排序上半部分的新值。

以下类包含这些修复：

import java.util.concurrent.RecursiveAction;

public class BitonicSortTask extends RecursiveAction {

    private final int array[];
    private final int low;
    private final int high;
    private final int dir;

    public BitonicSortTask(int array[], int low, int high, int dir) {
        this.array = array;
        this.low = low;
        this.high = high;
        this.dir = dir;
    }

    @Override
    protected void compute() {
        if (high > 1) {
            int temp = high / 2;
            // from low, with a size of temp
            BitonicSortTask left = new BitonicSortTask(array, low, temp, 1);
            // from low + temp, with a size of temp
            BitonicSortTask right = new BitonicSortTask(array, low + temp, temp, 0);
            invokeAll(left, right);
            BitonicMerge(array, low, high, dir);
        }
    }

    private void BitonicMerge(int[] array, int low, int high, int dir) {
        if (high > 1) {
            // temp is the mid point, and also the new 'high' for both parts
            int temp = high / 2;
            for (int i = low; i < low + temp; i++) {
                compAndSwap(array, i, i + temp, dir);
            }
            // from low, with a size of temp
            BitonicMerge(array, low, temp, dir);
            // from low + temp, with a size of temp
            BitonicMerge(array, low + temp, temp, dir);
        }
    }

    private void compAndSwap(int a[], int i, int j, int dir) {
        if ((a[i] > a[j] && dir == 1) || (a[i] < a[j] && dir == 0)) {
            int temp = a[i];
            a[i] = a[j];
            a[j] = temp;
        }
    }
}

并为Test班级。只需检查数组的大小。

import java.util.Arrays;
import java.util.concurrent.ForkJoinPool;

public class BitonicSortTest {

    public static void main(String[] args) {
        int a[] = new int[1 << 4];
        for (int i = 0; i < a.length; i++) {
            a[i] = (int) (Math.round(100 * Math.random()));
        }
        // Don't need variables for low / hi (it's just zero and array length)
        BitonicSortTask task = new BitonicSortTask(a, 0, a.length, 1);
        ForkJoinPool fjp = new ForkJoinPool();
        fjp.invoke(task);
        System.out.println(Arrays.toString(a));
    }
}

警告

此算法仅适用于长度为 2 的幂的数组。请参阅双调排序以了解 n 不是 2 的幂。

于 2017-04-18T21:11:51.237 回答