基准排序算法 Java；平均 运行 次不正确
Benchmarking Sorting Algorithms Java; Average Run Times are incorrect
虽然我知道以下基准测试方法并不理想，但我正在研究基准排序算法以帮助更好地理解算法和数据结构。
我想列出“大”n 500000 和小“n”大小数组 50 的平均 运行 次，但我的平均值总是在增加。
我不确定哪里出错了：
public class BenchmarkingAlgorithms
{
public static void main(String[] args)
{
int[] largeUnsortedArray = largeArrayWithRandomInts(500000);
bubbleSort(largeUnsortedArray);
selectionSort(largeUnsortedArray);
insertionSort(largeUnsortedArray);
benchmarkQuickSort(largeUnsortedArray);
benchmarkMergeSort(largeUnsortedArray);
int[] smallUnsortedArray = smallArrayWithRandomInts(50);
bubbleSort(smallUnsortedArray);
selectionSort(smallUnsortedArray);
insertionSort(smallUnsortedArray);
benchmarkQuickSort(smallUnsortedArray);
benchmarkMergeSort(smallUnsortedArray);
}
/**
* Sorting an array of ints in ascending order using bubbleSort
* Best-Case Complexity: O(n), Average Complexity: O(n^2), Worst-Case Complexity: O(n^2)
* O(n) is achieved in Best-Case (already sorted array) using the alreadySorted flag
* @param array
* @return
*/
static int[] bubbleSort(int[] array)
{
int bubbleSortTime[] = new int[500];
int x, y;
for (x = 0; x< 500; x++) {
int temp;
boolean alreadySorted = true;
long start = System.nanoTime();
{
for (int i = 0; i < array.length; i++)
{
for (int j = 0; j < array.length - 1; j++)
{
if (array[j] > array[j + 1])
{
alreadySorted = false;
temp = array[j + 1];
array[j + 1] = array[j];
array[j] = temp;
}
}
if (alreadySorted == true)
{
break;
}
}
long end = System.nanoTime();
long bubbleSortRunTime = end - start;
bubbleSortTime[x] = (int) bubbleSortRunTime;
x++;
}
// getting array length
int length = bubbleSortTime.length;
// default sum value.
int sum = 0;
// sum of all values in array using for loop
for (int i = 0; i < bubbleSortTime.length; i++) {
sum += bubbleSortTime[i];
}
double average = sum / length;
System.out.println("Average of array : "+average + " nano seconds.");
}
return array;
}
/**
* Sorting an array of ints in ascending order using selectionSort
* Best-Case Complexity: O(n^2), Average Complexity: O(n^2), Worst-Case Complexity: O(n^2)
* @param array
* @return
*/
static int[] selectionSort(int[] array)
{
int selectionSortTime[] = new int[500];
int x, y;
for (x = 0; x< 500; x++) {
int min;
int pos = 0;
long start = System.nanoTime();
{
for (int i = 0; i < array.length - 1; i++)
{
min = array[i];
for (int j = i + 1; j < array.length; j++)
{
if (array[j] < min)
{
min = array[j];
pos = j;
}
}
array[pos] = array[i];
array[i] = min;
}
}
long end = System.nanoTime();
long selectionSortRunTime = end - start;
selectionSortTime[x] = (int) selectionSortRunTime;
x++;
// getting array length
int length = selectionSortTime.length;
// default sum value.
int sum = 0;
// sum of all values in array using for loop
for (int i = 0; i < selectionSortTime.length; i++) {
sum += selectionSortTime[i];
}
double average = sum / length;
System.out.println("Average of array : "+average + " nano seconds.");
}
return array;
}
/**
* Sorting an array of ints in ascending order using insertionSort
* Best-Case Complexity: O(n), Average Complexity: O(n^2), Worst-Case Complexity: O(n^2)
* @param array
* @return
*/
static int[] insertionSort(int[] array)
{
int insertionSortTime[] = new int[500];
int x, y;
for (x = 0; x< 500; x++) {
long start = System.nanoTime();
int j;
{
for (int i = 1; i < array.length; i++)
{
int key = array[i];
for (j = i - 1; (j >= 0) && (key < array[j]); j--)
{
array[j + 1] = array[j];
}
array[j + 1] = key;
}
}
long end = System.nanoTime();
long insertionSortRunTime = end - start;
insertionSortTime[x] = (int) insertionSortRunTime;
x++;
// getting array length
int length = insertionSortTime.length;
// default sum value.
int sum = 0;
// sum of all values in array using for loop
for (int i = 0; i < insertionSortTime.length; i++) {
sum += insertionSortTime[i];
}
double average = sum / length;
System.out.println("Average of array : "+average + " nano seconds.");
}
return array;
}
/**
* Sorting an array of ints in ascending order using quickSort
* Best-Case Complexity: O(n log(n)), Average Complexity: O(n log(n)), Worst-Case Complexity: O(n^2))
* @param array
* @return
*/
static void quickSort(int[] array, int low, int high)
{
int pivot = array[low + ((high - low) / 2)];
int i = low;
int j = high;
while (i <= j)
{
while (array[i] < pivot)
{
i++;
}
while (array[j] > pivot)
{
j--;
}
if (i <= j)
{
int temp = array[i];
array[i] = array[j];
array[j] = temp;
i++;
j--;
}
}
if (low < j)
{
quickSort(array, low, j);
}
if (i < high)
{
quickSort(array, i, high);
}
}
/**
* Helping method to benchmark quick sort's execution time
* @param array
*/
static void benchmarkQuickSort(int[] array)
{
int quickSortTime[] = new int[500];
int x, y;
for (x = 0; x< 500; x++) {
long start = System.nanoTime();
quickSort(array, 0, array.length - 1);
long end = System.nanoTime();
long quickSortRunTime = end - start;
quickSortTime[x] = (int) quickSortRunTime;
x++;
// getting array length
int length = quickSortTime.length;
// default sum value.
int sum = 0;
// sum of all values in array using for loop
for (int i = 0; i < quickSortTime.length; i++) {
sum += quickSortTime[i];
}
double average = sum / length;
System.out.println("Average of array : "+average + " nano seconds.");
}
}
/**
* Sorting an array of ints in ascending order using mergeSort
* Best-Case Complexity: O(n log(n)), Average Complexity: O(n log(n)), Worst-Case Complexity: O(n log(n)))
* @param array
* @return
*/
public static int[] mergeSort(int[] array)
{
if (array.length == 1)
{
return array;
}
int[] array1 = new int[(array.length/2)];
int[] array2 = new int[(array.length-array1.length)];
System.arraycopy(array, 0, array1, 0, array1.length);
System.arraycopy(array, array1.length, array2, 0, array2.length);
mergeSort(array1);
mergeSort(array2);
merge(array1, array2, array);
return array;
}
/**
* Merges 2 sorted arrays of ints
* @param array1
* @param array2
* @param mergedArray
* @return
*/
static void merge(int[] array1, int[] array2, int[] mergedArray)
{
int array1Index = 0;
int array2Index = 0;
int pos = 0;
while ((array1Index < array1.length) && (array2Index < array2.length))
{
if (array1[array1Index] < array2[array2Index])
{
mergedArray[pos] = array1[array1Index];
array1Index++;
pos++;
} else
{
mergedArray[pos] = array2[array2Index];
array2Index++;
pos++;
}
}
if (array1Index < array2Index)
{
System.arraycopy(array1, array1Index, mergedArray, pos, array1.length - array1Index);
}
else if (array2Index < array1Index) ;
{
System.arraycopy(array2, array2Index, mergedArray, pos, array2.length - array2Index);
}
}
/**
* Helping method to benchmark merge sort's execution time
* @param array
*/
static void benchmarkMergeSort(int[] array)
{
int mergeSortTime[] = new int[500];
int x, y;
for (x = 0; x< 500; x++) {
long start = System.nanoTime();
mergeSort(array);
long end = System.nanoTime();
long quickSortRunTime = end - start;
mergeSortTime[x] = (int) quickSortRunTime;
x++;
// getting array length
int length = mergeSortTime.length;
// default sum value.
int sum = 0;
// sum of all values in array using for loop
for (int i = 0; i < mergeSortTime.length; i++) {
sum += mergeSortTime[i];
}
double average = sum / length;
System.out.println("Average of array : "+average + " nano seconds.");
}
}
/**
* Creates and returns an array with random ints
* @param size the size of the array to be created
* @return
*/
static int[] largeArrayWithRandomInts(int size)
{
int[] largeArray = new int[size];
for (int i = 0; i < size; i++)
{
largeArray[i] = (int) (Math.random() * Math.random() * 500000);
}
return largeArray;
}
static int[] smallArrayWithRandomInts(int size)
{
int[] smallArray = new int[size];
for (int i = 0; i < size; i++)
{
smallArray[i] = (int) (Math.random() * Math.random() * 50);
}
return smallArray;
}
/**
* Prints the elements of one dimensional array of type int
* @param array
*/
static void printArray(int[] array)
{
for (int i = 0; i < array.length; i++)
{
System.out.print(array[i] + " ");
}
System.out.println();
}
}
我很感激任何见解。随时准备学习新事物。
您的方法中有多处出错。
- 您正在通过取
bubbleSortTime 中 500 个元素的平均值来计算和打印中间时间。对于第一个 运行，而不是除以 bubbleSortTime.length（即 500），您应该除以 x + 1 以获得您完成的 运行 的平均值到目前为止。
- 您分别为每个 运行 计时，由于
System.nanoTime() 的工作方式，四舍五入到大约 50 纳秒（参见 javadoc）。你应该做的是将开始时间存储到一个变量，然后 运行 你想要在一个循环中计时 X 次的代码（100-1000 次通常就足够了，更多 运行s 会给出一个更精确的结果），然后记录结束时间，最后将经过的时间除以X，得到定时代码的平均运行时间。
- 在开始为您的代码计时之前，您应该至少 运行 计时代码一次。这将导致加载所有 类 和所需的系统库，这可能是一次稍微慢一点的操作。
虽然我知道以下基准测试方法并不理想，但我正在研究基准排序算法以帮助更好地理解算法和数据结构。
我想列出“大”n 500000 和小“n”大小数组 50 的平均 运行 次，但我的平均值总是在增加。
我不确定哪里出错了：
public class BenchmarkingAlgorithms
{
public static void main(String[] args)
{
int[] largeUnsortedArray = largeArrayWithRandomInts(500000);
bubbleSort(largeUnsortedArray);
selectionSort(largeUnsortedArray);
insertionSort(largeUnsortedArray);
benchmarkQuickSort(largeUnsortedArray);
benchmarkMergeSort(largeUnsortedArray);
int[] smallUnsortedArray = smallArrayWithRandomInts(50);
bubbleSort(smallUnsortedArray);
selectionSort(smallUnsortedArray);
insertionSort(smallUnsortedArray);
benchmarkQuickSort(smallUnsortedArray);
benchmarkMergeSort(smallUnsortedArray);
}
/**
* Sorting an array of ints in ascending order using bubbleSort
* Best-Case Complexity: O(n), Average Complexity: O(n^2), Worst-Case Complexity: O(n^2)
* O(n) is achieved in Best-Case (already sorted array) using the alreadySorted flag
* @param array
* @return
*/
static int[] bubbleSort(int[] array)
{
int bubbleSortTime[] = new int[500];
int x, y;
for (x = 0; x< 500; x++) {
int temp;
boolean alreadySorted = true;
long start = System.nanoTime();
{
for (int i = 0; i < array.length; i++)
{
for (int j = 0; j < array.length - 1; j++)
{
if (array[j] > array[j + 1])
{
alreadySorted = false;
temp = array[j + 1];
array[j + 1] = array[j];
array[j] = temp;
}
}
if (alreadySorted == true)
{
break;
}
}
long end = System.nanoTime();
long bubbleSortRunTime = end - start;
bubbleSortTime[x] = (int) bubbleSortRunTime;
x++;
}
// getting array length
int length = bubbleSortTime.length;
// default sum value.
int sum = 0;
// sum of all values in array using for loop
for (int i = 0; i < bubbleSortTime.length; i++) {
sum += bubbleSortTime[i];
}
double average = sum / length;
System.out.println("Average of array : "+average + " nano seconds.");
}
return array;
}
/**
* Sorting an array of ints in ascending order using selectionSort
* Best-Case Complexity: O(n^2), Average Complexity: O(n^2), Worst-Case Complexity: O(n^2)
* @param array
* @return
*/
static int[] selectionSort(int[] array)
{
int selectionSortTime[] = new int[500];
int x, y;
for (x = 0; x< 500; x++) {
int min;
int pos = 0;
long start = System.nanoTime();
{
for (int i = 0; i < array.length - 1; i++)
{
min = array[i];
for (int j = i + 1; j < array.length; j++)
{
if (array[j] < min)
{
min = array[j];
pos = j;
}
}
array[pos] = array[i];
array[i] = min;
}
}
long end = System.nanoTime();
long selectionSortRunTime = end - start;
selectionSortTime[x] = (int) selectionSortRunTime;
x++;
// getting array length
int length = selectionSortTime.length;
// default sum value.
int sum = 0;
// sum of all values in array using for loop
for (int i = 0; i < selectionSortTime.length; i++) {
sum += selectionSortTime[i];
}
double average = sum / length;
System.out.println("Average of array : "+average + " nano seconds.");
}
return array;
}
/**
* Sorting an array of ints in ascending order using insertionSort
* Best-Case Complexity: O(n), Average Complexity: O(n^2), Worst-Case Complexity: O(n^2)
* @param array
* @return
*/
static int[] insertionSort(int[] array)
{
int insertionSortTime[] = new int[500];
int x, y;
for (x = 0; x< 500; x++) {
long start = System.nanoTime();
int j;
{
for (int i = 1; i < array.length; i++)
{
int key = array[i];
for (j = i - 1; (j >= 0) && (key < array[j]); j--)
{
array[j + 1] = array[j];
}
array[j + 1] = key;
}
}
long end = System.nanoTime();
long insertionSortRunTime = end - start;
insertionSortTime[x] = (int) insertionSortRunTime;
x++;
// getting array length
int length = insertionSortTime.length;
// default sum value.
int sum = 0;
// sum of all values in array using for loop
for (int i = 0; i < insertionSortTime.length; i++) {
sum += insertionSortTime[i];
}
double average = sum / length;
System.out.println("Average of array : "+average + " nano seconds.");
}
return array;
}
/**
* Sorting an array of ints in ascending order using quickSort
* Best-Case Complexity: O(n log(n)), Average Complexity: O(n log(n)), Worst-Case Complexity: O(n^2))
* @param array
* @return
*/
static void quickSort(int[] array, int low, int high)
{
int pivot = array[low + ((high - low) / 2)];
int i = low;
int j = high;
while (i <= j)
{
while (array[i] < pivot)
{
i++;
}
while (array[j] > pivot)
{
j--;
}
if (i <= j)
{
int temp = array[i];
array[i] = array[j];
array[j] = temp;
i++;
j--;
}
}
if (low < j)
{
quickSort(array, low, j);
}
if (i < high)
{
quickSort(array, i, high);
}
}
/**
* Helping method to benchmark quick sort's execution time
* @param array
*/
static void benchmarkQuickSort(int[] array)
{
int quickSortTime[] = new int[500];
int x, y;
for (x = 0; x< 500; x++) {
long start = System.nanoTime();
quickSort(array, 0, array.length - 1);
long end = System.nanoTime();
long quickSortRunTime = end - start;
quickSortTime[x] = (int) quickSortRunTime;
x++;
// getting array length
int length = quickSortTime.length;
// default sum value.
int sum = 0;
// sum of all values in array using for loop
for (int i = 0; i < quickSortTime.length; i++) {
sum += quickSortTime[i];
}
double average = sum / length;
System.out.println("Average of array : "+average + " nano seconds.");
}
}
/**
* Sorting an array of ints in ascending order using mergeSort
* Best-Case Complexity: O(n log(n)), Average Complexity: O(n log(n)), Worst-Case Complexity: O(n log(n)))
* @param array
* @return
*/
public static int[] mergeSort(int[] array)
{
if (array.length == 1)
{
return array;
}
int[] array1 = new int[(array.length/2)];
int[] array2 = new int[(array.length-array1.length)];
System.arraycopy(array, 0, array1, 0, array1.length);
System.arraycopy(array, array1.length, array2, 0, array2.length);
mergeSort(array1);
mergeSort(array2);
merge(array1, array2, array);
return array;
}
/**
* Merges 2 sorted arrays of ints
* @param array1
* @param array2
* @param mergedArray
* @return
*/
static void merge(int[] array1, int[] array2, int[] mergedArray)
{
int array1Index = 0;
int array2Index = 0;
int pos = 0;
while ((array1Index < array1.length) && (array2Index < array2.length))
{
if (array1[array1Index] < array2[array2Index])
{
mergedArray[pos] = array1[array1Index];
array1Index++;
pos++;
} else
{
mergedArray[pos] = array2[array2Index];
array2Index++;
pos++;
}
}
if (array1Index < array2Index)
{
System.arraycopy(array1, array1Index, mergedArray, pos, array1.length - array1Index);
}
else if (array2Index < array1Index) ;
{
System.arraycopy(array2, array2Index, mergedArray, pos, array2.length - array2Index);
}
}
/**
* Helping method to benchmark merge sort's execution time
* @param array
*/
static void benchmarkMergeSort(int[] array)
{
int mergeSortTime[] = new int[500];
int x, y;
for (x = 0; x< 500; x++) {
long start = System.nanoTime();
mergeSort(array);
long end = System.nanoTime();
long quickSortRunTime = end - start;
mergeSortTime[x] = (int) quickSortRunTime;
x++;
// getting array length
int length = mergeSortTime.length;
// default sum value.
int sum = 0;
// sum of all values in array using for loop
for (int i = 0; i < mergeSortTime.length; i++) {
sum += mergeSortTime[i];
}
double average = sum / length;
System.out.println("Average of array : "+average + " nano seconds.");
}
}
/**
* Creates and returns an array with random ints
* @param size the size of the array to be created
* @return
*/
static int[] largeArrayWithRandomInts(int size)
{
int[] largeArray = new int[size];
for (int i = 0; i < size; i++)
{
largeArray[i] = (int) (Math.random() * Math.random() * 500000);
}
return largeArray;
}
static int[] smallArrayWithRandomInts(int size)
{
int[] smallArray = new int[size];
for (int i = 0; i < size; i++)
{
smallArray[i] = (int) (Math.random() * Math.random() * 50);
}
return smallArray;
}
/**
* Prints the elements of one dimensional array of type int
* @param array
*/
static void printArray(int[] array)
{
for (int i = 0; i < array.length; i++)
{
System.out.print(array[i] + " ");
}
System.out.println();
}
}
我很感激任何见解。随时准备学习新事物。
您的方法中有多处出错。
- 您正在通过取
bubbleSortTime中 500 个元素的平均值来计算和打印中间时间。对于第一个 运行，而不是除以bubbleSortTime.length（即 500），您应该除以x + 1以获得您完成的 运行 的平均值到目前为止。 - 您分别为每个 运行 计时，由于
System.nanoTime()的工作方式，四舍五入到大约 50 纳秒（参见 javadoc）。你应该做的是将开始时间存储到一个变量，然后 运行 你想要在一个循环中计时 X 次的代码（100-1000 次通常就足够了，更多 运行s 会给出一个更精确的结果），然后记录结束时间，最后将经过的时间除以X，得到定时代码的平均运行时间。 - 在开始为您的代码计时之前，您应该至少 运行 计时代码一次。这将导致加载所有 类 和所需的系统库，这可能是一次稍微慢一点的操作。