javascript - native JavaScript 排序的执行速度比实现的合并排序和快速排序慢

Question

我已经实现了一个合并排序和一个快速排序来将它们与原生 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]);

Answer 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;
    }
}