我编写了一个学校作业程序,该程序打印出使用六种不同的排序算法对整数数组进行排序所需的时间:选择排序,冒泡排序,合并排序,快速排序,堆排序和基数排序。整数数组的范围是50,000至300,000个元素。
困扰我的是合并排序,堆排序,基数排序和Collections.sort()
方法的第一个结果。
第一个数组(50,000个元素的数组)比随后的更长的数组需要更长的排序时间。正如我所期望的那样,每个后续的较大数组将花费越来越多的时间进行排序。我想知道是什么原因造成的,这是我没有考虑的开销,还是我的算法或程序有问题。
我已在显示结果的屏幕快照中附加了一个链接
以下是代码示例
int[] array = generateIntegers(50000);
long start = System.currentTimeMillis();
radixSort(array);
long end = System.currentTimeMillis();
System.out.println(end - start);
int[] arrayTwo = generateIntegers(100000);
start = System.currentTimeMillis();
radixSort(arrayTwo);
end = System.currentTimeMillis();
System.out.println(end - start);
int[] arrayThree = generateIntegers(150000);
start = System.currentTimeMillis();
radixSort(arrayThree);
end = System.currentTimeMillis();
System.out.println(end - start);
安慰:
40
10
13
和generateIntegers(n)
方法
public static int[] generateIntegers(int size)
{
int[] arr = new int[size];
Random rand = new Random();
for (int i = 0; i < size; i++)
arr[i] = rand.nextInt(integerRange);
return arr;
}
感谢您的输入!
正确衡量Java程序的性能非常复杂且困难,特别是当您想要比较不同的算法时,由于JVM在执行过程中进行了许多巧妙的优化(例如,参见Wikipedia:Java性能-自适应优化)。
一个主要规则是在进行任何测量之前执行“ JVM预热”。这使JVM有时间“学习”您的代码以及如何使用它(执行配置文件)来优化代码。然后,您应该计算几次执行的平均执行时间值。
您的效果评估方法可能如下所示:
public long measure(Runnable testCode, int warmupIterations, int testIterations) {
// warmup
for(int i = 0; i < warmupIterations; i++) {
testCode.run();
}
// test
long time = System.currentTimeMillis();
for(int i = 0; i < testIterations; i++) {
testCode.run();
}
long elapsed = System.currentTimeMillis() - time;
return elapsed / testIterations;
}
本文收集自互联网,转载请注明来源。
如有侵权,请联系[email protected] 删除。
我来说两句