http://jsperf.com/optimized-mergesort-versus-quicksort
Warum funktioniert diese Half-Buffer-Merge-Sortierung so schnell wie Quicksort?
Quicksort ist:
- In-Place, obwohl es dauert
log(n) Rekursionen (Stapelplatz)
- Cache-freundlich
Diese Half-Buffer-Merge-Sortierung:
- Verwendet ein
n/2 Puffer für Zusammenführungen.
- Verwendet
log(n) Rekursionen.
- Macht weniger Vergleiche.
Meine Frage ist, warum entspricht die Halbpuffer-Zusammenführungssortierung in diesem Szenario der Geschwindigkeit von QuickSort? Außerdem, mache ich irgendetwas falsch mit dem QuickSort, das es langsamer macht?
function partition(a, i, j) {
var p = i + Math.floor((j - i) / 2);
var left = i + 1;
var right = j;
swap(a, i, p);
var pivot = a[i];
while (left <= right) {
while (builtinLessThan(a[left], pivot)) {
++left;
}
while (builtinLessThan(pivot, a[right])) {
--right;
}
if (left <= right) {
swap(a, left, right);
++left;
--right;
}
}
swap(a, i, right);
return right;
};
function quickSort(a, i, j) {
var p = partition(a, i, j);
if ((p) - i > j - p) {
if (i < p - 1) {
quickSort(a, i, p - 1);
}
if (p + 1 < j) {
quickSort(a, p + 1, j);
}
} else {
if (p + 1 < j) {
quickSort(a, p + 1, j);
} if (i < p - 1) {
quickSort(a, i, p - 1);
}
}
};
Merge Sort führt weniger Vergleiche durch, aber mehr Moves als Quick Sort. Das Aufrufen einer Funktion zum Durchführen der Vergleiche erhöht den Overhead für Vergleiche, wodurch die schnelle Sortierung langsamer wird. All diese if-Anweisungen im Beispiel Quick Sort verlangsamen es auch. Wenn der Vergleich und der Austausch inline durchgeführt werden, sollte die schnelle Sortierung etwas schneller sein, wenn ein Array von pseudozufälligen Ganzzahlen sortiert wird.
Wenn auf einem Prozessor mit 16 Registern, wie einem PC im 64-Bit-Modus, ausgeführt wird, ist die 4-Wege-Zusammenführungssortierung mit einer Reihe von Zeigern, die in Registern landen, ungefähr so schnell wie die schnelle Sortierung. Eine 2-Wege-Merge-Sortierung vergleicht durchschnittlich 1 für jedes verschobene Element, während eine 4-Wege-Merge-Sortierung durchschnittlich 3 Vergleiche für jedes verschobene Element durchführt, aber nur die Hälfte der Anzahl von Durchgängen benötigt, sodass die Anzahl der grundlegenden Operationen gleich ist, aber die Vergleiche sind etwas Cache-freundlicher, wodurch die 4-Wege-Merge-Sortierung etwa 15% schneller wird, ungefähr gleich viel wie die schnelle Sortierung.
Ich bin nicht mit Java-Skript vertraut, also konvertiere ich die Beispiele in C++.
Mit einer konvertierten Version des Java-Skripts Merge Sort dauert es etwa 2,4 Sekunden, um 16 Millionen pseudozufällige 32-Bit-Ganzzahlen zu sortieren. Die unten gezeigte beispielhafte schnelle Sortierung dauert etwa 1,4 Sekunden, und die unten gezeigte beispielhafte Zusammenführung von unten nach oben dauert etwa 1,6 Sekunden. Wie bereits erwähnt, würde ein 4-Wege-Merge mit einer Reihe von Zeigern (oder Indizes) auf einem Prozessor mit 16 Registern ebenfalls etwa 1,4 Sekunden dauern.
Beispiel für eine schnelle Sortierung in C++:
void QuickSort(int a[], int lo, int hi) {
int i = lo, j = hi;
int pivot = a[(lo + hi) / 2];
int t;
while (i <= j) { // partition
while (a[i] < pivot)
i++;
while (a[j] > pivot)
j--;
if (i <= j) {
t = a[i]
a[i] = a[j];
a[j] = t;
i++;
j--;
}
}
if (lo < j) // recurse
QuickSort(a, lo, j);
if (i < hi)
QuickSort(a, i, hi);
}
C++-Bottom-Up-Merge-Sort-Beispiel:
void BottomUpMergeSort(int a[], int b[], size_t n)
{
size_t s = 1; // run size
if(GetPassCount(n) & 1){ // if odd number of passes
for(s = 1; s < n; s += 2) // swap in place for 1st pass
if(a[s] < a[s-1])
std::swap(a[s], a[s-1]);
s = 2;
}
while(s < n){ // while not done
size_t ee = 0; // reset end index
while(ee < n){ // merge pairs of runs
size_t ll = ee; // ll = start of left run
size_t rr = ll+s; // rr = start of right run
if(rr >= n){ // if only left run
rr = n;
BottomUpCopy(a, b, ll, rr); // copy left run
break; // end of pass
}
ee = rr+s; // ee = end of right run
if(ee > n)
ee = n;
BottomUpMerge(a, b, ll, rr, ee);
}
std::swap(a, b); // swap a and b
s <<= 1; // double the run size
}
}
void BottomUpMerge(int a[], int b[], size_t ll, size_t rr, size_t ee)
{
size_t o = ll; // b[] index
size_t l = ll; // a[] left index
size_t r = rr; // a[] right index
while(1){ // merge data
if(a[l] <= a[r]){ // if a[l] <= a[r]
b[o++] = a[l++]; // copy a[l]
if(l < rr) // if not end of left run
continue; // continue (back to while)
while(r < ee) // else copy rest of right run
b[o++] = a[r++];
break; // and return
} else { // else a[l] > a[r]
b[o++] = a[r++]; // copy a[r]
if(r < ee) // if not end of right run
continue; // continue (back to while)
while(l < rr) // else copy rest of left run
b[o++] = a[l++];
break; // and return
}
}
}
void BottomUpCopy(int a[], int b[], size_t ll, size_t rr)
{
while(ll < rr){ // copy left run
b[ll] = a[ll];
ll++;
}
}
size_t GetPassCount(size_t n) // return # passes
{
size_t i = 0;
for(size_t s = 1; s < n; s <<= 1)
i += 1;
return(i);
}
C++-Beispiel für eine 4-Wege-Merge-Sortierung mit Zeigern (Goto wird verwendet, um Codeplatz zu sparen, es ist alter Code). Es beginnt mit dem 4-Wege-Merge, und wenn das Ende eines Laufs erreicht ist, wechselt es zum 3-Wege-Merge, dann zum 2-Wege-Merge und dann zu einer Kopie des Rests des verbleibenden Laufs. Dies ähnelt Algorithmen, die für externe Sortierungen verwendet werden, aber die externe Sortierungslogik ist allgemeiner und verarbeitet häufig bis zu 16-Wege-Zusammenführungen.
int * BottomUpMergeSort(int a[], int b[], size_t n)
{
int *p0r; // ptr to run 0
int *p0e; // ptr to end run 0
int *p1r; // ptr to run 1
int *p1e; // ptr to end run 1
int *p2r; // ptr to run 2
int *p2e; // ptr to end run 2
int *p3r; // ptr to run 3
int *p3e; // ptr to end run 3
int *pax; // ptr to set of runs in a
int *pbx; // ptr for merged output to b
size_t rsz = 1; // run size
if(n < 2)
return a;
if(n == 2){
if(a[0] > a[1])std::swap(a[0],a[1]);
return a;
}
if(n == 3){
if(a[0] > a[2])std::swap(a[0],a[2]);
if(a[0] > a[1])std::swap(a[0],a[1]);
if(a[1] > a[2])std::swap(a[1],a[2]);
return a;
}
while(rsz < n){
pbx = &b[0];
pax = &a[0];
while(pax < &a[n]){
p0e = rsz + (p0r = pax);
if(p0e >= &a[n]){
p0e = &a[n];
goto cpy10;}
p1e = rsz + (p1r = p0e);
if(p1e >= &a[n]){
p1e = &a[n];
goto mrg201;}
p2e = rsz + (p2r = p1e);
if(p2e >= &a[n]){
p2e = &a[n];
goto mrg3012;}
p3e = rsz + (p3r = p2e);
if(p3e >= &a[n])
p3e = &a[n];
// 4 way merge
while(1){
if(*p0r <= *p1r){
if(*p2r <= *p3r){
if(*p0r <= *p2r){
mrg40: *pbx++ = *p0r++; // run 0 smallest
if(p0r < p0e) // if not end run continue
continue;
goto mrg3123; // merge 1,2,3
} else {
mrg42: *pbx++ = *p2r++; // run 2 smallest
if(p2r < p2e) // if not end run continue
continue;
goto mrg3013; // merge 0,1,3
}
} else {
if(*p0r <= *p3r){
goto mrg40; // run 0 smallext
} else {
mrg43: *pbx++ = *p3r++; // run 3 smallest
if(p3r < p3e) // if not end run continue
continue;
goto mrg3012; // merge 0,1,2
}
}
} else {
if(*p2r <= *p3r){
if(*p1r <= *p2r){
mrg41: *pbx++ = *p1r++; // run 1 smallest
if(p1r < p1e) // if not end run continue
continue;
goto mrg3023; // merge 0,2,3
} else {
goto mrg42; // run 2 smallest
}
} else {
if(*p1r <= *p3r){
goto mrg41; // run 1 smallest
} else {
goto mrg43; // run 3 smallest
}
}
}
}
// 3 way merge
mrg3123: p0r = p1r;
p0e = p1e;
mrg3023: p1r = p2r;
p1e = p2e;
mrg3013: p2r = p3r;
p2e = p3e;
mrg3012: while(1){
if(*p0r <= *p1r){
if(*p0r <= *p2r){
*pbx++ = *p0r++; // run 0 smallest
if(p0r < p0e) // if not end run continue
continue;
goto mrg212; // merge 1,2
} else {
mrg32: *pbx++ = *p2r++; // run 2 smallest
if(p2r < p2e) // if not end run continue
continue;
goto mrg201; // merge 0,1
}
} else {
if(*p1r <= *p2r){
*pbx++ = *p1r++; // run 1 smallest
if(p1r < p1e) // if not end run continue
continue;
goto mrg202; // merge 0,2
} else {
goto mrg32; // run 2 smallest
}
}
}
// 2 way merge
mrg212: p0r = p1r;
p0e = p1e;
mrg202: p1r = p2r;
p1e = p2e;
mrg201: while(1){
if(*p0r <= *p1r){
*pbx++ = *p0r++; // run 0 smallest
if(p0r < p0e) // if not end run continue
continue;
goto cpy11;
} else {
*pbx++ = *p1r++; // run 1 smallest
if(p1r < p1e) // if not end run continue
continue;
goto cpy10;
}
}
// 1 way copy
cpy11: p0r = p1r;
p0e = p1e;
cpy10: while (1) {
*pbx++ = *p0r++; // copy element
if (p0r < p0e) // if not end of run continue
continue;
break;
}
pax += rsz << 2; // setup for next set of runs
}
std::swap(a, b); // swap ptrs
rsz <<= 2; // quadruple run size
}
return a; // return sorted array
}
auf meiner Box ist es 30% langsamer.
– Thomas Jungblut
17. Januar 2016 um 22:42 Uhr
Nun, ich teste dies in Chrome und in Node. Im Knoten ist es doppelt so schnell wie Quicksort. In FireFox ist es 5% schneller als in Chrome.
– ahitt6345
17. Januar 2016 um 22:42 Uhr
Vergleiche sind billig. Optimiertes Quicksort macht ~2,5-mal weniger Swaps als Merge-Sort. Wenn also die Swap-Operation billig ist, ist die Zusammenführungssortierung schneller. Andernfalls gewinnt Quicksort.
– SaschaMN
17. Januar 2016 um 22:56 Uhr
Ich habe bereits teure Vergleiche getestet (Merge Sort war soooo viel schneller). Aber ich habe nie daran gedacht, teure (Swaps/Array-Zugriffe) zu testen. Irgendeine Idee, wie man das testet?
– ahitt6345
17. Januar 2016 um 23:24 Uhr
Der Link zu jsperf ist tot, daher kann ich nicht mehr sagen, was hier verglichen wird. Können wir den relevanten Code in diese Frage einfügen?
– ggorlen
18. September 2020 um 17:39 Uhr