我已经尝试过基准测试,由于某种原因,当在100万个元素数组上尝试将它们都Mergesort
按0.3s排序并Quicksort
花费1.3s时。
我听说,由于它的内存管理,通常quicksort更快,但是如何解释这些结果呢?
如果这有任何区别,我正在运行MacBook Pro。输入是一组从0到127的随机生成的整数。
代码使用Java:
合并排序:
static void mergesort(int arr[]) {
int n = arr.length;
if (n < 2)
return;
int mid = n / 2;
int left[] = new int[mid];
int right[] = new int[n - mid];
for (int i = 0; i < mid; i++)
left[i] = arr[i];
for (int i = mid; i < n; i++)
right[i - mid] = arr[i];
mergesort(left);
mergesort(right);
merge(arr, left, right);
}
public static void merge(int arr[], int left[], int right[]) {
int nL = left.length;
int nR = right.length;
int i = 0, j = 0, k = 0;
while (i < nL && j < nR) {
if (left[i] <= right[j]) {
arr[k] = left[i];
i++;
} else {
arr[k] = right[j];
j++;
}
k++;
}
while (i < nL) {
arr[k] = left[i];
i++;
k++;
}
while (j < nR) {
arr[k] = right[j];
j++;
k++;
}
}
快速排序:
public static void quickSort(int[] arr, int start, int end) {
int partition = partition(arr, start, end);
if (partition - 1 > start) {
quickSort(arr, start, partition - 1);
}
if (partition + 1 < end) {
quickSort(arr, partition + 1, end);
}
}
public static int partition(int[] arr, int start, int end) {
int pivot = arr[end];
for (int i = start; i < end; i++) {
if (arr[i] < pivot) {
int temp = arr[start];
arr[start] = arr[i];
arr[i] = temp;
start++;
}
}
int temp = arr[start];
arr[start] = pivot;
arr[end] = temp;
return start;
}
您的实现有点简单:
mergesort
在每个递归调用中分配2个新数组,这很昂贵,但是某些JVM在优化这种编码模式方面出奇地有效。quickSort
使用的支点选择差,即子数组的最后一个元素,这给排序后的子数组(包括那些具有相同元素的子数组)提供了二次时间。数据集是一个伪随机数在较小范围内的数组0..127
,导致实现的缺点quickSort
要比mergesort
版本的效率低得多。增大数据集的大小应使其更加明显,甚至可能由于太多的递归调用而导致堆栈溢出。具有通用模式(例如相同的值,增加或减少的集合以及此类序列的组合)的数据集将导致实现的灾难性性能quickSort
。
这是经过稍加修改的版本,对枢轴(数组3/4处的元素)的病理选择较少,并且有一个循环可检测枢轴值的重复项,从而提高具有重复值的数据集的效率。在仅包含4万个元素的数组的标准排序基准上,它的性能要好得多(100x),但比radixsort慢得多(8x):
public static void quickSort(int[] arr, int start, int end) {
int p1 = partition(arr, start, end);
int p2 = p1;
/* skip elements identical to the pivot */
while (++p2 <= end && arr[p2] == arr[p1])
continue;
if (p1 - 1 > start) {
quickSort(arr, start, p1 - 1);
}
if (p2 < end) {
quickSort(arr, p2, end);
}
}
public static int partition(int[] arr, int start, int end) {
/* choose pivot at 3/4 or the array */
int i = end - ((end - start + 1) >> 2);
int pivot = arr[i];
arr[i] = arr[end];
arr[end] = pivot;
for (i = start; i < end; i++) {
if (arr[i] < pivot) {
int temp = arr[start];
arr[start] = arr[i];
arr[i] = temp;
start++;
}
}
int temp = arr[start];
arr[start] = pivot;
arr[end] = temp;
return start;
}
对于OP的数据集,假设分布具有良好的随机性,则扫描重复项可改善性能。如预期的那样,选择不同的枢轴,无论是第一个,最后一个,中间,3/4或2/3或什至3的中间值都几乎没有影响。
quickSort
由于选择了支点,因此对其他非随机分布的进一步测试表明此实现具有灾难性的性能。根据我的基准,通过选择在数组的3/4或2/3处旋转元素,可以大大提高性能(对于50k样本,其性能提高了300倍,比标准合并排序快40%,可比时间缩短radix_sort
)。
本文收集自互联网,转载请注明来源。
如有侵权,请联系 [email protected] 删除。
我来说两句