Java - 为什么这个二叉堆的实现比另一个快？
Java - Why is this implementation of a binary heap faster than the other?
阅读了一些关于 heaps/priority 队列的内容后，我最近自己实现了一个。之后我决定将我的实现的性能与我在一本书中找到的实现的性能进行比较，结果让我有点困惑。看来两种实现的插入方法之间存在巨大的性能差异。
我用这段代码测试了两个堆：
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 ];
}
}
编辑：这本书是 "Data Structures and Algorithm Analysis in Java" 马克·艾伦·魏斯 (Mark Allen Weiss) 的书。第三版。国际标准书号：0-273-75211-1.
将实现的测试作为这个问题的一部分，你如何测试这些实现可以解释很多差异，考虑这个例子。当我将你的堆放在一个名为 OPHeap 的 class 中，将书的堆放在一个名为 BookHeap 的 class 中，然后按以下顺序进行测试：
import java.util.Random;
public class Test {
public static void main(String ...args) {
{
Random rnd = new Random();
BookHeap<Integer> heap = new BookHeap<Integer>();
long startTime = System.currentTimeMillis();
for(int i = 0; i < 1_000_000_0; i++) heap.insert(rnd.nextInt(1000));
System.out.println("Book's Heap:" + (System.currentTimeMillis() - startTime));
}
{
Random rnd = new Random();
OPHeap<Integer> heap = new OPHeap<Integer>();
long startTime = System.currentTimeMillis();
for(int i = 0; i < 1_000_000_0; i++) heap.insert(rnd.nextInt(1000));
System.out.println(" OP's Heap:" + (System.currentTimeMillis() - startTime));
}
}
}
我得到这个输出：
Book's Heap:1924
OP's Heap:1171
然而，当我交换测试顺序时，我得到这个输出：
OP's Heap:1867
Book's Heap:1515
这叫做"Warm-up"，你可以从this article中学到很多处理它的方法。此外，无论何时您在测试中使用 Random，您都应该定义一个种子值，这样您的 "pseudo random" 结果是可预测的。
在这里，您的代码是用 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 这样的复杂、自我优化的运行时中测量任何有意义的东西是一个非常困难的挑战，最好留给像 JMH 这样的专家基准测试工具。
附带说明一下，如果您使用 System.arraycopy 而不是手动循环，则可以节省大约 20% 的时间（在两种实现中）。令人尴尬的是，这不是我的主意——IntelliJ IDEA 的自动检查表明了这一点，并自行转换了代码:)
阅读了一些关于 heaps/priority 队列的内容后，我最近自己实现了一个。之后我决定将我的实现的性能与我在一本书中找到的实现的性能进行比较，结果让我有点困惑。看来两种实现的插入方法之间存在巨大的性能差异。
我用这段代码测试了两个堆：
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 ];
}
}
编辑：这本书是 "Data Structures and Algorithm Analysis in Java" 马克·艾伦·魏斯 (Mark Allen Weiss) 的书。第三版。国际标准书号：0-273-75211-1.
将实现的测试作为这个问题的一部分，你如何测试这些实现可以解释很多差异，考虑这个例子。当我将你的堆放在一个名为 OPHeap 的 class 中，将书的堆放在一个名为 BookHeap 的 class 中，然后按以下顺序进行测试：
import java.util.Random;
public class Test {
public static void main(String ...args) {
{
Random rnd = new Random();
BookHeap<Integer> heap = new BookHeap<Integer>();
long startTime = System.currentTimeMillis();
for(int i = 0; i < 1_000_000_0; i++) heap.insert(rnd.nextInt(1000));
System.out.println("Book's Heap:" + (System.currentTimeMillis() - startTime));
}
{
Random rnd = new Random();
OPHeap<Integer> heap = new OPHeap<Integer>();
long startTime = System.currentTimeMillis();
for(int i = 0; i < 1_000_000_0; i++) heap.insert(rnd.nextInt(1000));
System.out.println(" OP's Heap:" + (System.currentTimeMillis() - startTime));
}
}
}
我得到这个输出：
Book's Heap:1924
OP's Heap:1171
然而，当我交换测试顺序时，我得到这个输出：
OP's Heap:1867
Book's Heap:1515
这叫做"Warm-up"，你可以从this article中学到很多处理它的方法。此外，无论何时您在测试中使用 Random，您都应该定义一个种子值，这样您的 "pseudo random" 结果是可预测的。
在这里，您的代码是用 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 这样的复杂、自我优化的运行时中测量任何有意义的东西是一个非常困难的挑战，最好留给像 JMH 这样的专家基准测试工具。
附带说明一下，如果您使用 System.arraycopy 而不是手动循环，则可以节省大约 20% 的时间（在两种实现中）。令人尴尬的是，这不是我的主意——IntelliJ IDEA 的自动检查表明了这一点，并自行转换了代码:)