老师您好，对于Heapify的两种操作，结果似乎不是很稳定
来源：8-5 Heapify 和 Replace
温柔的微笑
2019-08-16
private static int n = 1000000;
public static void main(String[] args) {
Integer[] testData = new Integer[n];
Random random = new Random();
for (int i = 0; i < n; i++) {
testData[i] = random.nextInt(Integer.MAX_VALUE);
}
System.out.println("isHeapify true time :"+testHeap(testData, true)+"s");
System.out.println("isHeapify false time :"+testHeap(testData, false)+"s");
}
public static double testHeap(Integer[] testData, boolean isHeapify){
long startTime = System.nanoTime();
MaxHeap<Integer> maxHeap;
if (isHeapify){
maxHeap = new MaxHeap<>(testData);
} else {
maxHeap = new MaxHeap<>();
for (Integer i: testData){
maxHeap.add(i);
}
}
long endTime = System.nanoTime();
return (endTime-startTime)/1000000000.0;
}
运行结果1：
isHeapify true time :0.122953275s
isHeapify false time :0.100756227s
运行结果2：
isHeapify true time :0.084443782s
isHeapify false time :0.068161134s
运行结果3：
isHeapify true time :0.063246667s
isHeapify false time :0.094706342s
差别不是很大，而且有时使用下沉的方式比循环添加元素还要慢
1回答
-
其实是正常的。
首先，O(n) 级别的算法和 O(nlogn) 级别的算法，差距就是不大的，之间的差距，远没有 O(n) 和 O(n^2) 级别的算法差距明显。
其次，根据你提供的数据，算法性能其实都在 0.1 秒甚至是 0.01 秒这个级别。可以看出来，你的计算机性能还是很强劲的。与此同时，在这个时间级别里，细微的操作系统上的变化，也会给程序性能测试带来影响。更不用提在现代计算机上，可能还有多核运算带来的影响。
另外，你使用的是 Java 语言，由于 Java 语言代码本身运行在 JVM 上，JVM 的具体实现，包括 JVM 内部的优化，也会影响程序的性能测试。对于这一点，Java 已经比很多脚本语言，比如 Python 或者 js 好很多了，但还是有影响的。使用更底层的语言，比如 C/C++，甚至是汇编语言，将能更充分地保证你的测试结果仅仅是算法逻辑的执行结果，而排除更多干扰。
如果你希望看到更准确更稳定的性能结果，我的建议是：
1）增加数据规模；
2）多次运行取平均值；用统计结果代替单次测试结果，通常都是更稳定可靠的；
3）使用更底层的方式，比如 C/C++，甚至是汇编语言，代替 Java 实现。
道理上，你应该能看到对于大多数情况，平均来看，使用 heapify 应该会快一些。n 越大应该越明显。如果能看到这一点，就已经足够了。我不建议在这个logn复杂度的性能差异中，在你的机器上测试，可能有毫米级别的误差，耽误太多时间：）
继续加油！：）
112019-08-16
相似问题