执行bitonic排序时java.lang.NoClassDefFoundError

Question

我想使用java的fork join模型实现bitonic排序。这是分拣机的代码

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

你能告诉我这个的原因以及如何解决它。

Answer 1

问题是您将导入范围缩小到很多，因为编译器不会警告您。要正确使用Fork / Join-Framework，必须使用通配符导入。

您的BitonicSortTask.java类需要

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

你的BitonicSortTest.java类需要

import java.util.concurrent.*;

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

Answer 2

问题是您的排序算法被破坏了。这导致了StackOverFlowError并且由于堆栈耗尽，这经常被误报为ClassDefNotFoundError。

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

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

• FelixMüller的BitonicSorter.java
• Geeks for geeks Bitonic Sort
• Wikipedia Bitonic Sort

算法所需的更改很简单

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的数组。请参阅Bitonic sorting for n not a power of 2。