4

こんにちは、さまざまな並べ替えアルゴリズムをマイクロベンチマークしようとしていますが、jmh とベンチマークのクイックソートで奇妙な問題が発生しました。私の実装に何か問題があるのか​​もしれません。誰かが問題がどこにあるのかを知るのを手伝ってくれたら、私は興味があります. まず、jdk 7 と jmh 0.9.1 で ubuntu 14.04 を使用します。ベンチマークを実行しようとする方法は次のとおりです。

@OutputTimeUnit(TimeUnit.MILLISECONDS)
@BenchmarkMode(Mode.AverageTime)
@Warmup(iterations = 3, time = 1)
@Measurement(iterations = 3, time = 1)
@State(Scope.Thread)
public class SortingBenchmark {

private int length = 100000;

private Distribution distribution = Distribution.RANDOM;

private int[] array;

int i = 1;

@Setup(Level.Iteration)
public void setUp() {
    array = distribution.create(length);
}

@Benchmark
public int timeQuickSort() {
    int[] sorted = Sorter.quickSort(array);
    return sorted[i];
}

@Benchmark
public int timeJDKSort() {
    Arrays.sort(array);
    return array[i];
}

public static void main(String[] args) throws RunnerException {
    Options opt = new OptionsBuilder().include(".*" + SortingBenchmark.class.getSimpleName() + ".*").forks(1)
            .build();

    new Runner(opt).run();
}
}

他のアルゴリズムもありますが、多かれ少なかれ問題ないので省略しました。何らかの理由でクイックソートが非常に遅くなりました。時間の大きさが遅くなります！さらに、StackOverflowException なしで実行するには、より多くのスタック スペースを割り当てる必要があります。何らかの理由で、クイックソートは多くの再帰呼び出しを行っているようです。興味深いことに、メイン クラスでアルゴリズムを単純に実行すると、正常に実行されます (同じランダム分布と 100000 要素で)。スタックを増やす必要はなく、単純な nanotime ベンチマークは、他のアルゴリズムに非常に近い時間を示しています。また、JDK のベンチマークでは、jmh を使用してテストすると非常に高速であり、単純なナノタイム ベンチマークを使用した他のアルゴリズムに沿ってはるかに高速です。私はここで何か間違ったことをしていますか、それとも何かを見逃していますか? これが私のクイックソートアルゴリズムです：

public static int[] quickSort(int[] data) {
    Sorter.quickSort(data, 0, data.length - 1);
    return data;
}
private static void quickSort(int[] data, int sublistFirstIndex, int sublistLastIndex) {
    if (sublistFirstIndex < sublistLastIndex) {
        // move smaller elements before pivot and larger after
        int pivotIndex = partition(data, sublistFirstIndex, sublistLastIndex);
        // apply recursively to sub lists
        Sorter.quickSort(data, sublistFirstIndex, pivotIndex - 1);
        Sorter.quickSort(data, pivotIndex + 1, sublistLastIndex);
    }
}
private static int partition(int[] data, int sublistFirstIndex, int sublistLastIndex) {
    int pivotElement = data[sublistLastIndex];
    int pivotIndex = sublistFirstIndex - 1;
    for (int i = sublistFirstIndex; i < sublistLastIndex; i++) {
        if (data[i] <= pivotElement) {
            pivotIndex++;
            ArrayUtils.swap(data, pivotIndex, i);
        }
    }
    ArrayUtils.swap(data, pivotIndex + 1, sublistLastIndex);
    return pivotIndex + 1; // return index of pivot element
}

これで、ピボットを選択したために、既に並べ替えられたデータに対してアルゴリズムを実行すると、アルゴリズムが非常に遅くなることがわかりました (O(n^2))。しかし、それでもランダム化されたもので実行し、メインメソッドでソートされたデータで実行しようとしても、ランダム化されたデータで jmh を使用したバージョンよりもはるかに高速でした。ここで何かが欠けていると確信しています。ここで他のアルゴリズムを含む完全なプロジェクトを見つけることができます: https://github.com/ignl/SortingAlgos/

4

1 に答える 1