本机JavaScript排序的执行速度比已实现的mergesort和quicksort慢

龙承德

2023-03-14

问题内容：

我已经实现了mergesort和quicksort来将它们与本机JavaScript排序进行比较。对于快速排序，我尝试使用此算法：在youtube上查看算法。两种算法都使用尽可能少的内存，对于合并排序，将为每个递归调用传递辅助数组（以避免开销），对于快速排序，将传递起始位置和结束位置。我正在使用排序来管理NodeJs应用程序中的大量数据。

在下面有mergesort，quicksort和本机JavaScript排序，您可以测试性能

问题是：为什么本机JavaScript的执行速度较慢？

就我而言：

Chrome-合并排序：度量：1997.920ms；快速排序：测量：1755.740ms; native：度量：4988.105ms
节点：合并排序：度量：2233.413ms; 快速排序：测量：1876.055ms; 母语：措施：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的quicksort不需要GetThirdIndex（）之类的东西。数组中也有“空洞”的检查，但我认为这并不重要。

GetThirdIndex（）的替代方法是就地中位数：

http://en.wikipedia.org/wiki/Median_of_medians

使用这些方法来防止最坏情况的合并排序比快速排序更快，但是合并排序需要的辅助数组的大小与原始数组的大小相同或一半。

Introsort是quicksort和heapsort的混合体，如果递归级别太深，则切换到heapsort是一种替代方法：

http://en.wikipedia.org/wiki/Introsort

下面的第二个合并排序示例使用一个compare函数进行公平的比较。它比本机版本快得多。对于Chrome，比较功能对整体时间的影响不大。对于Firefox，比较功能具有更大的作用。对于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排序的执行速度比已实现的mergesort和quicksort慢

相关阅读

相关文章

相关问答

相关工具

相关文档