Die native JavaScript-Sortierung ist langsamer als die implementierte Zusammenführung von Mergesort und Quicksort

Relus Mesaros:

Ich habe einen Mergesort und einen Quicksort implementiert, um sie mit der nativen JavaScript-Sortierung zu vergleichen. Für den Quicksort habe ich versucht, diesen Algorithmus zu verwenden: Algorithmus auf youtube anzeigen . Beide Algorithmen verbrauchen so wenig Speicher wie möglich. Für die Zusammenführungssortierung wird für jeden rekursiven Aufruf ein Hilfsarray übergeben (um Overheads zu vermeiden) und für die Quicksortierung die Positionen der Start- und Endpositionen. Ich verwende Sortierungen, um große Datenmengen in einer NodeJs-App zu verwalten.

Im Folgenden finden Sie die Sortierung von Mergesort, Quicksort und nativem JavaScript. Sie können die Leistung testen

Die Frage ist: Warum arbeitet das native JavaScript langsamer?

In meinem Fall:

Chrome - Merge Sort: Measure: 1997.920ms; Quicksort: Maßnahme: 1755,740 ms; native: Measure: 4988.105ms
Knoten: Merge Sort: Measure: 2233.413ms; Quicksort: Maßnahme: 1876,055 ms; native: Maßnahme: 6317,118 ms

Zusammenführen, sortieren

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

Schnelle Sorte

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

rcgldr:

Warum ist die native Sorte langsamer? Betrachten Sie den Code in

https://github.com/v8/v8/blob/0c76b0ae850027006d5ec0d92449e449d996d3bb/src/js/array.js#L744

Das Problem scheint GetThirdIndex () zu sein. Es wird aufgerufen, wenn die Partitionsgröße> 1000 ist, und ich gehe davon aus, dass es verwendet wird, um die QuickSort-Worst-Case-Leistung zu verhindern. Der Overhead ist jedoch erheblich, da interne Arrays von Paaren erstellt und diese sortiert werden und das Sortieren dieser Paare zu einer weiteren Rekursion führen kann ruft GetThirdIndex () auf. Dies wird mit den rekursiven Aufrufen kombiniert, die sich auf die Partitionierung des ursprünglichen Arrays und die Partitionierung der internen Arrays von Paaren beziehen.

Da es sich bei den Testdaten für diese Beispiele um Zufallsdaten handelt, benötigt Relus Quicksort nicht so etwas wie GetThirdIndex (). Es gibt auch die Überprüfung auf "Löcher" im Array, aber ich gehe davon aus, dass dies nicht signifikant ist.

Eine Alternative zu GetThirdIndex () wäre ein vorhandener Median der Mediane:

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

Mit diesen Methoden, die zur Vermeidung von Worst-Case-Szenarien verwendet werden, ist die Zusammenführungssortierung schneller als die Quicksortierung. Sie benötigt jedoch ein Hilfsarray, das dieselbe oder die halbe Größe des ursprünglichen Arrays hat.

Introsort, eine Mischung aus Quicksort und Heapsort, und eine Umstellung auf Heapsort, wenn der Rekursionsgrad zu tief wird, wäre eine Alternative:

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

Das folgende Beispiel für eine zweite Zusammenführungssortierung verwendet eine Vergleichsfunktion, um einen fairen Vergleich durchzuführen. Es ist deutlich schneller als die native Version. Im Fall von Chrome hatte eine Vergleichsfunktion keinen großen Einfluss auf die Gesamtzeit. Im Fall von Firefox hatte die Vergleichsfunktion mehr Wirkung. Im Fall von Firefox ist die native Version wegen fehlenden Speichers fehlgeschlagen, daher konnte ich das nicht vergleichen.

Dies sind etwas schnellere Versionen der Top-Down-Zusammenführungssortierung, auf die das Originalposter "neugierig" war, wobei gegenseitig rekursive Funktionen verwendet wurden, um ein Kopieren und eine etwas optimierte Zusammenführung () zu vermeiden (zwei Bedingungen pro Vergleich).

Ergebnisse mit Firefox (Zeiten variieren etwas)

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

Ergebnisse mit Chrome (Zeiten variieren etwas)

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

Zusammenführen, sortieren

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

Sortierung mit Vergleichsfunktion zusammenführen

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

Randnotiz: native Sortierung ist nicht stabil:

Native Javascript Sort - Test auf Stabilität

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 - Ändern Sie den Vergleich, um ihn stabil zu machen

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

Dieser Artikel stammt aus dem Internet. Bitte geben Sie beim Nachdruck die Quelle an.

Bei Verstößen wenden Sie sich bitte [email protected] Löschen.

bearbeiten am2020-07-16

Lass mich ein paar Worte sagen

0Kommentare

LoginNach der Teilnahme an der Überprüfung

TOP Liste

Artikel