Родственный JavaScript сортировка выполняется медленнее, чем реализованные mergesort и quicksort

Question

Я реализовал слияние и quicksort, чтобы сравнить их с родной сортировкой JavaScript. Для quicksort я попытался использовать этот алгоритм: view algorithm on youtube. Оба алгоритма используют как можно меньше памяти, так как для сортировки слияния передается вспомогательный массив для каждого рекурсивного вызова (чтобы избежать накладных расходов), а для быстрой сортировки - позиции начального и конечного положения. Я использую сортировки для управления большими объемами данных в приложении NodeJs.

Ниже есть, быстрая сортировка слияния и родного род JavaScript, и вы можете проверить производительность

Вопрос: Почему родная JavaScript исполняющей медленнее?

В моем случае:

Chrome - сортировка слиянием: мера: 1997.920ms; quicksort: measure: 1755.740мс; native: measure: 4988.105ms
Узел: merge sort: measure: 2233.413ms; quicksort: measure: 1876.055ms; родной: мера: 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]);

Быстрая сортировка

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 Сортировка

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, и я предполагаю, что он используется для предотвращения производительности худшего случая quicksort, но накладные расходы значительны, поскольку он создает внутренние массивы пар и сортирует их, а сортировка этих пар может привести к дальнейшему рекурсивному вызывает GetThirdIndex(). Это сочетается с рекурсивными вызовами, связанными с разделением исходного массива и разбиением внутренних массивов пар.

Поскольку тестовые данные для этих примеров являются случайными данными, операционная система Relu не нуждается в чем-то вроде GetThirdIndex(). Есть также проверка на наличие «дыр» в массиве, но я предполагаю, что это не имеет значения.

Альтернатива GetThirdIndex() был бы на месте медиана медиан:

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

Merge сортировать быстрее, чем быстрая сортировка с этими методами, используемых для предотвращения наихудших сценариев, но ему нужен вспомогательный массив того же размера или половины размера исходного массива.

Introsort, который представляет собой гибрид сортировки и пирамидальной сортировки, переключение на пирамидальной сортировки, если уровень рекурсии становится слишком глубоко, может служить альтернативой:

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

Второй пример сортировка слиянием ниже использует функцию сравнения , чтобы провести справедливое сравнение. Это значительно быстрее, чем родная версия. В случае Chrome функция сравнения не сильно повлияла на общее время. В случае с Firefox функция сравнения имела больший эффект. В случае с Firefox родная версия потерпела неудачу из-за нехватки памяти, поэтому я не смог ее сравнить.

Это несколько более быстрые версии слияния сверху вниз, которые оригинальные плакаты были «любопытными», используя взаимно рекурсивные функции, чтобы избежать копирования и несколько оптимизированного слияния() (два условных выражения для сравнения).

Результаты с 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]);

Merge Сортировка с функцией сравнения

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]);

примечания стороны: родной сорт не является стабильным:

Native Javascript Sort - тест на стабильность

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 Сортировка - изменение сравнить, чтобы сделать его стабильным

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