原生JavaScript排序执行速度比实现的mergesort和quicksort慢 [英] Native JavaScript sort performing slower than implemented mergesort and quicksort
问题描述
我已经实现了mergesort和quicksort来将它们与原生JavaScript排序进行比较。对于快速排序我尝试使用此算法：在youtube上查看算法。两种算法都使用尽可能少的内存，对于合并排序，为每个递归调用传递辅助数组（以避免开销），对于快速排序，使用起始位置和结束位置的位置。我正在使用各种方法来管理NodeJs应用程序中的大量数据。
下面你有mergesort，quicksort和本地JavaScript排序，你可以测试性能
问题是：为什么本机JavaScript执行速度较慢？
在我的情况下：
Chrome - 合并排序：测量：1997.920ms;快速排序：措施：1755.740ms; native：measure：4988.105ms
节点：merge sort：measure：2233.413ms;快速排序：措施：1876.055ms; native：measure：6317.118ms
合并排序
var length =千万; //十亿; 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 ++];函数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）;合并（array，aux，lo，mid，hi）; function merge_sort（array）{var aux = array.slice（0）; sort（array，aux，0，array.length - 1）;返回数组; } return merge_sort（array）;} console.time（'measure'）; mergeSort（arr）; console.timeEnd（'measure'）; console.log（arr [0]，arr [1]）;
Quicksort
var length = 10000000; //十亿; 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;让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--;方向=！方向; } else leftPos ++; } else {if（arr [pivot]< = arr [rightPos]）{rightPos--; } else {quickSort.swap（arr，pivot，rightPos）; leftPos ++; pivot = rightPos;方向=！方向; 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; //十亿; 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，它是quicksort和heapsort的混合体，如果递归级别太深，则会转换为heapsort： / p>
http://en.wikipedia.org/wiki / Introsort
下面的第二个合并排序示例使用比较函数进行公平比较。它比原生版本快得多。对于Chrome，比较功能不会对整体时间产生太大影响。在Firefox的情况下，比较功能有更多的影响。在Firefox的情况下，本机版本因内存不足而失败，因此我无法对此进行比较。
这些是自顶向下合并排序的更快版本海报是好奇的，使用相互递归的函数来避免复制和稍微优化的merge（）（每次比较两个条件）。
Firefox的结果（时间有所不同）
本机排序 - 内存不足失败。
Relu的合并排序--1.8秒
Relu快速排序 - 1.3秒
优化合并排序 - 1.4秒
优化合并排序与比较 - 1.8秒
Chrome结果（时间有所不同）
原生排序 - 5.3秒
Relu的合并排序 - 2.1秒
Relu快速排序 - 1.8秒
优化合并排序--1.6秒
优化合并排序与比较 - 1.7秒
合并排序
var length = 10000000; //十亿; 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 ++];而（j <= hi）;打破; } else {aux [k ++] = arr [j ++]; if（j> hi）{do aux [k ++] = arr [i ++];而（i <= mid）;打破;函数sortarrtoaux（arr，aux，lo，hi）{if（hi< lo）return; if（hi == lo）{aux [lo] = arr [lo];返回; } var mid = Math.floor（lo +（hi - lo）/ 2）; sortarrtoarr（arr，aux，lo，mid）; sortarrtoarr（arr，aux，mid + 1，hi）;合并（arr，aux，lo，mid，hi）;函数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）;合并（aux，arr，lo，mid，hi）;函数merge_sort（arr）{var aux = arr.slice（0）; sortarrtoarr（arr，aux，0，arr.length - 1）;返回} return merge_sort（array）;} console.time（'measure'）; mergeSort（arr）; console.timeEnd（'measure'）; console.log（arr [0]，arr [1]）;
合并排序与比较功能
var length = 10000000; //十亿; 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 ++];而（j <= hi）;打破; } else {aux [k ++] = arr [j ++]; if（j> hi）{do aux [k ++] = arr [i ++];而（i <= mid）;打破;函数sortarrtoaux（arr，aux，lo，hi，comparefn）{if（hi< lo）return; if（hi == lo）{aux [lo] = arr [lo];返回; } var mid = Math.floor（lo +（hi - lo）/ 2）; sortarrtoarr（arr，aux，lo，mid，comparefn）; sortarrtoarr（arr，aux，mid + 1，hi，comparefn）;合并（arr，aux，lo，mid，hi，comparefn）;函数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）;合并（aux，arr，lo，mid，hi，comparefn）;函数merge_sort（arr，comparefn）{var aux = arr.slice（0）; sortarrtoarr（arr，aux，0，arr.length - 1，comparefn）;返回} return merge_sort（array，comparefn）;} console.time（'measure'）; mergeSort（arr，function compareNumbers（a，b）{return a - b;}）; console.timeEnd（'measure'）; //检查resultfor（let i = 1; i< length; i ++）{if（arr [i]< arr [i-1]）{console.log（'error'）;打破; 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]）;打破; }
原生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];返回[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（'不稳定）; console.log（arr [i-1] [0]，arr [i-1] [1]）; console.log（arr [i] [0]，arr [i] [1]）;打破; }
I've implemented a mergesort and a quicksort to compare them with the native JavaScript sort. For the quicksort I've tried to use this algorithm: view algorithm on youtube. Both algorithms use as less memory as possible, for the merge sort an auxiliary array is passed for each recursive call (to avoid overheads) , and for the quicksort, positions of the starting and ending positions. I'm using sorts to manage large amounts of data in a NodeJs app.
Below you have the mergesort, quicksort and native JavaScript sort and you can test the performance
The question is: Why is the native JavaScript performing slower ?
In my case:
Chrome - merge sort: measure: 1997.920ms; quicksort: measure: 1755.740ms; native : measure: 4988.105ms
Node: merge sort: measure: 2233.413ms; quicksort: measure: 1876.055ms; native: measure: 6317.118ms
Merge Sort
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]);
Quicksort
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');
Native Javascript Sort
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]);
So why is the native sort slower? Looking at the code in
https://github.com/v8/v8/blob/0c76b0ae850027006d5ec0d92449e449d996d3bb/src/js/array.js#L744
The issue seems to be GetThirdIndex(). It gets called when partition size is > 1000, and I assume it's used to prevent quicksort worst case performance, but the overhead is significant, as it creates internal arrays of pairs and sorts those, and the sorting of those pairs can result in further recursive calls to GetThirdIndex(). This is combined with the recursive calls related to partitioning the original array and to partitioning the internal arrays of pairs.
Since the test data for these examples is random data, Relu's quicksort doesn't need something like GetThirdIndex(). There's also the check for "holes" in the array, but I assume this isn't significant.
An alternative to GetThirdIndex() would be an in place median of medians:
http://en.wikipedia.org/wiki/Median_of_medians
Merge sort is faster than quicksort with these methods used to prevent worst case scenarios, but it needs an auxiliary array the same size or half the size of the original array.
Introsort, which is a hybrid of quicksort and heapsort, switching to heapsort if the level of recursion gets too deep would be an alternative:
http://en.wikipedia.org/wiki/Introsort
The second merge sort example below uses a compare function, to make a fair comparison. It's significantly faster than the native version. In the case of Chrome, a compare function didn't affect the overall time much. In the case of Firefox, the compare function had more effect. In the case of Firefox, the native version failed for out of memory so I couldn't compare that.
These are somewhat faster versions of top down merge sort which the original poster was "curious" about, using mutually recursive functions to avoid copy and somewhat optimized merge() (two conditionals per compare).
Results with Firefox (times vary somewhat)
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
Results with Chrome (times vary somewhat)
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
Merge Sort
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]);
Merge Sort with compare function
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]);
Side note: native sort is not stable:
Native Javascript Sort - test for stability
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;
}
}
Native Javascript Sort - change compare to make it stable
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慢的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
