admin管理员组文章数量:1201793
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]);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]);2 Answers
Reset to default 18So 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;
}
}I do not know how 14 is greater than 76 and 61
版权声明：本文标题：node.js - Native JavaScript sort performing slower than implemented mergesort and quicksort - Stack Overflow 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.betaflare.com/web/1738609020a2102523.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
<,>, or==– Hamms Commented Aug 3, 2016 at 1:03