11.12 Algorithmen 

Um Probleme in der Informatik zu lösen, ist die Wahl einer geeigneten Datenstruktur nur der erste Schritt. Im zweiten Schritt müssen Algorithmen implementiert werden. Da viele Algorithmen immer wiederkehrende (Teil-)Probleme lösen, hilft uns auch hier die Java-Bibliothek mit einigen Standard-Algorithmen weiter. Dazu zählen etwa Funktionen zum Sortieren und Suchen in Containern und das Füllen von Containern. Um die Methoden möglichst flexibel einzusetzen, definierten die Bibliotheksentwickler die Klasse Collections – die wir nicht mit dem Interface Collection verwechseln dürfen. Collections bietet die notwendigen Algorithmen als statische Funktionen an, die als Parameter ein Collection-Objekt erwarten. Allerdings sind viele Algorithmen nur auf List-Objekten definiert. Das ist erstaunlich, denn zum Beispiel Mischen und Sortieren sind für Container ohne definierte Ordnung oder mit einer über externe Schlüssel definierten Ordnung nicht sinnvoll. Auch die binäre Suche erfordert Container mit einer impliziten Reihenfolge der Elemente. Bei Set und Map vollziehen sich die Suchoperationen eher hinter den Kulissen und die verwendete Suchtechnik wird verborgen. Nur Min- und Max-Methoden arbeiten auf allgemeinen Collection-Objekten. Nutzt die Collections-Klasse keine List-Objekte, arbeitet sie mit Collection-Objekten, um allgemein zu bleiben. Iteratoren erscheinen nicht als Übergabeparameter.

Betrachten wir die Implementierung der Methode shuffle(), die die Elemente wahllos durcheinander würfelt. shuffle() ist somit genau das Gegenteil von sort().

public static void shuffle(List list, Random rnd) {
  for (int i=list.size(); i>1; i--)
    swap(list, i-1, rnd.nextInt(i));
}

Da shuffle() allgemein auf List-Objekten arbeitet, können wir hier LinkedList-, Vector- und ArrayList-Objekte einsetzen.

Listing 11.14   VectorShuffle.java

import java.util.*;

public class VectorShuffle
{
  public static void main( String args[] )
  {
    List v = new Vector();

    for ( int i = 0; i < 10; i++ )
      v.add( new Integer(i) );

    Collections.shuffle( v );

    System.out.println( v );
  }
}

Die shuffle()-Methode existiert in zwei Ausführungen. In der oben verwendeten und in einer erweiterten Variante, die als zweiten Parameter ein Random-Objekt erwartet.

static void shuffle( List list ) Würfelt die Elemente der Liste durcheinander. Dafür wird ein Standard-Generator für Zufallszahlen verwendet.

static void shuffle( List list, Random rnd ) Würfelt die Elemente der Liste durcheinander und benutzt dafür den Random-Generator rnd.

11.12.1 Datenmanipulation 

Mit drei Collections-Methoden werden Daten einer Liste verändert. Die Implementierungen sind hier mit aufgeführt, da sie in hervorragender Weise zeigen, wie sich mit den Iteratoren arbeiten lässt.

Daten umdrehen

Die erste Methode ist reverse(). Sie dreht die Reihenfolge der Elemente in einer Liste um. Die Laufzeit ist linear zur Anzahl der Elemente. Die Implementierung ist schön, da sie zwei Iteratoren benutzt, die gegeneinander laufen.

public static void reverse(List l) {
  ListIterator fwd = l.listIterator(),
               rev = l.listIterator(l.size());
  for (int i=0, n=l.size()/2; i<n; i++) {
    Object tmp = fwd.next();
    fwd.set(rev.previous());
    rev.set(tmp);
  }
}

Listen füllen

Mit der fill()-Methode lässt sich eine Liste in linearer Zeit mit mehreren identischen Elementen belegen. Nützlich ist dies, wenn eine Liste mit lauter identischen Elementen initialisiert werden muss. fill() arbeitet wiederum mit einem ListIterator.

public static void fill(List list, Object o) {
  for (ListIterator i = list.listIterator(); i.hasNext(); ) {
    i.next();
    i.set(o);
  }
}

Daten zwischen Listen kopieren

Die letzte verändernde Methode ist copy(List quelle, List ziel). Sie kopiert alle Elemente von quelle in die Liste ziel und überschreibt dabei Elemente, die eventuell schon an den entsprechenden Positionen der Zielliste liegen. Die Zielliste muss mindestens so lang sein wie die Quellliste, andernfalls wird eine IndexOutOfBoundsException ausgeworfen, wie der nachfolgende Quelltext zeigt. Hat das Ziel weitere Elemente, ist dies egal, da diese nicht angetastet werden.

public static void copy( List dest, List src ) {
  try {
    for (ListIterator di=dest.listIterator(),
         si=src.listIterator();
        si.hasNext(); ) {
      di.next();
      di.set(si.next());
    }
  } catch(NoSuchElementException e) { // von di.next()
    throw new
     IndexOutOfBoundsException("Source does not fit in dest.");
  }
}

static void reverse( List l ) Kehrt die Reihenfolge der Elemente in der Liste um.

static void fill( List list, Object o ) Überschreibt jedes vorhandene Element der Liste mit dem Element o.

static void copy( List dest, List src ) Kopiert alle Elemente von dest nach src und überschreibt dabei die ersten Elemente von src. Ist src zu klein, gibt es eine IndexOutOfBoundsException.

11.12.2 Größten und kleinsten Wert einer Collection finden 

Die Methoden min() und max() suchen das kleinste und größte Element einer Collection. Die Laufzeit ist linear zur Größe der Collection. Die Methoden machen keine Unterscheidung, ob die Elemente der Datenstruktur schon sortiert sind oder nicht.

static Object min( Collection coll )

static Object max( Collection coll )

static Object min( Collection coll, Comparator comp )

static Object max( Collection coll, Comparator comp )

Wir sehen, dass es eine überladene Version der jeweiligen Methoden gibt, da für beliebige Objekte eventuell ein Comparator-Objekt erfoderlich ist, das den Vergleich vornimmt. Als aufmerksamer Leser überlegen Sie nun bestimmt, wie denn min() auf einem Collection-Objekt mit beliebigen Elementen arbeitet.

Bisher kennen wir nur min() und max() auf den numerischen Datentypen. Wenn wir also ein String-Objekt in eine Liste packen oder ein Double-Objekt in eine Menge, wie werden diese dann richtig sortiert? Die Antwort liefert die Comparable-Schnittstelle, die einzig die Methode compareTo(Object o) verlangt. Interessant ist nun, dass Byte, Character, Double, File, Float, Long, ObjectStreamField, Short, String, Integer, BigInteger, BigDecimal, Date und CollationKey diese Schnittstelle implementieren. Das sind also unsere Kandidaten für Klassen, deren Exemplare wir vergleichen können.

Werfen wir einen Blick auf min(), und unsere Zweifel sind aus der Welt geräumt.

public static Object min(Collection coll) {
  Iterator i = coll.iterator();
  Comparable candidate = (Comparable)(i.next());
  while (i.hasNext()) {
    Comparable next = (Comparable)(i.next());
     if (next.compareTo(candidate) < 0)
      candidate = next;
  }
  return candidate;
}

Jedes Element, welches wir über den Iterator holen, casten wir in ein Comparable-Objekt. Dies muss für alle Elemente der übergebenen Datenstruktur gelingen, damit wir das Minimum bestimmen können. Versuchen wir zu schummeln, und die Elemente lassen sich nicht alle vergleichen, dann gibt es eine ClassCastException. Das passiert etwa, wenn zwar alle Elemente Comparable sind, sich aber nicht alle untereinander paarweise vergleichen lassen, wie zum Beispiel Date und File. Beide Klassen implementieren Comparable, aber new Date().compareTo(new File("/tmp")) ergibt eine ClassCastException.

11.12.3 Sortieren 

Die Collection-Klasse bietet zwei sort()-Methoden, die die Elemente einer Liste stabil sortieren. Stabile Sortieralgorithmen lassen die Reihenfolge von gleichen Elementen unverändert. Dies spielt dann eine Rolle, wenn nicht alle Attribute der Elemente in den Vergleich eingehen. Wenn wir etwa die Folge (27,1), (3,2), (56,1), (4,2) (3,1) nach der zweiten Komponente der Zahlenpaare sortieren und anschließend nach der ersten Komponente, dann erwarten wir, dass (3,1) vor (3,2) liegt und der Algorithmus die Reihenfolge der beiden Zahlenpaare nicht wieder ändert. Diese Eigenschaft ist nur dann garantiert, wenn die zweite Sortierung mit einem stabilen Sortieralgorithmus erfolgt. Etwas praktischer lässt sich diese Eigenschaft an einem E-Mail-Programm zeigen. Sortieren wir unsere Nachrichten zuerst nach dem Datum und anschließend nach dem Absender, so sollen die Nachrichten vom selben Absender immer noch nach dem Datum sortiert bleiben.

Die Methode sort() sortiert die Elemente in ihrer natürlichen Ordnung, also Zahlen nach der Größe (19<34) und Zeichenketten alphanumerisch (Michael<Raphael<Ulli). Eine zweite überladene Form von sort() arbeitet mit einem speziellen Comparator-Objekt, welches jeweils zwei Objekte mit seiner compare(Object, Object)-Methode vergleicht. Die Sortierfunktion arbeitet nur mit List-Objekten. Bei den anderen Datenstrukturen würde das ohnehin wenig Sinn machen, diese sind entweder unsortiert oder haben eine extern bestimmte Ordnung, wie oben schon angemerkt. Eine analoge Sortierfunktion für die Elemente von Arrays, nämlich sort(), gibt es aber noch in der Klasse Array.

Das folgende Programm sortiert eine Reihe von Zeichenketten aufsteigend. Es nutzt die Methode Arrays.asList(), um aus einem String-Feld eine Liste zu konstruieren. So sparen wir uns wiederholte add()-Operationen. Leider gibt es keinen Konstruktor für ArrayList, der ein Array von Strings direkt verarbeitet. Eine mit einem Konstruktor vergleichbare Lösung ist Arrays.asList(), die genau die Aufgabe effizient löst. Im allgemeinen Fall wird new ArrayList(Arrays.asList(...)) verwendet.

Listing 11.15   CollectionsSortDemo.java

import java.util.*;

public class CollectionsSortDemo
{
  public static void main( String args[] )
  {
    List l = Arrays.asList( new String[]{
      "Noah",   "Abraham", "Isaak",  "Ismael", "Moses",   
      "Jesus", "Muhammed",
      "Saskia", "Regina",  "Angela", "Astrid", "Manuela", "Silke",
      "Linda",  "Daniela", "Silvia", "Samah",  "Radhia",  "Mejda" } );
    Collections.sort( l );

    System.out.println( l );
  }
}

asList() und die »echten« Listen

Arrays von Objektreferenzen und dynamische Datenstrukturen passen nicht so richtig zusammen. Die Java-Bibliothek bietet auch nicht allzu viel an, um Felder in dynamische Datenstrukturen umzuwandeln. Eine Ausnahme bildet die Hilfsklasse Arrays, die eine Methode asList() anbietet. Bei den uns bekannten Unterklassen ArrayList und LinkedList stellt sich die Frage, ob asList() damit etwas zu tun hat. Die Antwort ist nein. Arrays implementiert eine eigene interne Listen-Klasse, die mit ArrayList oder LinkedList von der Implementierung her nichts gemeinsam hat, bis auf die Tatsache, dass sie die Schnittstelle List implementiert, obwohl die interne Klasse auch ArrayList heißt. Die Unterscheidung ist wichtig, da ArrayList aus Arrays eine Mini-Implementierung des Vorbilds ist. Daher lässt sich mit ihr auch nicht alles machen, was spätestens dann klar wird, wenn über einen Iterator Elemente in der Liste gelöscht werden sollen. Dann folgt eine UnsupportedOperationException(), die aus AbstractList kommt. Die kleine ArrayList-Implementierung in Arrays erweitert nämlich AbstractList und implementiert nur das Notwendigste. Damit wir jetzt dennoch Elemente löschen können, müssen wir die einfache Liste in eine spezielle LinkedList oder ArrayList umbauen. Das sieht dann wie folgt aus:

List l = new ArrayList( Arrays.asList( new String[]{"Purzelchen", "Hässchen"} ) );

Iterator i = l.iterator();
i.next();
i.remove();

Merge-Sort steht dahinter

Der Methode sort() in der Klasse Collections liegt als Algorithmus ein optimierter Merge-Sort zugrunde. Er arbeitet in der Regel sehr schnell; die Laufzeit beträgt n*log(n), wenn n Elemente zu sortieren sind. Obwohl Quick-Sort bei einigen Sortierfolgen schneller ist, hat dieser den großen Nachteil, dass er nicht stabil arbeitet und keine garantierte Laufzeit von n*log(n) besitzt.¹  Auf fast sortierten Datenfolgen arbeitet Merge-Sort jedoch wesentlich schneller.

Daten in umgekehrter Reihenfolge sortieren

Da es keine spezielle Methode reverseSort() gibt, verwendet man ein spezielles Comparator-Objekt, um Daten entgegensetzt zu ihrer natürlichen Reihenfolge zu sortieren. Mit der statischen Methode reverseOrder() der Klasse Collections können wir ein geeignetes Comparator-Exemplar anfordern. Im folgenden Programm fügen wir einige Zeichenketten in eine Liste ein, die wir anschließend absteigend sortieren lassen.

Listing 11.16   CollectionsReverseSortDemo.java

import java.util.*;

public class CollectionsReverseSortDemo
{
  public static void main( String args[] )
  {
    List l = Arrays.asList( new String[]{
      "Adam", "Eva", "Set", "Enosch", "Kenan", "Mahalalel", "Jered" } );

    Comparator comparator = Collections.reverseOrder();
  
    Collections.sort( l, comparator );

    System.out.println( l ); // [Set, Mahalalel, Kenan, Jered, Eva, Enosch, Adam]
  }
}

Eine andere Möglichkeit für umgekehrt sortierte Listen besteht darin, erst die Liste mit sort() zu sortieren und anschließend mit reverse() umzudrehen. Die Lösung mit einem reverseOrder()-Comparator ist jedoch stabil. Die Lösung mit reverse() kehrt die Reihenfolge der gleichen Elemente ebenfalls um.

static void sort( List list ) Sortiert die Elemente der Liste gemäß ihrer natürlichen Ordnung.

static void sort( List list, Comparator c ) Sortiert die Elemente der Liste gemäß der Ordnung, die durch den Comparator c festgelegt wird.

Die sort()-Methode arbeitet mit der toArray()-Funktion der Klasse List. Damit werden die Elemente der Liste in einem Array abgelegt. Anschließend wird die sort()-Methode der mächtigen Arrays-Klasse genutzt und am Ende der sortierte Array-Inhalt mit einem ListIterator wieder in die Liste übertragen.

public static void sort(List list) {
  Object a[] = list.toArray();
  Arrays.sort(a);
  ListIterator i = list.listIterator();
  for (int j=0; j<a.length; j++) {
    i.next();
    i.set(a[j]);
  }
}

11.12.4 Elemente in der Collection suchen 

Die Collection-Klassen enthalten eine Methode, mit der sich Elemente suchen lassen. Diese Methode heißt contains(Object) und gibt entweder true oder false zurück. Wenn allerdings eine Liste sortiert ist, lässt sich eine Suche besonders schnell durchführen. Diesem Verfahren, der Halbierungssuche (engl.: binary search), liegt eine einfache Idee zugrunde. Wir beginnen die Suche nach einem Objekt in der Mitte der Liste. Ist das gesuchte Objekt kleiner als das mittlere Listenelement, dann muss es sich links von der Mitte befinden, andernfalls rechts. Die Liste wird also in zwei gleich große Abschnitte unterteilt, von denen nur einer weiter durchsucht werden muss. Diesen Vorgang wiederholen wir so lange, bis das Element gefunden wurde. Dadurch ist die Suche sehr schnell und benötigt höchstens log(n) Listenhalbierungen, bei einer Liste mit n Elementen. Es kann aber passieren, dass das gesuchte Element nicht in der Liste vorkommt. Dieser Fall wird erkannt, wenn durch das wiederholte Halbieren der Liste ein Listenabschnitt mit nur einem Element entstanden ist. Stimmt dieses eine Element nicht mit dem gesuchten Objekt überein, ist das Ergebnis der Suche ein »Nicht gefunden«. Die Suche nach einem nicht vorhandenen Element ist geringfügig aufwändiger als eine erfolgreiche Suche, benötigt aber ebenfalls nur logarithmisch viele Halbierungsschritte. Enthält die Liste mehrere gleiche Elemente, dann ist nicht gesichert, welches davon bei der Suche gefunden wird. Besteht etwa die Liste aus zehn Zahlen mit dem Wert 22, dann liefert der Algorithmus das fünfte Element.

Von binarySearch() gibt es zwei Varianten. Die erste Methode nimmt an, dass die Werte in ihrer natürlichen Form sortiert sind. Die zweite arbeitet wieder mit einem Comparator-Objekt zusammen. Beide Methoden liefern die Position des gefunden Objekts innerhalb der Liste als Ergebnis. Wurde kein passendes Element gefunden, ist das Ergebnis eine negative Zahl und beschreibt recht trickreich die Stelle, an der der Algorithmus den letzten Vergleich durchgeführt hat. Der Rückgabewert ist dann »– Einfügepunkt – 1« und der Einfügepunkt ist die Position in der Liste, an die der Wert gemäß Sortierung eingesetzt werden kann. Wir können folgende Programmzeilen verwenden, um einen nicht gefundenen Wert gleich passend einzufügen:

int pos = Collections.binarySearch( l, key );
if ( pos < 0 )
  l.add( -pos – 1, key);

Ist die Liste nicht sortiert, kann die Halbierungssuche nicht richtig funktionieren, da sie möglicherweise in die falsche Richtung läuft, und das Element sich in der anderen Hälfte der unterteilten Liste befindet. Eine nicht sortierte Liste kann aber mit sort() sortiert werden. Es ist aber immer noch schneller, in einer unsortierten Liste zu suchen, – Laufzeit O(n), als erst die Liste zu sortieren, – Laufzeit O(n log(n)), und dann darin mit Halbierungssuche zu suchen, – Laufzeit O(log(n)). Wenn ausreichend viele Suchvorgänge nacheinander durchzuführen sind, lohnt sich das vorherige Sortieren der Liste natürlich.

static int binarySearch( List list, Object key ) Sucht ein Element in der Liste. Gibt die Position zurück oder einen Wert kleiner 0, falls kein passendes Element in der Liste ist.

static int binarySearch( List list, Object key, Comparator c ) Sucht ein Element mit Hilfe des Comparator-Objekts in der Liste. Gibt die Position oder einen Wert kleiner 0 zurück, falls kein passendes Element in der Liste ist.

¹   Die STL-Bibliothek bei C++ unterstützt stabile und nicht stabile Sortieralgorithmen. Davon können wir in Java nur träumen.