当前位置: 首页 > 面试题库 >

本机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实现快速排序(Quicksort)的算法详解,包括了Javascript实现快速排序(Quicksort)的算法详解的使用技巧和注意事项,需要的朋友参考一下 目前,最常见的排序算法大概有七八种,其中"快速排序"(Quicksort)使用得最广泛,速度也较快。它是图灵奖得主C. A. R. Hoare(1934--)于1960时提出来的。 "快速排序"的思想很简单,

  • 本文向大家介绍基于javascript实现的快速排序,包括了基于javascript实现的快速排序的使用技巧和注意事项,需要的朋友参考一下     "妙味课堂"的一期视频教学。 主要原理是:快速排序的原理:找基准点、建立二个数组分别存储、递归 基准点:就是找到这个数组中间的一个数; 建立二个数组分别存储:就是以这个基准点,将它的左右数值,分别存放到两个定义的新数组当中; 递归:在函数内部调用自身;

  • 本文向大家介绍javascript与Python快速排序实例对比,包括了javascript与Python快速排序实例对比的使用技巧和注意事项,需要的朋友参考一下 本文实例对比了javascript与Python快速排序实现方法。分享给大家供大家参考。具体如下: js实现方法: python实现方法: 希望本文所述对大家的javascript及Python程序设计有所帮助。

  • 问题 用快速排序对长度为 n 的无序序列 s 进行排序。 解法 本问题对无序序列 s 进行升序排序,排序后 s 是从小到大的。 将长度为 n 的序列 s ,选取最左边的值作为 pivot ,将剩余部分分为 left 和 right 两个部分, left 和 right 是无序的,且 left 中的所有元素 forall x le pivot (其中 x in left ), right 中的所有元

  • 我极度困惑。其中一个测验问题是"True or False, Quick ort在算法的征服阶段实现排序",我选择了true,因为我记得读过: 快速排序的三个步骤如下: 分割:重新排列元素,并将阵列分割为两个子阵列和中间的一个元素,以便左子阵列中的每个元素小于或等于中间元素,右子阵列中的每个元素大于中间元素。 征服:递归地对两个子数组排序。 组合:无。 然而,测验的答案说答案是错误的,没有任何解释

  • 我正在尝试测试Aparapi的性能。我看到过一些博客,其中的结果显示,Aparapi确实在做数据并行操作的同时提高了性能。 但我在测试中没有看到这一点。这里是我所做的,我写了两个程序,一个使用Aparapi,另一个使用普通循环。 方案1:在Aparapi 程序2:使用循环 程序1需要大约330ms,而程序2只需要大约55ms。我是不是做错什么了?我在Aparpai程序中打印出了执行模式,它打印出的