11.8 Algorithmen in Collections

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 Standardalgorithmen 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 für Container sind zum Beispiel Mischen und Sortieren 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.

Alle Funktionen sind statisch, so dass Collections als Utility-Klasse wie Math gewertet werden kann. Ein Exemplar von Collections lässt sich nicht anlegen - der Konstruktor ist privat.

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.10 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.8.1 Datenmanipulation: Umdrehen, Füllen, Kopieren

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);
  }
}

Wenn wir nun die Liste mit genau einer Referenz füllen, heißt dies auch, dass es immer das gleiche Objekt ist, das an allen Positionen sitzt. Es ist die Frage, ob das immer so sinnvoll und nützlich ist.

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.8.2 Vergleichen von Objekten mit Comparator und Comparable

Sollen beliebige Objekte verglichen werden, muss es eine Ordnung dieser Objekte geben. Wie sollte das System sonst selbstständig entscheiden können, ob ein Personen-Objekt kleiner als ein anderes Personen-Objekt ist. Weil die eine Person 1,50 Meter groß ist, die andere aber 1,80 Meter, oder weil die eine Person eine Million Euro auf dem Konto hat und die andere nur fünf Euro?

Vergleiche zwischen den Elementen einer Datenstruktur werden von speziellen Hilfsobjekten durchgeführt, den Comparatoren.

Die Schnittstelle Comparator

Eine Klasse für konkrete Comparator-Objekte implementiert eine Schnittstelle, die zwei Methoden vorgibt.

int compare( Object o1, Object o2 ) Vergleicht zwei Argumente auf ihre Ordnung.

boolean equals( Object obj ) Testet, ob zwei Objekte aus Sicht des Comparator-Objekts gleich sind.

Hier klicken, um das Bild zu Vergrößern

Der Unterschied zwischen Comparable und Comparator

Es mag überraschen, dass es in Java 2 zwei unterschiedliche Schnittstellen zur Sortierunterstützung gibt: einmal java.lang.Comparable und einmal java.util.Comparator.

Die Schnittstelle Comparable schreibt die Methode int compareTo( Object o) vor.

Comparator definiert die Methode int compare( Object o1, Object o2 ).

Der Unterschied liegt also in der Signatur einmal darin, dass Comparable eine Schnittstelle ist, die von dem Objekt selbst definiert wird, so dass es sich mit anderen vergleichen kann. Der Comparator dagegen lässt sich als Extraklasse nutzen, falls die Klassen nicht Comparable implementieren. So erwartet auch der Comparator zwei Objekte o1 und o2 und nicht nur eins, da er ja nicht sich selbst mit einem anderen Objekt vergleicht. Ein Comparator ist somit flexibler und kann jederzeit beliebige Objekte vergleichen.

Der Einsatz der beiden Schnittstellen lässt sich auch in den Java-Bibliotheken ablesen. So bietet etwa die Klasse java.util.Arrays statische Methoden zum binären Suchen und zum Sortieren eines Arrays an, einmal mit Comparator und einmal mit Comparable. Doch da im Fall Comparable die Objekte selbst die Schnittstelle implementieren, muss das Comparable-Objekt nicht als Parameter angegeben werden.

class java.util.Arrays

static void sort( Object a[] ) Sortiert die Elemente. Zum Vergleichen wird vorausgesetzt, dass sie die Klasse Comparable implementieren. Falls sie dies nicht tun, wird eine Ausnahme ausgelöst.

static sort( Object a[], Comparator c ) Vergleicht die Objekte mit einem externen Comparator. Falls die Objekte auch noch Comparable implementieren, wird diese Sortierordnung nicht genutzt.

11.8.3 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 Methode 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.

Die Schnittstelle Comparable

Bisher kennen wir nur min() und max() der Utility-Klasse Math 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.8.4 Sortieren

Die Collections-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 von demselben 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 (Hansi<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()-Aufrufe. 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.11 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 );
  }
}

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 jedoch Merge-Sort 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.12 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.8.5 nCopies()

Die statische Funktion nCopies(int number, Object element) erzeugt eine Liste mit der gewünschten Anzahl Elementen aus einem Objekt. Die Liste besteht aber nicht aus einer Anzahl Kopien des Elements (mit clone()), sondern aus einer Liste, die ein Element immer wiederholt. Daher sind auch nur Leseoperationen wie get() oder contains() erlaubt, jedoch keine Veränderungen. Daher ist der Einsatzbereich der Liste beschränkt; der der Funktion dadurch aber nicht. Denn die Elemente der Liste können als Ausgang für eine modifizierbare Datenstruktur gelten, der sich eine Liste übergeben lässt. Das gilt zum Beispiel für eine ArrayList, die im Konstruktor eine andere Liste akzeptiert, aus der sie die Werte nimmt.

List l = new ArrayList( Collections.nCopies(100, "") );
l.addAll( Collections.nCopies(10, ".") );

11.8.6 Singletons

Singletons sind Objekte, die genau ein Exemplar realisieren. In der Collections-Klasse gibt dazu drei Funktionen. singleton(Object o) liefert eine Menge mit genau einem Element. Auf den ersten Blick erscheint die Funktion ziemlich unnütz, doch sie löst sehr elegant ein Problem, für das die Collection-Klassen keine Lösung zeigen: Löschen aller Vorkommen eines Elements. Zwar gibt es die Collection-Funktion remove(Object), doch das löscht nur das erste Vorkommen. Um alle Vorkommen zu löschen ist entweder eine Schleife zu schreiben oder singleton() zu nutzen. Uns hilft beim Löschen aller Elemente die Funktion removeAll(Collection). Doch sie erwartet ein Collection. Aber diese bekommen wir ja gerade durch singleton()!

void removeAll( Collection c, Object o )
{
  c.removeAll( Collections.singleton(o) );
}

Neben der einfachen Methode singleton(Object o) existiert noch singletonList(Object o), die eine Liste liefert, und singletonMap(Object key, Object value) für eine Map.

11.8.7 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 (auch binäre Suche, 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 Listen-Element, 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 gefundenen 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.