为什么 JMH 报告简单的 Quicksort 如此奇怪的时间——显然与 N * log(N) 不成比例？

Question

为什么 JMH 报告简单的 Quicksort 如此奇怪的时间——显然与 N * log(N) 不成比例？

m. *_*khm 2 java quicksort time-complexity jmh

出于研究排序算法（我自己的）的意图，我决定将其性能与经典算法进行比较quicksort，令我惊讶的是，我发现我的实现所花费的时间quicksort与N log(N). 我彻底尝试在我的quicksort但没有成功。这是排序算法的一个简单版本，处理Integer不同大小的数组，填充随机数，我不知道错误可能潜入何处。我什至计算了我的代码执行的所有比较和交换，并且他们的人数与N log(N). 我完全糊涂了，无法理解我观察到的现实。以下是对包含 1,000、2,000、4,000、8,000 和 16,000 个随机值的数组进行排序的基准测试结果（使用测量JMH）：

Benchmark                       Mode  Cnt       Score     Error  Units    2N / N ratio          
QSortBenchmarks.sortArray01000  avgt    5     561.505 ±   2.992  us/op              
QSortBenchmarks.sortArray02000  avgt    5    2433.307 ±  11.770  us/op    4.334 
QSortBenchmarks.sortArray04000  avgt    5    8510.448 ±  34.051  us/op    3.497 
QSortBenchmarks.sortArray08000  avgt    5   38269.492 ± 161.010  us/op    4.497 
QSortBenchmarks.sortArray16000  avgt    5  147132.524 ± 261.963  us/op    3.845

Run Code Online (Sandbox Code Playgroud)

显然，我观察到的时间复杂度远非O(n log(n))，几乎是O(n^2)。可能有一个很小的怀疑，即随机种子非常不幸，以至于数组中的值碰巧接近最坏的情况。这个概率非常接近于 0，但不是 0。但是几个不同的随机种子的结果非常相似。

这是比较和交换的数量（对于 40 次迭代，每个大小的随机填充数组）：

                     Avr. Comparisons      Avr. Swaps                     2N / N ratio
sortArray01000():           12119.925,       2398.925             
sortArray02000():           26581.600,       5268.525                     2.193, 2.196
sortArray04000():           59866.925,      11451.625                     2.252, 2.174
sortArray08000():          127731.025,      25006.425                     2.134, 2.184
sortArray16000():          273409.925,      54481.525                     2.141, 2.179

Run Code Online (Sandbox Code Playgroud)

大家可以看到，操作的次数比较符合O(Nlog(N))规律。

甚至有可能怀疑单个操作的成本取决于我们处理的数组的大小，并且我已经检查过它是否正确（使用一个简单的方法来反转不同大小的数组） - 不是，因为意料之中，事实并非如此。时代非常接近O(n)。

我唯一能想到的是我的代码中有一些棘手的逻辑错误，但我想不通。

有谁能够帮助我？

这是代码：

import java.io.IOException;
import java.util.Locale;
import java.util.Random;
import java.util.function.Consumer;

import org.openjdk.jmh.annotations.*;
import org.openjdk.jmh.runner.Runner;
import org.openjdk.jmh.runner.RunnerException;
import org.openjdk.jmh.runner.options.Options;
import org.openjdk.jmh.runner.options.OptionsBuilder;

/**
 * Why does quicksort take time disproportionate to N * log(N)?
 * Rectified for StackOverflow
 * 21.05.17 16:20:01
 */

@State(value = Scope.Benchmark)
@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(java.util.concurrent.TimeUnit.MICROSECONDS)
@Fork(value = 2)
@Warmup(iterations = 5, time = 10)
@Measurement(iterations = 5, time = 10)
public class QSortBenchmarks {

  private static final int LOOPS_TO_ITERATE = 40; // 40;

  private static final int RAND_SEED = 123456789;
  private static final int RAND_LIMIT = 10000;
  private static final Random RAND = new Random(RAND_SEED); // Constant seed for reproducibility;

  private static int cmpCount = 0, swapCount = 0;
  private static int cmpTotal = 0, swapTotal = 0;

  private static final Integer[] array01000 = new Integer[1000];
  private static final Integer[] array02000 = new Integer[2000];
  private static final Integer[] array04000 = new Integer[4000];
  private static final Integer[] array08000 = new Integer[8000];
  private static final Integer[] array16000 = new Integer[16000];

  @Setup
  public static void initData() {
    cmpCount = 0; swapCount = 0;

    fillWithRandoms(array01000);
    fillWithRandoms(array02000);
    fillWithRandoms(array04000);
    fillWithRandoms(array08000);
    fillWithRandoms(array16000);
  }

  public static void main(String[] args) throws IOException, RunnerException {
    Locale.setDefault(Locale.US);
    initData();

    runJMH(); // Run benchmarks. Comment-out it, if you want just to count comparisons etc.
//    System.exit(0); // If don't want to count comparisons and swaps

    System.out.printf("\nRand seed = %d, rand limit = %d, iterations = %d\n",
                      RAND_SEED, RAND_LIMIT, LOOPS_TO_ITERATE);

    System.out.print("sortArray01000(): ");
    loopOverMethod(qq -> sortArray01000());

    System.out.print("sortArray02000(): ");
    loopOverMethod(qq -> sortArray02000());

    System.out.print("sortArray04000(): ");
    loopOverMethod(qq -> sortArray04000());

    System.out.print("sortArray08000(): ");
    loopOverMethod(qq -> sortArray08000());

    System.out.print("sortArray16000(): ");
    loopOverMethod(qq -> sortArray16000());
  }

  private static void loopOverMethod(Consumer<Object> method) {
    cmpTotal = 0; swapTotal = 0;
    for (int loops = 0; loops < LOOPS_TO_ITERATE; loops++ ) {
      initData();
      method.accept(null);;
      cmpTotal += cmpCount; swapTotal += swapCount;
    }
    System.out.printf("avrg compares: %12.3f,  swaps: %12.3f\n",
                      (double)cmpTotal / LOOPS_TO_ITERATE, (double)swapTotal / LOOPS_TO_ITERATE);
  }

  /**
   * @throws RunnerException
   */
  private static void runJMH() throws RunnerException {
    final Options opt = new OptionsBuilder()
        .include(QSortBenchmarks.class.getSimpleName())
        .forks(1)
        .build();
    new Runner(opt).run();
  }

  private static void fillWithRandoms(Integer[] array) {
    for (int i = 0; i < array.length; i++) { // // Fill it with LIST_SIZE random values
      array[i] = (int)(RAND.nextDouble() * RAND_LIMIT);
    }
  }

  @Benchmark
  public static void sortArray01000() {
    final Integer[] array = array01000;
    quickSort(array, 0, array.length - 1);
  }

  @Benchmark
  public static void sortArray02000() {
    final Integer[] array = array02000;
    quickSort(array, 0, array.length - 1);
  }

  @Benchmark
  public static void sortArray04000() {
    final Integer[] array = array04000;
    quickSort(array, 0, array.length - 1);
  }

  @Benchmark
  public static void sortArray08000() {
    final Integer[] array = array08000;
    quickSort(array, 0, array.length - 1);
  }

  @Benchmark
  public static void sortArray16000() {
    final Integer[] array = array16000;
    quickSort(array, 0, array.length - 1);
  }

  private static void quickSort(Integer[] array, int lo, int hi) {
    if (hi <= lo) return;
    final int j = partition(array, lo, hi);
    quickSort(array, lo, j - 1);
    quickSort(array, j + 1, hi);
  }

  private static int partition(Integer[] array, int lo, int hi) {
    int i = lo, j = hi + 1;
    while (true) {
      while (compare(array[++i], array[lo]) < 0) // while (array[++i] < array[lo])
        if (i == hi) break;
      while (compare(array[lo], array[--j]) < 0) // while (array[lo] < array[--j])
        if (j == lo) break;
      if (i >= j) break;
      swapItems(array, i, j);
    }
    swapItems(array, lo, j);
    return j;
  }

  private static int compare(Integer v1, Integer v2) {
    cmpCount++;
    return v1.compareTo(v2);
  }

  private static void swapItems(Integer[] array, int i, int j) {
    swapCount++;
    final Integer tmp = array[i];
    array[i] = array[j];
    array[j] = tmp;
  }

}

Run Code Online (Sandbox Code Playgroud)

更新 21-05-18 10:08Z

局势已经明朗。正是JMH那显示出与实际执行时间毫无共同之处的奇怪结果。一个简单的手工基准测试System.nanoTime()，用于 10,000、20,000、40,000、80,000 和 160,000 个项目的数组，显示以下时间：

Rand seed = 123, rand limit = 1000000, iterations = 1000
sortArray_010k(): avrg time:    1049.538 mks/op
sortArray_020k(): avrg time:    2282.189 mks/op
sortArray_040k(): avrg time:    4976.079 mks/op
sortArray_080k(): avrg time:   10762.461 mks/op
sortArray_160k(): avrg time:   23115.345 mks/op

Run Code Online (Sandbox Code Playgroud)

而JMH相同数组的结果如下：

Benchmark                       Mode  Cnt      Score     Error  Units
QSortBenchmarks.sortArray_010k  avgt    5    109.454 ±   0.444  ms/op
QSortBenchmarks.sortArray_020k  avgt    5    373.518 ±  17.439  ms/op
QSortBenchmarks.sortArray_040k  avgt    5   1350.420 ±  26.733  ms/op
QSortBenchmarks.sortArray_080k  avgt    5   6519.015 ±  48.770  ms/op
QSortBenchmarks.sortArray_160k  avgt    5  26837.697 ± 926.132  ms/op

Run Code Online (Sandbox Code Playgroud)

手工制作的基准测试显示的数字N log(N)非常符合，看起来很逼真，并且与观察到的执行时间（以秒为单位）非常吻合。而且它们比显示的数字少 100 到 1000 多倍JMH。

这loopOverMethod()是获得它们的修改方式：

  private static void loopOverMethod(Consumer<Object> method) {
    for (int loops = 0; loops < 100; loops++ ) { // Kinda warmup
      initData();
      method.accept(null);
    }

    long time = 0;
    cmpTotal = 0; swapTotal = 0;
    for (int loops = 0; loops < LOOPS_TO_ITERATE; loops++ ) {
      initData();
      time -= System.nanoTime();
      method.accept(null);
      time += System.nanoTime();
      cmpTotal += cmpCount; swapTotal += swapCount;
    }
    System.out.printf("avrg time: \t%10.3f mks\n", 
                      time * 1e-3 / LOOPS_TO_ITERATE);
  }

Run Code Online (Sandbox Code Playgroud)

但现在出现了另一个问题。为什么会JMH显示出如此奇怪的结果？我使用它的方式有什么问题？显然我必须修改我使用的其他项目JMH。而是一个令人不快的消息。

更新 21-05-19 10:08Z

把它放在这里作为问题的更新，因为评论不允许插入引号。Thomas Kleger 给出的综合答案是绝对正确的。按照他的建议，我得到了以下结果：

JMH：

Benchmark                       Mode  Cnt      Score    Error  Units
QSortBenchmarks.sortArray_010k  avgt    5    975.028 ± 23.907  us/op
QSortBenchmarks.sortArray_020k  avgt    5   2253.627 ± 94.108  us/op
QSortBenchmarks.sortArray_040k  avgt    5   4836.680 ± 80.964  us/op
QSortBenchmarks.sortArray_080k  avgt    5  10041.063 ± 27.796  us/op
QSortBenchmarks.sortArray_160k  avgt    5  21232.223 ± 32.008  us/op

Run Code Online (Sandbox Code Playgroud)

手工基准：

Rand seed = 123, rand limit = 1000000, iterations = 1000
sortArray_010k(): avrg time:    1060.951 mks
sortArray_020k(): avrg time:    2296.533 mks
sortArray_040k(): avrg time:    5021.629 mks
sortArray_080k(): avrg time:   10855.963 mks
sortArray_160k(): avrg time:   23335.923 mks

Run Code Online (Sandbox Code Playgroud)

现在结果看起来很合理，我对它们完全满意。

Answer 1

Tho*_*ger 5

三点共同反对您的实施：

快速排序的最坏情况复杂度为 O(n^2)
选择最左边的元素作为枢轴会在已经排序的数组 ( https://en.wikipedia.org/wiki/Quicksort#Choice_of_pivot )上给出最坏的情况：

在快速排序的早期版本中，通常会选择分区最左边的元素作为主元元素。不幸的是，这会导致已经排序的数组出现最坏情况

您的算法对数组进行原地排序，这意味着在第一次通过后，“随机”数组将被排序。（为了计算平均时间，JMH 对数据进行了多次传递）。

要解决此问题，您可以更改基准测试方法。例如，您可以更改sortArray01000()为

@Benchmark
public static void sortArray01000() {
  final Integer[] array = Arrays.copyOf(array01000, array01000.length);
  quickSort(array, 0, array.length - 1);
}

Run Code Online (Sandbox Code Playgroud)

或者您可以修改@Setup注释，以便在每次调用基准方法之前执行它：

@Setup(Level.Invocation)
public static void initData() {
    //...
}

Run Code Online (Sandbox Code Playgroud)

的@Setup批注采用在执行设置方法时，决定的参数。

这三个级别是（https://hg.openjdk.java.net/code-tools/jmh/file/2be2df7dbaf8/jmh-core/src/main/java/org/openjdk/jmh/annotations/Level.java）：

Level.Trial: 在每个基准测试之前
Level.Iteration: 在每次迭代之前
Level.Invocation: 在每次执行基准方法之前

默认级别是Level.Trial( https://hg.openjdk.java.net/code-tools/jmh/file/2be2df7dbaf8/jmh-core/src/main/java/org/openjdk/jmh/annotations/Setup.java#l54）。

这对你的测试意味着什么？

要理解这一点，您必须了解 JMH 如何执行您的基准测试：

它开始对您的一种基准方法进行试验
在这次试验中，它进行了 5 次预热迭代和 5 次测量迭代
在每次迭代期间，它会在紧密循环中调用您的基准测试方法，直到 10 秒过去 - 如果您的基准测试方法需要 500us，这意味着它将在每次迭代期间调用大约 20'000 次，或在完整试用期间调用大约 200'000 次

现在使用@Setup(Level.Trial)和对输入数据进行排序的基准方法，这意味着只有快速排序方法的第一次调用才能显示O(N log(N))行为，所有剩余的调用都对已经排序的数组进行操作，并显示的最坏情况行为O(N^2)。

随着@Setup(Level.Iteration)形势依然没有太大的更好-现在是基准方法在具有每次迭代的第一个电话O(N log(N))的行为，每次迭代的剩余〜20'000电话仍然显示O(N^2)。

与@Setup(Level.Invocation)最后的每个基准方法（和因此快速排序的每次调用）都有自己的，未分类的数组作为输入，这清楚地表明在结果的调用：

@Setup(Level.Trial)

1000: 780 us
2000: 3300 us


@Setup(Level.Iteration)

1000: 780 us
2000: 3280 us
4000: 11700 us


@Setup(Level.Invocation)

1000: 58 us
2000: 124 us
4000: 280 us

Run Code Online (Sandbox Code Playgroud)

通过我提出的更改（在基准方法中复制输入数组），我得到了稍微好一点的结果，但这可能是由于缓存效果：

1000: 25 us
2000: 108 us
4000: 260 us

Run Code Online (Sandbox Code Playgroud)

归档时间：	4 年，6 月前
查看次数：	137 次
最近记录：	4 年，6 月前