18
Zrobiłem mały test i okazało się, że array.sort(function(a, b) { return a - b; }); jest dużo szybszy niż array.sort(); w JavaScript.JavaScript, sortowanie z drugim parametrem jest szybsze
Wyniki były dość szokujące, około 1,7 razy szybciej w IE9, 1,6 razy w FF7 i 6,7 razy w Chrome.
Ponadto, implementując quicksort samodzielnie w JS, stwierdziłem, że był on szybszy niż obie wyżej wymienione metody. (Dwie różne implementacje, jedna akceptuje funkcję porównywania jako parametr, druga nie. Oba były szybsze.)
Czy istnieje uzasadnione wytłumaczenie?
EDIT: Moje implementacje:
Nie comparer:
function quickSort(array, from, to) {
if(typeof from === 'undefined') {
from = 0;
to = array.length - 1;
}
else if(typeof to === 'undefined') {
to = array.length - 1;
}
if(to - from < 1) {
return;
}
var i = from, pivot = to, t;
while(i < pivot) {
if(array[i] > array[pivot]) {
t = array[i];
array[i] = array[pivot - 1];
array[pivot - 1] = array[pivot];
array[pivot] = t;
pivot--;
}
else {
i++;
}
}
quickSort(array, from, pivot - 1);
quickSort(array, pivot + 1, to);
}
Z comparer:
function quickSortFunc(array, sortfunc, from, to) {
if(typeof from === 'undefined') {
from = 0;
to = array.length - 1;
}
else if(typeof to === 'undefined') {
to = array.length - 1;
}
if(to - from < 1) {
return;
}
var i = from, pivot = to, t;
while(i < pivot) {
if(sortfunc(array[i], array[pivot]) > 0) {
t = array[i];
array[i] = array[pivot - 1];
array[pivot - 1] = array[pivot];
array[pivot] = t;
pivot--;
}
else {
i++;
}
}
quickSortFunc(array, sortfunc, from, pivot - 1);
quickSortFunc(array, sortfunc, pivot + 1, to);
}
jest możliwość, że funkcja sortowania jest prowadzony od średnich. Jak duże były używane tablice? – Matt
Sortowanie "normalne" działa na reprezentację łańcuchów elementów. To może być możliwe narzut. –
Matt, przetestowałem go na tablicach 100, 1000, 10000 i 100000 elementów. Felix, ja o tych dwóch, to wciąż nie wyjaśnia, dlaczego moja implementacja z porównywarką była szybsza niż natywna implementacja z porównywarką. –