我已经实现了一个合并排序和一个快速排序来将它们与原生 JavaScript 排序进行比较。对于快速排序，我尝试使用此算法:view algorithm on youtube .两种算法都使用尽可能少的内存，对于合并排序，为每个递归调用传递一个辅助数组(以避免开销)，对于快速排序，开始和结束位置的位置。我正在使用排序来管理 NodeJs 应用程序中的大量数据。
下面你有合并排序、快速排序和原生 JavaScript 排序，你可以测试性能
问题是:为什么原生 JavaScript 执行速度较慢？
就我而言:
Chrome - 合并排序:测量:1997.920ms；快速排序:测量:1755.740ms； native :测量:4988.105ms
Node :归并排序:测量:2233.413ms；快速排序:测量:1876.055ms； native :测量:6317.118ms
合并排序
var length = 10000000; // ten millions;
var arr = [];
for (let i = length; i > 0; i--) {
// random array
arr.push(parseInt(Math.random() * 1000000000));
}
var mergeSort = function(array) {
function merge(arr, aux, lo, mid, hi) {
for (var k = lo; k <= hi; k++) {
aux[k] = arr[k];
}
var i = lo;
var j = mid + 1;
for (var k = lo; k <= hi; k++) {
if (i > mid) {
arr[k] = aux[j++];
} else if (j > hi) {
arr[k] = aux[i++];
} else if (aux[i] < aux[j]) {
arr[k] = aux[i++];
} else {
arr[k] = aux[j++];
}
}
}
function sort(array, aux, lo, hi) {
if (hi <= lo) return;
var mid = Math.floor(lo + (hi - lo) / 2);
sort(array, aux, lo, mid);
sort(array, aux, mid + 1, hi);
merge(array, aux, lo, mid, hi);
}
function merge_sort(array) {
var aux = array.slice(0);
sort(array, aux, 0, array.length - 1);
return array;
}
return merge_sort(array);
}
console.time('measure');
mergeSort(arr);
console.timeEnd('measure');
console.log(arr[0], arr[1]);快速排序
var length = 10000000; // ten millions;
var arr = [];
for (let i = length; i > 0; i--) {
// random array
arr.push(parseInt(Math.random() * 1000000000));
}
function quickSort(arr, leftPos, rightPos, arrLength) {
let initialLeftPos = leftPos;
let initialRightPos = rightPos;
let direction = true;
let pivot = rightPos;
while ((leftPos - rightPos) < 0) {
if (direction) {
if (arr[pivot] < arr[leftPos]) {
quickSort.swap(arr, pivot, leftPos);
pivot = leftPos;
rightPos--;
direction = !direction;
} else
leftPos++;
} else {
if (arr[pivot] <= arr[rightPos]) {
rightPos--;
} else {
quickSort.swap(arr, pivot, rightPos);
leftPos++;
pivot = rightPos;
direction = !direction;
}
}
}
if (pivot - 1 > initialLeftPos) {
quickSort(arr, initialLeftPos, pivot - 1, arrLength);
}
if (pivot + 1 < initialRightPos) {
quickSort(arr, pivot + 1, initialRightPos, arrLength);
}
}
quickSort.swap = (arr, el1, el2) => {
let swapedElem = arr[el1];
arr[el1] = arr[el2];
arr[el2] = swapedElem;
}
arrLength = arr.length;
console.time('measure');
quickSort(arr, 0, arrLength - 1, arrLength);
console.log(arr[0], arr[1]);
console.timeEnd('measure');原生 Javascript 排序
var length = 10000000; // ten millions;
var arr = [];
for (let i = length; i > 0; i--) {
// random array
arr.push(parseInt(Math.random() * 100000000));
}
console.time('measure');
arr.sort(function compareNumbers(a, b) {
return a - b;
});
console.timeEnd('measure');
console.log(arr[0], arr[1]);最佳答案
那么为什么原生排序更慢呢？查看中的代码
https://github.com/v8/v8/blob/0c76b0ae850027006d5ec0d92449e449d996d3bb/src/js/array.js#L744
问题似乎是 GetThirdIndex()。当分区大小> 1000时调用它，我假设它用于防止快速排序最坏情况的性能，但开销很大，因为它创建内部对数组并对它们进行排序，并且这些对的排序可能导致进一步递归调用 GetThirdIndex()。这与与分割原始数组和分割内部对数组相关的递归调用相结合。
由于这些示例的测试数据是随机数据，因此 Relu 的快速排序不需要 GetThirdIndex() 之类的东西。还检查了数组中的“孔”，但我认为这并不重要。
GetThirdIndex() 的替代方法是中位数的就地中位数:
http://en.wikipedia.org/wiki/Median_of_medians
合并排序比快速排序更快，这些方法用于防止最坏的情况，但它需要一个与原始数组大小相同或一半大小的辅助数组。
Introsort 是快速排序和堆排序的混合体，如果递归级别太深，可以切换到堆排序:
http://en.wikipedia.org/wiki/Introsort
下面的第二个合并排序示例使用比较函数进行公平比较。它比 native 版本快得多。对于 Chrome，比较功能对整体时间影响不大。在 Firefox 的情况下，比较功能更有效。在火狐的情况下，原生版本因内存不足而失败，所以我无法比较。
这些是自顶向下合并排序的更快版本，原始发布者对此感到“好奇”，使用相互递归函数来避免复制和稍微优化的 merge()(每次比较两个条件)。
Firefox 的结果(时间略有不同)
native sort - failed for out of memory.
Relu's merge sort - 1.8 seconds
Relu's quick sort - 1.3 seconds
optimized merge sort - 1.4 seconds
optimized merge sort with compare - 1.8 seconds
Chrome 的结果(时间有所不同)
native sort - 5.3 seconds
Relu's merge sort - 2.1 seconds
Relu's quick sort - 1.8 seconds
optimized merge sort - 1.6 seconds
optimized merge sort with compare - 1.7 seconds
合并排序
var length = 10000000; // ten millions;
var arr = [];
for (let i = length; i > 0; i--) {
// random array
arr.push(parseInt(Math.random() * 1000000000));
}
var mergeSort = function(array) {
function merge(arr, aux, lo, mid, hi) {
var i = lo;
var j = mid + 1;
var k = lo;
while(true){
if(arr[i] <= arr[j]){
aux[k++] = arr[i++];
if(i > mid){
do
aux[k++] = arr[j++];
while(j <= hi);
break;
}
} else {
aux[k++] = arr[j++];
if(j > hi){
do
aux[k++] = arr[i++];
while(i <= mid);
break;
}
}
}
}
function sortarrtoaux(arr, aux, lo, hi) {
if (hi < lo) return;
if (hi == lo){
aux[lo] = arr[lo];
return;
}
var mid = Math.floor(lo + (hi - lo) / 2);
sortarrtoarr(arr, aux, lo, mid);
sortarrtoarr(arr, aux, mid + 1, hi);
merge(arr, aux, lo, mid, hi);
}
function sortarrtoarr(arr, aux, lo, hi) {
if (hi <= lo) return;
var mid = Math.floor(lo + (hi - lo) / 2);
sortarrtoaux(arr, aux, lo, mid);
sortarrtoaux(arr, aux, mid + 1, hi);
merge(aux, arr, lo, mid, hi);
}
function merge_sort(arr) {
var aux = arr.slice(0);
sortarrtoarr(arr, aux, 0, arr.length - 1);
return arr;
}
return merge_sort(array);
}
console.time('measure');
mergeSort(arr);
console.timeEnd('measure');
console.log(arr[0], arr[1]);使用比较功能合并排序
var length = 10000000; // ten millions;
var arr = [];
for (let i = length; i > 0; i--) {
// random array
arr.push(parseInt(Math.random() * 1000000000));
}
var mergeSort = function(array, comparefn) {
function merge(arr, aux, lo, mid, hi, comparefn) {
var i = lo;
var j = mid + 1;
var k = lo;
while(true){
var cmp = comparefn(arr[i], arr[j]);
if(cmp <= 0){
aux[k++] = arr[i++];
if(i > mid){
do
aux[k++] = arr[j++];
while(j <= hi);
break;
}
} else {
aux[k++] = arr[j++];
if(j > hi){
do
aux[k++] = arr[i++];
while(i <= mid);
break;
}
}
}
}
function sortarrtoaux(arr, aux, lo, hi, comparefn) {
if (hi < lo) return;
if (hi == lo){
aux[lo] = arr[lo];
return;
}
var mid = Math.floor(lo + (hi - lo) / 2);
sortarrtoarr(arr, aux, lo, mid, comparefn);
sortarrtoarr(arr, aux, mid + 1, hi, comparefn);
merge(arr, aux, lo, mid, hi, comparefn);
}
function sortarrtoarr(arr, aux, lo, hi, comparefn) {
if (hi <= lo) return;
var mid = Math.floor(lo + (hi - lo) / 2);
sortarrtoaux(arr, aux, lo, mid, comparefn);
sortarrtoaux(arr, aux, mid + 1, hi, comparefn);
merge(aux, arr, lo, mid, hi, comparefn);
}
function merge_sort(arr, comparefn) {
var aux = arr.slice(0);
sortarrtoarr(arr, aux, 0, arr.length - 1, comparefn);
return arr;
}
return merge_sort(array, comparefn);
}
console.time('measure');
mergeSort(arr, function compareNumbers(a, b) {
return a - b;
});
console.timeEnd('measure');
// check result
for (let i = 1; i < length; i++) {
if(arr[i] < arr[i-1]){
console.log('error');
break;
}
}
console.log(arr[0], arr[1]);旁注:原生排序不稳定:
原生 Javascript 排序 - 测试稳定性
var length = 100000;
var arr = [];
var j;
for (let i = 0; i < length; i++) {
j = parseInt(Math.random() * 100);
arr[i] = [j, i];
}
console.time('measure');
arr.sort(function compareNumbers(a, b) {
return a[0] - b[0];
});
console.timeEnd('measure');
for (let i = 1; i < length; i++) {
if( (arr[i][0] == arr[i-1][0]) &&
(arr[i][1] < arr[i-1][1]) ){
console.log('not stable');
console.log(arr[i-1][0], arr[i-1][1]);
console.log(arr[i ][0], arr[i ][1]);
break;
}
}原生 Javascript 排序 - 更改比较以使其稳定
var length = 100000;
var arr = [];
var j;
for (let i = 0; i < length; i++) {
j = parseInt(Math.random() * 100);
arr[i] = [j, i];
}
console.time('measure');
arr.sort(function compareNumbers(a, b) {
if(a[0] == b[0])
return a[1] - b[1];
return a[0] - b[0];
});
console.timeEnd('measure');
for (let i = 1; i < length; i++) {
if( (arr[i][0] == arr[i-1][0]) &&
(arr[i][1] < arr[i-1][1]) ){
console.log('not stable');
console.log(arr[i-1][0], arr[i-1][1]);
console.log(arr[i ][0], arr[i ][1]);
break;
}
}关于javascript - native JavaScript 排序的执行速度比实现的合并排序和快速排序慢，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/38732480/