Java Tuning - Sortieralgorithmen

0. Inhalt

1. Einleitung

2. Unnötigen Sortieraufwand vermeiden

3. Ein effizienten Sortier-Framework

4. Schneller Sortieren als O(nlogn)

5. Performance-Checkliste

6. Performance-Test

A. Anhang

A.1 Paper von Karl-Friedrich Neubert von der euroFORTH'97 –Konferenz

A.2 Beschreibung des Flashsort-Algorithmus aus der Zeitschrift Dr. Dobb's Journal vom Februar 1998.

A.3 Quelltexte

1. Einleitung

Sortier-Algorithmen gehören neben den Such-Algorithmen zu den meistbenutzten Funktionen in der Informatik.

So werden z.B. in jeder Datenbank-Anwendung Sortier-Algorithmen eingesetzt, welche dort die Leistungsfähigkeit der Anwendung stark bedingen.

Gerade deshalb besteht ein erhöhter Bedarf daran, diese Algorithmen so leistungsfähig und schnell wie möglich zu machen, um somit die Performance der benutzenden Anwendungen zu steigern.

Hierzu gibt es viele Möglichkeiten, von der einfachen Vermeidung von überflüssigem Aufwand bei Typumwandlungen, über die Erstellung eines Sortier-Frameworks, welches automatisch bestimmte Optimierungen vornimmt, bis zur Implementierung spezialisierter Algorithmen, welche zusätzliche Informationen aus den zu sortierenden Objekten benutzen.

Auf diese Möglichkeiten soll im Folgenden detaillierter eingegangen werden. Sie alle stammen aus dem Buch „Java Performance Tuning“, Kapitel 9 von Jack Shirazi und werden im Verlauf dieser Arbeit implementiert und getestet.

2. Unnötigen Sortier-Aufwand vermeiden

Das JDK bringt viele Sortier-Methoden mit sich, welche zum Sortieren von Arrays (java.util.Arrays) und Collections (java.util.Collections) benutzt werden können. Diese Algorithmen sind normalerweise für kleinere Anwendungen völlig ausreichend.

Wenn es aber um spezialisierte Anwendungen geht, welche häufig große Datenmengen sortieren müssen, bieten diese Methoden häufig nicht mehr die benötigte Performance. Oftmals erhält man aber schon die nötige Leistungssteigerung, indem man einfach einen Standard-Sortier-Algorithmus wie Quicksort direkt in die zu sortierende Klasse implementiert.

Nur sehr stark spezialisierte Anwendungen benötigen gewöhnlich auch sehr spezialisierte Sortier-Algorithmen.

Quicksort-Tuning:

Als Beispiel soll eine einfache Klasse genommen werden, die nur eine Integer- Variable besitzt, welche sortiert werden muss.

Eine Implementierung kann aussehen wie in

- class Sortable implements Comparable

beschrieben.

Objekte dieser Klasse könnten nun mit der Methode Arrays.sort() sortiert werden. Da aber ein direkter Vergleich mit exakt dem selben Sortier-Algorithmus, der im Folgenden verbessert wird, gemacht werden soll, wird hier ein Standard- Quicksort-Algorithmus verwendet. Die einzige Modifizierung dieses Quicksort wird sein, dass für jede Optimierung eine geeignete Vergleichs-Methode sowie der geeignete Datentyp verwendet wird.

Implementierungen:

- class StandardQuicksort
- class QuicksortComparable
- class QuicksortInt

Natürlich könnte man das zu sortierende Array vom Typen Object anlegen. Die Vergleiche werden jedoch mit der Methode Coparator.compareTo() gemacht, so das jedes Objekt die Comparable-Schnittstelle implementieren müsste.

Wenn aber jedes Objekt ein auch ein Comparable ist, warum deklariert man nicht gleich ein Comparable-Array anstatt eines Object-Arrays und verhindert so eine unnötige Typumwandlung?

Es ist also viel schneller, eine Vergleichs-Methode zu benutzen, die eine

Comparable-Signatur verwendet.

Man kann den Quicksort noch weiter verändern, so dass er auch die eben beschriebenen Sortable-Objekte verarbeiten kann. Dieser kann dann die Methode Sortable.compareToSortable verwenden, was wiederum eine Typumwandlung vermeidet.

Solch ein Quicksort ist in der Klasse

- class QuicksortSortable

beschrieben.

Eine letzte Verbesserung soll sein, dass nun direkt auf das Feld Sortable.order zugegriffen werden soll. Dies gibt dann noch einmal eine kleine Zeitverbesserung beim Sortieren.

Der Algorithmus hierzu sieht aus wie in

- class QuicksortSortable2

Zusammenfassung:

Wenn man also möchte, dass ein Sortier-Algorithmus schneller arbeitet, wäre es ein guter Anfang, die Vergleichsmethoden zu optimieren. Hierzu gibt es verschiedene Möglichkeiten:

- Typumwandlungen durch spezifizieren von genaueren Datentypen verhindern
- Vergleichs-Algorithmen derart verändern, dass sie schneller laufen
- Objekte durch Hüllen austauschen, welche schneller verglichen werden können
- Methodenaufrufe verhindern, indem auf die Felder direkt zugegriffen wird
- Arrays teilweise vorsortieren und danach den richtigen Sortier-Algorithmus verwenden

Als Schlussfolgerung kann man sagen, dass durch die Vermeidung von Typumwandlungen durch das Implementieren eines Standard-Algorithmusses sowie einer Vergleichs-Methode für die spezielle Klasse, die Sortierzeit fast verdoppelt werden kann und das durch nur wenig Aufwand.

Erst wenn die Leistung immer noch stark unter der gewünschten liegt, sollte man sich Gedanken über alternative Techniken machen.

Verkettete Listen:

Um nicht-Array-Elemente wie verkettete Listen zu sortieren, ist ein rekursiver Merge- Sort die beste Wahl. Dieser kann schneller sein als ein Quick-Sort in einem Array mit den selben Daten.

3. Ein effizientes Sortier-Framework

Die vielen Sortier-Methoden, die im JDK implementiert wurden, sind für die meisten Situationen völlig passend oder ausreichend und können durch die im vorigen Kapitel beschriebenen Techniken weiter verbessert werden.

Wenn man aber an Projekten arbeitet, die vielseitige und variable Sortier- Möglichkeiten benötigen, ist es sinnvoll, schon frühzeitig im Software-Entwicklungs- Prozess ein Gerüst zum Sortieren aufzubauen.

Dieses sollte es erlauben, Sortier-Algorithmen sowie Methoden zum Vergleichen und Ordnen einfach und schnell austauschen zu können, ohne dabei die eigentliche Applikation zu sehr verändern zu müssen.

Schnittstellen:

Die einfachste Methode, verschiedenste Sortier-Algorithmen zu unterstützen, bieten Interfaces: es muss für jeden Objekt-Typen, der sortiert werden kann, auch ein Sortier-Interface geben. So sollten z.B. Arrays und Collections in jedem Sortier- Framework unterstützt werden, sowie alle anderen Objekte aus der speziellen Anwendung.

Hierzu können die beiden Schnittstellen

- interface ArraySorter
- interface CollectionSorter

verwendet werden, welche lediglich Sortier-Methoden mit unterschiedlichen Signaturen bieten

Die erste Implementierung dieser Schnittstellen

- class ArrayQuickSorter implements ArraySorter

erlaubt es, den Sortier-Algorithmus einfach dadurch zu wechseln, indem ein anderes Sortier-Objekt benutzt wird.

Spezielle Fälle:

Wir sind jedoch erst auf halber Strecke zu einem effizienten Sortier-Framework. Die allgemeine Struktur zum Sortieren steht zwar somit fest, sie bietet aber noch keine Unterstützung für generelle Optimierungen wie z.B. optimierte Vergleichs-Wrapper (wie z.B. mit java.text.CollationKey), welche hier ComparisonKeys genannt werden sollen.

- interface ComparisonKey

Um diese generellen Optimierungen zu unterstützen, benötigt man das Interface Comparator, welches zusätzliche Methoden zum überprüfen des Vorhandenseins der optimierten ComparisonKeys bietet. Da das man der Comparator-

Schnittstelle keine Methoden mehr hinzufügen kann, muss man ein Sub-Interface benutzen.

- interface KeyedComparator extends Comparator

Diese Ergänzung müssen nun zu dem Framework in jedem Sortier-Objekt hinzufügen. Da aber nicht jedes Sortier-Objekt wieder und wieder von Hand geändern werden soll, muss ein besserer Weg zum optimieren gefunden werden.

Eine Optimierung wäre z.B. ein Sortier-Algorithmus, der einen Aufruf jeglicher Methoden-Vergleiche verhindert. Dies wird mittels einer speziellen ComparisonKey- Klasse unterstützt.

- class IntegerComparisonKey implements ComparisonKey

Wird dieser Sortierer neu implementiert, muss nur die Methode, die den eigentlichen Sortier-Algorithmus implementiert, geändert werden.

- class ArrayQuicksorter2 implements ArraySorter

Diese speziellen Fälle bedeuten zwar, dass der selbe Algorithmus mehrmals implementiert werden muss, wobei sich nur die Daten-Typen und die Vergleichs- Methoden ändern.

Dies muss man jedoch in Kauf nehmen, wenn man Leistungs-Optimierungen durchführen will. Zudem befinden sich alle Implementierungen in einer Klasse und wenn diese einmal fertig kompiliert wurde, wird man sie kaum noch ändern müssen.

Zwischenstand:

Das Framework unterstützt nun:

- eine einfache Möglichkeit, den Sortier-Algorithmus zu wechseln
- eine einfache Möglichkeit, die paarweisen Vergleichs-Methoden zu wechseln
- Automatische Unterstützung für ComparisonKeys-Objekte (diese werden idealerweise dann genutzt, wenn die Vergleichs-Methoden Berechnungen für jedes Objekt, das verglichen wird, machen müssen und diese Berechnungen zwischengespeichert werden können)
- Eine optimierte Klasse für Integer-Vergleiche, welche keine Methodenaufrufe beim Sortieren benötigen

Dies sollte nun eine gute Basis zum Bau eines effizienten Sortier-Gerüstes sein. Viele weitere Optimierungen sind nötig, jedoch sollte das Framework diese automatisch verwalten.

Weitere Verbesserungen:

Die letzte Version des Gerüsts (ArrayQuickSorter2) unterstützt die schnellste Sortier-Methode aus dem vorherigen Kapitel, welche ohne Typumwandlungen und mit direktem Zugriff zum Sortier-Feld auskommt.

Leider sind die Kosten für das Erzeugen der IntegerComparisonKey-Objekte für jedes zu sortierende Objekt groß genug, um so den Geschwindigkeitsvorteil, der durch den Verzicht auf die Typumwandlung gewonnen wurde, zu eliminieren.

Diese Kosten können jedoch weiter reduziert werden, indem das

IntegerComparisonKey-Array in ein Object- und int- Paar umgewandelt wird. Folgende Schnittstelle unterstützt das benötigte Abbilden:

- interface RawIntComparator extends KeyedComparator

Für die Sortable-Klasse vom Anfang kann man damit eine Comparator-Klasse implementieren,

- class SortableComparator implements RawIntComparator

welche dann in einem geänderten Sortier-Gerüst benutzt wird:

- class ArrayQuickSorter3 implements ArraySorter

Mit dieser Optimierung ist das Framework jetzt so schnell wie der schnellste Quicksort-Algorithmus aus dem vorherigen Kapitel.

4. Schneller sortieren als O(nlogn)

Wenn es darum geht, abzuschätzen wie lange ein bestimmter Algorithmus zum Ausführen benötigt, möchte man häufig nicht nur wissen, wie lange er für eine bestimmte Menge von Daten braucht, sondern man möchte ebenfalls wissen, wie lange er für verschieden große Datenmengen benötigt. Es geht also darum, wie skalierbar der Algorithmus ist.

Eine Möglichkeit, diese Skalierbarkeit einem bestimmten Algorithmus darzustellen ist, die Skalierungseigenschaften mittels einer numerischen Funktion zu beschreiben. Hierzu wird die O- Notation (gesprochen „groß O“) benutzt.

Für einen Algorithmus, der zum Beispiel die Eigenschaft O(n) besitzt, bedeutet dies, dass der Rechenaufwand linear mit der Menge der zu berechnenden Daten wächst, während ein Algorithmus mit O(n2) für die doppelte Datenmenge viermal soviel Zeit zum berechnen benötigt.

Die O-Notation zeigt also an, wie teuer ein spezieller Algorithmus ist, wenn die zu bearbeitende Datenmenge wächst.

Zusätzliche Informationen helfen:

Analysen von Sortier-Algorithmen haben gezeigt, dass im Schnitt kein genereller Algorithmus schneller sortieren kann als O(nlogn).

Viele Anwendungen benötigen jedoch gar keinen „generellen“ Sortierer. Vielmehr besitzt man häufig noch zusätzliche Informationen über die zu sortierenden Daten, welche bei der Verbesserung der Leistung eines speziellen Algorithmus helfen können.

Hat man beispielsweise 1000 Objekte, die sortiert werden müssen und jedem dieser Objekte kann ein eindeutiger Wert zwischen 1 und 1000 zugewiesen werden, ist die beste Sortiermöglichkeit, die Objekte einfach an die passende Stelle in einem Array einzufügen.

Normalerweise kann man seine zu sortierenden Elemente nicht so einfach einordnen. Aber es gibt noch weitere Möglichkeiten, die man ausnutzen kann, um die Sortier- Eigenschaften der Elemente zu verbessern. So kann ein teilweise vorsortiertes Array beispielsweise schneller sortiert werden, als ein unsortiertes.

Worauf man bei Sortieralgorithmen weiterhin achten sollte:

- den Elementen sollte ein Ordnungswert gegeben werden können, der dann auf einfache Integer-Werte abgebildet werden kann
- die Verteilung von Schlüsselwerten ist regelmäßig, gleichmäßig oder die Werte können zu Gruppen zusammengefasst werden, die dann besser auf Array- Indizes abgebildet werden können

Es ist also auch häufig möglich, die letztendliche Position der Elemente im Array abzuschätzen und somit den Sortieraufwand zu reduzieren.

Flashsort:

Ein Algorithmus, der all diese Vorgehensweisen ausnutzt und implementiert, ist der Flashsort-Algorithmus

- class FlashSort2

von Karl-Friedrich Neubert.

Dieser Algorithmus bietet ein Sortier-Verhalten von O(n) und minimiert nebenbei den zusätzlichen Speicheraufwand, der zum Sortieren benötigt wird.

Flashsort besteht aus drei logischen Blöcken: Klassifizierung, Permutation und direktes Einfügen.

Zuerst werden die einzelnen zu sortierende Elemente klassifiziert und in verschiedene Gruppen eingeteilt. Im Anschluss daran findet eine Vertauschung und Neuordnung der gefundenen Klassen statt.

Nach den ersten beiden Schritten befinden sich die Elemente annähernd in der richtigen Position. Man erhält also nach der Permutation ein teilweise vorsortiertes Array, mit dem dann weitergearbeitet werden kann. Im letzten Schritt wird ein Straight-Insertion-Sort (direktes Einfügen) verwendet, mit dem dann die finale Ordnung erreicht wird.

Auf eine genauere Beschreibung wird an dieser Stelle verzichtet, im Anhang befinden sich jedoch die Schriftstücke von Karl-Friedrich Neubert von der euroFORTH'97 – Konferenz sowie eine Beschreibung des Algorithmus aus der Zeitschrift Dr. Dobb's Journal vom Februar 1998.

5. Performance-Checkliste

Zusammenfassend hier noch einmal eine Checkliste mit allen Möglichkeiten, die Leistung von Sortier-Algorithmen zu steigern.

Viele dieser Vorschläge sollten jedoch nur angewendet werden, wenn auch wirklich ein Flaschenhals identifiziert wurde:

- Typumwandlungen in den Sortier-Methoden verhindern bzw. eliminieren.
- Einen Standard-Sortier-Algorithmus wie z.B. Quicksort in der zu sortierenden Klasse direkt reimplementieren.
- Beschleunigung der Vergleichs-Methoden.
- Auf Felder direkt zugreifen, anstatt Methodenaufrufe zu verwenden.
- Verkettete Listen mit einem Merge-Sort sortieren.
- ComparisonKeys verwenden, um Objekte zu ersetzen, bei denen die Vergleichsmethode eine Berechnung für jedes zu vergleichende Objekt anstellen muss, welche aber zwischengespeichert werden kann.
- Arrays mit schnelleren Teil-Sortieren vorsortieren; anschließend nachsortieren mit der richtigen Vergleichs-Methode.
- Unterstützung von allgemeinen Optimierungen durch ein Sortier-Gerüst. Dazu zählen:
- ComparisonKey-Objekte, die Berechnungen zwischenspeichern, welche sonst wiederholt ausgeführt werden müssten.
- ComparisonKey-Objekte, die die zu ordnenden Werte in öffentlichen Feldern aufbewahren, auf welche direkt zugegriffen werden kann.
- Verbesserte Objekterzeugung durch Abbilden von ComparisonKey- Arrays auf mehrere Arrays.
- Spezialisierte Sortier-Algorithmen benutzen, die eine schnellere Sortierzeit oder bessere Skalierverhalten besitzen.
- Spezialisierte Sortier-Algorithmen benutzen, wenn die Reihenfolge der zu sortierenden Elemente direkt auf Integer-Schlüsselwerte abgebildet werden kann.

6. Performance-Test

Die in den Abschnitten „Unnötigen Sortier-Aufwand“ und „Schneller sortieren als O(nlogn)“ verwendeten Quicksort- und Flashsort-Algorithmen wurden im folgenden kurz getestet und mit den Testergebnissen von Jack Shirazi verglichen.

Getestet wurde mit dem JBuilder 4 und dem JDK 1.3.0. Zum Zeitmessen wurde die Klasse CStopWatch aus der Vorlesung JavaTuning verwendet.

Zur Vorgehensweise:

Es wurde ein Integer-Array der Länge von 10.000 bis 900.000 angelegt und mit Zufallszahlen, erzeugt durch die Methode Random.nextInt(), gefüllt.

Im Anschluss wurde dieses Array dann für jeden der Algorithmen geklont( damit

immer die selben int-Werte benutzt werden) und dem Sortier-Algorithmus übergeben und die Zeit gestoppt.

Das ganze wurde für jede Array-Größe drei mal durchgeführt und ein Mittelwert für die Darstellung berechnet.

Zum Vergleich wurden beim Testen auch die Zeiten für die Benutzung von Arrays.sort() hinzugefügt. Diese Methode benutzt einen Merge-Sortier- Algorithmus, welcher auf einem teilweise vorsortierten Array eine bessere Leistung zeigt. Dieser Algorithmus wurde für das JDK ausgewählt, weil er im Gegensatz zum Quicksort-Algorithmus, welcher eine bessere Durchschnittsleistung besitzt, eine hohe Sortier-Stabilität besitzt. Zudem hat Quicksort eine sehr schlechte Leistung für den Worst-Case-Fall.

Ergebnis:

Die Ergebnisse werden im folgenden Diagramm dargestellt:

Abbildung in dieser Leseprobe nicht enthalten

Wie zu erwarten war, bietet Flashwort eine deutlich bessere Performance, als alle anderen benutzten Algorithmen und wird nur noch von einem Quicksort übertroffen, der einen direkten Vergleich von Integer-Werten vornimmt.

Besser als von Shirazi bestimmt, verhält sich java.util.Arrays.sort(). Warum sich die Rechenzeit hierbei jedoch ab einer Array-Größe von 800.000 wieder verringert, konnte nicht erklärt werden.

[...]