Подтвердить что ты не робот

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

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

Ниже вы можете использовать сортировку mergesort, quicksort и native JavaScript, и вы можете протестировать производительность

Возникает вопрос: почему собственный JavaScript работает медленнее?

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

Chrome - merge sort: measure: 1997.920ms; quicksort: measure: 1755.740мс; родной: мера: 4988.105ms
Node: merge sort: measure: 2233.413ms; quicksort: measure: 1876.055ms; native: measure: 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]);
4b9b3361

ОТВЕТЫ

Ответ 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

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

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

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

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

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

Результаты с Firefox (времена несколько меняются)

native sort - failed for out of memory.
Relu merge sort - 1.8 seconds
Relu 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 merge sort - 2.1 seconds
Relu 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]);