您好，我正在尝试对各种排序算法进行微基准测试，但 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 基准测试显示的时间非常接近其他算法。在基准测试中，当使用 jmh 进行测试时，JDK 排序非常快，并且与其他具有天真的纳米时间基准测试的算法一致。我在这里做错了什么还是错过了什么？这是我的快速排序算法：
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/