Hierbei handelt es sich um die Parallelisierung der Original-Variante.
Die Beschreibung der Parallelisierung in Variante 1 ist sehr ungenau. Deshalb finden Sie hier den exakten (besser realisierbaren) Code.
Damit diese Parallelisierung korrekt funktioniert, muß das CREW-Modell (concurrent read, exclusive write) ermöglicht werden.
Variante | 4.a (iterativ) |
Typ | standard |
Eigenschaften | iterativ, in-place, stabil, parallelisierbar |
Datenstrukturen | Felder, einfachverkettete Listen |
Speicher | Ω(1) | Θ(1) | Ο(1) |
Laufzeit (p) | Ω(n) | Θ(n) | Ο(n) |
Laufzeit | Ω(n²) | Θ(n²) | Ο(n²) |
Vergleiche | n²/2 | n²/2 | n²/2 |
Vertauschungen | 0 | n²/16 | n²/2 |
simplesort(field A, int l, int r) {
for i:=0 to r-l-1 do {
for j:=0 to i do parallel {
if (A[l+j] >= A[r-i+j]) then {
exchange(A[l+j], A[r-i+j]);
}
}
}
}
| |
Variante | 4.b (rekursiv) |
Typ | standard |
Eigenschaften | rekursiv, in-place, stabil, parallelisierbar |
Datenstrukturen | Felder, einfachverkettete Listen |
Speicher | Ω(n) | Θ(n) | Ο(n) |
Laufzeit (p) | Ω(n) | Θ(n) | Ο(n) |
Laufzeit | Ω(n²) | Θ(n²) | Ο(n²) |
Vergleiche | n²/2 | n²/2 | n²/2 |
Vertauschungen | 0 | n²/16 | n²/2 |
simplesort(field A, int l, int r) {
if (l < r) then {
simplesort(A, l, r, r-l-1);
}
}
simplesort(field A, int l, int r, int i) {
if (i >= 0) {
simplesort(A, l, r, i-1);
simple(A, l, r-i, i);
}
}
simple(field A, int l, int r, int j) {
if (j >= 0) then {
do parallel {
if (A[l+j] >= A[r+j]) then {
exchange(A[l+j], A[r+j]);
}
simple(A, l, r, j-1);
}
}
}
| |
Simplesort, Variante 4
|