Java - 为什么这个二进制堆的实现比另一个更快？

Question

在阅读了一些关于堆/优先级队列的内容后，我最近自己实现了一个。之后我决定将我的实现的性能与我在一本书中找到的实现的性能进行比较，结果让我有点困惑。两种实现的插入方法之间似乎存在巨大的性能差异。

我使用这段代码来测试两个堆:

Random rnd = new Random();
long startTime = System.currentTimeMillis();
for(int i = 0; i < 1_000_000_0; i++) heap.insert(rnd.nextInt(1000));
System.out.println(System.currentTimeMillis() - startTime);

当我用我的堆实现运行它时，我得到了大约 600 毫秒的结果。当我用本书的实现运行它时，我得到大约 1900 毫秒。差距怎么可能这么大？我的实现肯定有问题。

我的实现:

public class Heap<T extends Comparable<? super T>> {

    private T[] array = (T[])new Comparable[10];
    private int size = 0;

    public void insert(T data) {
        if(size+1 > array.length) expandArray();

        array[size++] = data;
        int pos = size-1;
        T temp;

        while(pos != 0 && array[pos].compareTo(array[pos/2]) < 0) {
            temp = array[pos/2];
            array[pos/2] = array[pos];
            array[pos] = temp;
            pos /= 2;
        }
    }

    private void expandArray() {
        T[] newArray = (T[])new Comparable[array.length*2];

        for(int i = 0; i < array.length; i++)
            newArray[i] = array[i];

        array = newArray;
    }
}

本书的实现:

public class BooksHeap<AnyType extends Comparable<? super AnyType>>
{
    private static final int DEFAULT_CAPACITY = 10;

    private int currentSize;
    private AnyType [ ] array;

    public BinaryHeap( )
    {
        this( DEFAULT_CAPACITY );
    }

    public BinaryHeap( int capacity )
    {
        currentSize = 0;
        array = (AnyType[]) new Comparable[ capacity + 1 ];
    }

    public void insert( AnyType x )
    {
        if( currentSize == array.length - 1 )
            enlargeArray( array.length * 2 + 1 );

        int hole = ++currentSize;
        for( array[ 0 ] = x; x.compareTo( array[ hole / 2 ] ) < 0; hole /= 2 )
            array[ hole ] = array[ hole / 2 ];
        array[ hole ] = x;
    }


    private void enlargeArray( int newSize )
    {
            AnyType [] old = array;
            array = (AnyType []) new Comparable[ newSize ];
            for( int i = 0; i < old.length; i++ )
                array[ i ] = old[ i ];        
    }
}

编辑:这本书是 Mark Allen Weiss 的“Data Structures and Algorithm Analysis in Java”。第三版。国际标准书号:0-273-75211-1。

Answer 1

在这里，您的代码是用 JMH 测量的:

@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.NANOSECONDS)
@OperationsPerInvocation(Measure.SIZE)
@Warmup(iterations = 5, time = 1, timeUnit = TimeUnit.SECONDS)
@Measurement(iterations = 5, time = 1, timeUnit = TimeUnit.SECONDS)
@State(Scope.Thread)
@Fork(1)
public class Measure
{
  static final int SIZE = 4_000_000;
  private Random rnd;

  @Setup public void setup() {
    rnd  = new Random();
  }

  @Benchmark public Object heap() {
    Heap<Integer> heap = new Heap<>();
    for (int i = 0; i < SIZE; i++) heap.insert(rnd.nextInt());
    return heap;
  }

  @Benchmark public Object booksHeap() {
    BooksHeap<Integer> heap = new BooksHeap<>();
    for (int i = 0; i < SIZE; i++) heap.insert(rnd.nextInt());
    return heap;
  }

  public static class Heap<T extends Comparable<? super T>> {

    private T[] array = (T[])new Comparable[10];
    private int size = 0;

    public void insert(T data) {
      if(size+1 > array.length) expandArray();

      array[size++] = data;
      int pos = size-1;
      T temp;

      while(pos != 0 && array[pos].compareTo(array[pos/2]) < 0) {
        temp = array[pos/2];
        array[pos/2] = array[pos];
        array[pos] = temp;
        pos /= 2;
      }
    }

    private void expandArray() {
      T[] newArray = (T[])new Comparable[array.length*2];
      for (int i = 0; i < array.length; i++)
        newArray[i] = array[i];
      array = newArray;
    }
  }

  public static class BooksHeap<AnyType extends Comparable<? super AnyType>>
  {
    private static final int DEFAULT_CAPACITY = 10;

    private int currentSize;
    private AnyType [ ] array;

    public BooksHeap()
    {
      this( DEFAULT_CAPACITY );
    }

    public BooksHeap( int capacity )
    {
      currentSize = 0;
      array = (AnyType[]) new Comparable[ capacity + 1 ];
    }

    public void insert( AnyType x )
    {
      if( currentSize == array.length - 1 )
        enlargeArray( array.length * 2 + 1 );

      int hole = ++currentSize;
      for( array[ 0 ] = x; x.compareTo( array[ hole / 2 ] ) < 0; hole /= 2 )
        array[ hole ] = array[ hole / 2 ];
      array[ hole ] = x;
    }


    private void enlargeArray( int newSize )
    {
      AnyType [] old = array;
      array = (AnyType []) new Comparable[ newSize ];
      for( int i = 0; i < old.length; i++ )
        array[ i ] = old[ i ];
    }
  }
}

结果:

Benchmark          Mode  Cnt   Score    Error  Units
Measure.booksHeap  avgt    5  62,712 ± 23,633  ns/op
Measure.heap       avgt    5  62,784 ± 44,228  ns/op

它们完全一样。

练习的寓意:不要认为您可以只编写一个循环并将其称为基准。在像 HotSpot 这样的复杂、 self 优化的运行时中测量任何有意义的东西是一个非常困难的挑战，最好留给像 JMH 这样的专家基准测试工具。

作为旁注，如果您使用 System.arraycopy 而不是手动循环，您可以节省大约 20% 的时间(在两种实现中)。令人尴尬的是，这不是我的主意——IntelliJ IDEA 的自动检查表明了这一点，并自行转换了代码:)