Bitweise LSD-Sortierung (Radix-Sortierung)

Kürzlich veröffentlichte ich viele Artikel über verschiedene Sortieralgorithmen und deren Vergleich. Ich beschloss, meine eigenen fünf Cent zu verdienen.

Ich möchte über meinen Lieblingsalgorithmus für die bitweise Sortierung von LSD (niedrigstwertige Ziffer - zuerst das niedrigstwertige Bit) mit der Zählung (Radix-Sortierung) sprechen. Der klassische Algorithmus wurde vom Autor in Richtung einiger Optimierungen zugunsten von Beschleunigung und Einfachheit etwas überdacht.

Die vorgeschlagene Sortierung ist also nachhaltig. Wir werden die ganzzahligen 32-Bit-Zahlen sortieren. Um zu arbeiten, benötigen Sie ~ (n + 4 KB) zusätzlichen Speicher, was etwas verschwenderisch ist, aber eine gewisse Leistungssteigerung ermöglicht.

Bei dieser Art von LSD werden Vergleiche und Austausche nicht verwendet, der Algorithmus ist vollständig linear. Rechenkomplexität O (N).

Das Hauptmerkmal des Algorithmus ist die hohe Effizienz für stark gemischte oder zufällige Datensätze. Bei fast sortierten Mengen ist es sinnvoll, andere Algorithmen zu verwenden, da die Verstärkung nicht so signifikant ist. Bei kleinen Arrays mit weniger als ein paar hundert Elementen funktioniert dies nur schlecht.

Die Sortierung erfolgt lokal, um Speicherplatz zu sparen.

//================================================== // RADIX  (  by rebuilder) //   ,  . //   (n),   ~(n+4k) //================================================== procedure RSort(var m: array of Longword); //-------------------------------------------------- procedure Sort_step(var source, dest, offset: array of Longword; const num: Byte); var i,temp : Longword; k : Byte; begin for i := High(source) downto 0 do begin temp := source[i]; k := temp SHR num; dec(offset[k]); dest[offset[k]] := temp; end; end; //-------------------------------------------------- //    ,     var s : array[0..3] of array[0..255] of Longword; i,k : longword; //     k offset : array[0..3] of byte absolute k; m_temp : array of Longword; begin SetLength(m_temp, Length(m)); //    FillChar(s[0], 256 * 4 * SizeOf(Longword), 0); //   for i := 0 to High(m) do begin k := m[i]; Inc(s[0,offset[0]]); Inc(s[1,offset[1]]); Inc(s[2,offset[2]]); Inc(s[3,offset[3]]); end; //     for i := 1 to 255 do begin Inc(s[0,i], s[0,i-1]); Inc(s[1,i], s[1,i-1]); Inc(s[2,i], s[2,i-1]); Inc(s[3,i], s[3,i-1]); end; //         Sort_step(m, m_temp, s[0], 0); Sort_step(m_temp, m, s[1], 8); Sort_step(m, m_temp, s[2], 16); Sort_step(m_temp, m, s[3], 24); SetLength(m_temp, 0); end; //================================================== ... SetLength(m, n); for i := 0 to n - 1 do m[i] := Random(65536 * 65536); ... RSort(m); ... 

Der Code ist in Pascal geschrieben, aber es wird nicht schwierig sein, ihn in eine für Sie geeignete Sprache zu portieren.

Die Ausführungssequenz besteht aus zwei Phasen:

1. Für jeden Block (acht Binärziffern - 1 Byte (optimaler Wert)) wird durch Zählen seine Position in einem neuen Array berechnet.
2. Sequentiell für jeden Block (vom niedrigstwertigen bis zum höchsten) wird die zuvor berechnete Position angefahren.

Verbesserungen:

1. Für ein Array von Offsets verwenden wir die Ausrichtung im Speicher und aufgrund des kleinen Volumens wird es in L1 - dem Prozessor-Cache - platziert.
2. Das versetzte Array wird sofort für alle Ziffern gefüllt, sodass Sie nur einmal durch das Array gehen können, um zu zählen.
3. Die Positionsberechnung beginnt nicht am Anfang des Arrays, sondern löst am Ende zwei Probleme:
   
   • Das Ende des Arrays beim ersten Durchlauf befindet sich bereits im "aufgewärmten" Cache, was bei großen Arrays eine leichte Beschleunigung ergibt.
   • zweitens ist der absteigende Zyklus auf Null um einen Assembler-Befehl in jedem Schritt des Zyklus relativ zum aufsteigenden Zyklus kürzer.
4. Für jede Iteration (von vier) wird keine verschachtelte Schleife verwendet, wenn auch nicht so schön, aber es werden mehrere weitere Prozessoranweisungen gespeichert.

Aufgrund seiner Einfachheit ist der Code in der Geschwindigkeit sowohl für 32- als auch für 64-Bit-Compiler-Builds nahezu identisch. Bei Bedarf kann man sich leicht eine Version des Algorithmus für 16- und 64-Bit-Zahlen vorstellen.

Vergleich des Zufallsstichprobenalgorithmus mit der schnellen Sortierung auf einer 64-Bit-Plattform (durchschnittlich jeweils zehn Durchgänge).



Vorschläge und Kommentare zu Optimierungen sind willkommen.

Vielen Dank.