75 lines
4.4 KiB
Typst
75 lines
4.4 KiB
Typst
|
#import "@preview/rubber-article:0.5.0": *
|
||
|
|
|
||
|
|
#show: article.with(lang: "de")
|
||
|
|
|
||
|
|
#maketitle(
|
||
|
|
title: "AE2025: MSD-Radix-Sort + Robin-Hood-Sort",
|
||
|
|
authors: ("Patrick Schneider, urulu, 2352014",),
|
||
|
|
date: "30. September 2025",
|
||
|
|
)
|
||
|
|
|
||
|
|
= Implementierter Algorithmus
|
||
|
|
Implementiert wurde ein inplace MSD-Radix Sortieralgorithmus mit $2^r$ Buckets. Dabei wird dieser rekursiv auf den Buckets aufgerufen. Unterschreitet ein Bucket die vorgegebene Schranke $r h$, so wird vom MSD-Radix zu einem Robin-Hood Sortieralgorithmus gewechselt. Dieser ist nicht in-place implementiert.
|
||
|
|
|
||
|
|
Als Datenstruktur ist eine Array-Struktur wie in der Vorlesung (vgl. Folie 34) implementiert mit 64 Elementen pro Array.
|
||
|
|
|
||
|
|
== Inplace MSD-Radix
|
||
|
|
Zu gegebenem $n$, $r$ und Interval $[a,b)$ wird zunächst für jeden Bucket $b_i, i in {1...2^r}$ gezählt, wie viele Elemente diesem zugeteilt werden. Daraus werden die Startpositionen $s_i$ der Buckets iterativ erstellt, wobei wir die Endpositionen $t_i := s_i$ initialisieren. Anschließend wird über das Array iteriert und die Elemente $e_i$ entsprechend in die Buckets wie folgt einsortiert, wobei $b_j$ der Bucket von $e_i$ ist:
|
||
|
|
|
||
|
|
- Fall 1: $i in [s_j, t_j)$
|
||
|
|
|
||
|
|
$e_i$ ist bereits im richtigen Bucket, also wird das Ende des Buckets ($t_j <- t_j + 1$) vergrößert und mit $e_(i+1)$ fortgeführt.
|
||
|
|
|
||
|
|
- Fall 2: $i in.not [s_j, t_j)$
|
||
|
|
|
||
|
|
$e_i$ ist im falschen Bucket. also wird $e_i$ mit $e_(t_j)$ getauscht, das Ende des Buckets $b_j$ vergrößert und mit $e_i$ fortgeführt.
|
||
|
|
|
||
|
|
Hat ein Bucket mehr als $r h$ Elemente, so wird auf diesem erneut der MSD-Radix aufgerufen. Entsprechend wird die nächste Stelle angeschaut, hier implementiert durch das Verschieben der Maske um $d * r$ Bits nach links, wobei $d$ die entsprechende Rekursionstiefe ist.
|
||
|
|
Erneute Aufrufe von MSD-Radix werden durch einen Threadpool parallel abgearbeitet.
|
||
|
|
|
||
|
|
== Robin-Hood-Sort
|
||
|
|
Wie auf dem Aufgabenblatt beschrieben implementiert. Kollisionen durch linear-probing aufgelöst.
|
||
|
|
|
||
|
|
= Implementierte Optimierungen
|
||
|
|
|
||
|
|
1. Multithreading:
|
||
|
|
|
||
|
|
Anstelle immer einen neuen Thread zu erstellen, wird ein Threadpool verwendet, um so Aufwand zu sparen.
|
||
|
|
|
||
|
|
Um den Aufwand der Parallelisierung bei nur einem Thread zu vermeiden, wird ein Sentinel-TaskHandler eingesetzt, der Aufgaben direkt erledigt (vgl. @thread t1r8 mit t2r8).
|
||
|
|
|
||
|
|
Da ein MSD-Radix Durchlauf schnell erledigt ist, hat jeder Thread eine eigene Task-Queue um Synchronisierungsoverhead durch Mutexe zu reduzieren. Erst dadurch war die parallele Version schneller als die sequentielle (vgl. @old-thread).
|
||
|
|
Das führt von einem Speedup von ca. 2.
|
||
|
|
|
||
|
|
2. MSD-Radix:
|
||
|
|
|
||
|
|
Fall 1 wie oben erzwingt, dass jedes Element bis zu zwei mal angeschaut werden muss. Stattdessen kann direkt zum Ende des zugehörigen Buckets gesprungen werden, da die Elemente per Induktion schon richtig einsortiert sind. Das resultiert in $tilde n + 2^k$ angeschauten Elementen.
|
||
|
|
|
||
|
|
Durch die Experimente sieht man, wie für statisches $k$ die Laufzeit bei verschiedenem $n$ variiert (vgl. @constant-radix). Eine dynamische Wahl in Abhängigkeit der Anzahl an Elementen könnte ein besseres Resultat erbringen. Dabei wird die Anzahl an Buckets anhand der Formel
|
||
|
|
|
||
|
|
$ k = max{2, floor(log_2(n))/(r)} $
|
||
|
|
|
||
|
|
gewählt, wobei $r$ dem negativen Parameter aus den Tests entspricht (vgl. @dynamic-radix). Dabei wurden keine Verbesserungen festgestellt.
|
||
|
|
|
||
|
|
== Tests
|
||
|
|
Die folgenden Parameter wurden in jeglicher Kombination getestet:
|
||
|
|
|
||
|
|
- Threadanzahl $t$: 1, 2, 4, 8, 12, 16
|
||
|
|
- Small-Sort-Threshold $r h$: 64, 128, 256
|
||
|
|
- Anzahl Radix-Buckets $2^k$: -3, -2, -1, 1, 2, 4, 6, 8, 10, 12
|
||
|
|
- Anzahl Elemente $n$: $10^2, 10^3, 10^4 + 1, 10^5, 10^6 - 1, 10^7, 10^8, 2 * 10^8$
|
||
|
|
|
||
|
|
Entsprechend sind die Versuchsdurchläufe bezeichnet, wobei $r-{3,2,1}$ den entsprechend dynamisch berechneten Radix bezeichnet.
|
||
|
|
Manche Konfigurationen (z.B. $r h=64, n>=10^8, r=12$) führten zu Abstürzen oder Fehlern in der Sortierung. Das liegt an der statischen Wahl des Radix, in der 5. Rekursionstiefe können dann noch Buckets mit mehr als 64 Elementen sein, auf denen dann wieder ein 12-Bit Radix ausgeführt wird, was nicht möglich ist.
|
||
|
|
|
||
|
|
Die Wahl eines höheren $r h$ führt zu einem Anstieg der Laufzeit (vgl. @rh), wobei dieser nicht konsistent ist.
|
||
|
|
#grid(columns: 2,
|
||
|
|
|
||
|
|
[ #figure(image("plots/thread-r8-rh256.svg"))<thread> ],
|
||
|
|
[ #figure(image("plots/old-thread-r8-rh128.svg"))<old-thread> ],
|
||
|
|
[ #figure(image("plots/varying-rh.svg"))<rh> ],
|
||
|
|
[],
|
||
|
|
[ #figure(image("plots/constant-r-rh128.svg"))<constant-radix> ],
|
||
|
|
[ #figure(image("plots/dynamic-r-rh128.svg"))<dynamic-radix> ],
|
||
|
|
)
|