11.9 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. Allerdings sind viele Algorithmen nur auf List-Objekten definiert; die Implementierung von Collection reicht oft nicht aus. Das ist nicht erstaunlich, denn wenn ein Container keine Ordnung definiert, kann er nicht sortiert werden. Auch die binäre Suche erfordert Container mit einer impliziten Reihenfolge der Elemente. Nur Min- und Max-Methoden arbeiten auf allgemeinen Collection-Objekten. Nutzt die Collections-Klasse keine List-Objekte, arbeitet sie jedoch nur mit Collection-Objekten und nicht mit Iteratoren.

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.

Listing 11.7   Shuffle.java

import java.util.*;

public class Shuffle
{
  public static void main( String args[] )
  {
    List<Integer> v = new ArrayList<Integer>();
    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.9.1 Datenmanipulation: Umdrehen, Füllen, Kopieren 

Collections.reverse() dreht die Reihenfolge der Elemente in einer Liste um. Die Laufzeit ist linear zur Anzahl der Elemente. 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. Das heißt aber, 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.

Collections.copy(List quelle, List ziel) 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. Hat das Ziel weitere Elemente, ist dies egal, da diese nicht angetastet werden.

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

static <T> void fill( List<? super T> list, T obj ) Überschreibt jedes vorhandene Element der Liste mit dem Element o.

static <T> void copy( List<? super T> dest, List<? extends T> 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.9.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( T o1, T o2 ) Vergleicht zwei Argumente auf ihre Ordnung.

boolean equals( Object obj ) Testet, ob Comparator-Objekte gleich sind. Das testet keine Gleichheit von Objekten!

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 Argument 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 <T> void sort( T[] a, Comparator<? super T> c ) Vergleicht die Objekte mit einem externen Comparator. Falls die Objekte auch noch Comparable implementieren, wird diese Sortierordnung nicht genutzt.

11.9.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 <T extends Object & Comparable<? super T>> T min(Collection<? extends T> coll)

static <T> T min(Collection<? extends T> coll, Comparator<? super T> comp)

static <T extends Object & Comparable<? super T>> T max(Collection<? extends T> coll)

static <T> T max(Collection<? extends T> coll, Comparator<? super T> 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. Es sei auch bemerkt, dass dies mit die komlexesten Beispiele für Generics sind.

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 <T extends Object & Comparable<? super T>>
              T min( Collection<? extends T> coll )
{
    Iterator<? extends T> i = coll.iterator();
    T candidate = i.next();

    while( i.hasNext() )
    {
        T next = 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.9.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.8   CollectionsSortDemo.java

import java.util.*;

public class CollectionsSortDemo
{
  public static void main( String args[] )
  {
    List<String> 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 Funktion 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.9   CollectionsReverseSortDemo.java

import java.util.*;

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

    Comparator<String> comparator = (Comparator<String>)
                                   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 <T extends Comparable<? super T>> void sort(List<T> list) Sortiert die Elemente der Liste gemäß ihrer natürlichen Ordnung, die ihnen die Implementierung über Comparable gibt.

static <T> void sort(List<T> list, Comparator<? super T> 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 <T extends Comparable<? super T>> void sort( List<T> list )
{
  Object[] a = list.toArray();
  Arrays.sort( a );
  ListIterator<T> i = list.listIterator();
  for ( int j = 0; j < a.length; j++ ) {
    i.next();
    i.set( (T)a[j] );
  }
}

11.9.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<String> l = new ArrayList<String>( Collections.nCopies(10, "") );
l.addAll( Collections.nCopies(2, ".") );
System.out.println( l );   // [, , , , , , , , , , ., .]

11.9.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.9.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 <T extends Object & Comparable<? super T>> int binarySearch(List<? extends T> list, T 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 <T> int binarySearch(List<? extends T> list, T key, Comparator<? super T> 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.

Häufigkeit eines Elementes

Collections.frequency(Collection,Object) gibt seit Java 5 die Anzahl der Elemente zurück, die zu einem Such-Objekt equals()-gleich sind.

int i = Collections.frequency( Arrays.asList("Hallo :-) 
Suppi :-)".split("\\s")), ":-)" );
System.out.println( i );    // 2

static int frequency( Collection<?> c, Object o ) Liefert Anzahl Elemente, die mit o gleich sind, genauer gesagt, für die gilt: o == null ? e == null : o.equals(e).

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