13.6 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 Methoden zum Sortieren und Suchen in Containern und zum Füllen von Containern. Einige Algorithmen sind Teil der jeweiligen Datenstruktur selbst, andere wiederum befinden sich in der Extraklasse java.util.Collections. Diese Utility-Klasse, die wir nicht mit dem Interface Collection verwechseln dürfen, bietet Methoden, um zum Beispiel

• Listen zu sortieren, zu mischen, umzudrehen, zu kopieren und zu füllen,
• Elemente nach der Halbierungssuche zu finden,
• die Anzahl equals()-gleicher Elemente zu ermitteln,
• Extremwerte zu bestimmen,
• Elemente in einer Liste zu ersetzen und
• Wrapper um existierende Datenstrukturen zu legen.

Abbildung 13.6: UML-Diagramm von Collection

Viele Algorithmen sind nur auf List-Objekten definiert, denn der einfache Typ 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 doch nur mit Collection-Objekten und nicht mit Iteratoren.

Alle Methoden sind statisch, sodass Collections eine Utility-Klasse wie Math ist. Ein Exemplar von Collections lässt sich nicht anlegen – der Konstruktor ist privat.

List<String> list = new ArrayList<String>();
Collections.addAll( list, "Doha,Berlin,Wesel".split( "," ) );
Collections.sort( list );
System.out.println( Collections.binarySearch( list, "Wesel" ) >= 0 ); // true

13.6.1 Die Bedeutung von Ordnung mit Comparator und Comparable

Die Ordnung der Elemente spielt bei Daten eine große Rolle. Um Elemente in einem TreeSet sortiert zu halten oder in einer Liste das größte Element zu finden, muss die Ordnung definiert sein.

Um Ordnung herzustellen, unterscheidet Java zwei Wege:

• Elemente können eine natürliche Ordnung haben. Dann implementieren Klassen die Schnittstelle Comparable. Beispiele sind String, Date und Integer.
• Ein externes Vergleichsobjekt, das die Schnittstelle Comparator implementiert, stellt fest, wie die Ordnung für zwei Elemente ist.

Um Such- oder Sortieroperationen möglichst unabhängig von Klassen zu machen, die eine natürliche Ordnung besitzen oder die eine Ordnung über einen externen Comparator definiert bekommen, haben Utility-Klassen wie java.util.Arrays oder java.util.Collections oft zwei Arten von Methoden: einmal mit einem zusätzlichen Comparator-Parameter und einmal ohne. Wird kein Comparator angegeben, so müssen die Objekte vom Typ Comparable sein.

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.
• static int binarySearch(Object[] a, Object key)
  Sucht binär nach key. Die Objekte im Feld müssen Comparable implementieren.
• static <T> int binarySearch(T[] a, T key, Comparator<? super T> c)
  Sucht im sortierten Feld. Der Comparator bestimmt das Sortierkriterium.

class java.util.Collections

• static <T extends Comparable<? super T>> void sort(List<T> list)
• static <T> void sort(List<T> list, Comparator<? super T> c)
• static <T> int binarySearch(List<? extends Comparable<? super T>> list, T key)
• static <T> int binarySearch(List<? extends T> list, T key,
  Comparator<? super T> c)

Die Datenstrukturen, die eine Sortierung verlangen, wie TreeSet oder TreeMap, nehmen entweder einen Comparator entgegen oder erwarten von den Elementen eine Implementierung von Comparable.

13.6.2 Sortieren

Mit zwei statischen sort()-Methoden bietet die Utility-Klasse Collections die Möglichkeit, die Elemente einer Liste stabil zu sortieren.

class java.util.Collections

• 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. Eine mögliche natürliche Ordnung spielt keine Rolle.

Die Sortiermethode arbeitet nur mit List-Objekten. Bei den anderen Datenstrukturen wäre das ohnehin kaum sinnvoll, weil diese entweder unsortiert sind oder extern eine bestimmte Ordnung aufweisen, wie oben schon angemerkt wurde. Eine analoge Sortiermethode sort() für die Elemente von Arrays bietet die Klasse Arrays.

Beispielprogramm zum Sortieren

Das folgende Programm sortiert eine Reihe von Zeichenketten aufsteigend.

Listing 13.5: com/tutego/insel/util/CollectionsSortDemo.java, main()

List<String> list = Arrays.asList(
    "Saskia", "Regina", "Angela", "Astrid", "Manuela", "Silke",
    "Linda",  "Daniela", "Silvia", "Samah",  "Radhia",  "Mejda", "Tanja"
);
Collections.sort( list );
System.out.println( list );

Die statische Methode Arrays.asList() baut aus einem String-Feld (getarnt als Vararg) eine Liste auf. Die Liste im Ergebnis ist veränderbar.

Strings sortieren, auch unabhängig von der Groß- und Kleinschreibung

Die Klasse String realisiert über die Implementierung von Comparable eine natürliche Sortierung. Alle String-Objekte, die in einem Feld sind, können problemlos über Array.sort() sortiert werden, und alle Strings in Collection-Sammlungen können über Collections.sort() sortiert werden.

Um unabhängig von der Groß- und Kleinschreibung zu sortieren, bietet die Klasse String eine praktische Konstante: String.CASE_INSENSITIVE_ORDER. Das ist ein Comparator<String>, der gut als Argument für sort() passt. Im Übrigen ist es die einzige statische Variable der Klasse.

<TreeSet<String> set = new TreeSet<String>( String.CASE_INSENSITIVE_ORDER );
Collections.addAll( set, "noah", "abraham", "Isaak", "Ismael",
                    "moses", "JESUS", "Muhammed" );
System.out.println( set ); // [abraham, Isaak, Ismael, JESUS, moses, Muhammed, noah]

List<String> list = Arrays.asList( "A", "b", "ä", "ß", "S", "s" );
Comparator<Object> collator = Collator.getInstance( Locale.GERMAN );
Collections.sort( list, collator );
System.out.println( list ); // [A, ä, b, s, S, ß]

Daten in umgekehrter Reihenfolge sortieren

Da es keine spezielle Methode reverseSort() gibt, ist hier ein spezielles Comparator-Objekt im Einsatz, um Daten entgegengesetzt zu ihrer natürlichen Reihenfolge zu sortieren. Mit der statischen Methode reverseOrder() der Klasse Collections können wir ein geeignetes Comparator-Exemplar anfordern.

List<String> list = new ArrayList<String>();
Collections.addAll( list, "Adam", "Eva", "Set", "Enosch", "Kenan", "Mahalalel" );
Comparator<String> comparator = Collections.reverseOrder();
Collections.sort( list, comparator );
System.out.println( list ); // [Set, Mahalalel, Kenan, Eva, Enosch, Adam]

Eine andere Möglichkeit für umgekehrt sortierte Listen besteht darin, erst die Liste mit Collections.sort() zu sortieren und anschließend mit Collections.reverse(List<?> list) umzudrehen. Das Umdrehen ist jedoch ein zusätzlicher Durchlauf, der mit dem reverseOrder()-Comparator vermieden wird. Zudem ist die Lösung mit einem Comparator über reverseOrder() stabil. Für einen existierenden Comparator liefert Collections.reverseOrder(Comparator<T> cmp) einen Comparator<T>, der genau umgekehrt arbeitet.

13.6.3 Den größten und kleinsten Wert einer Collection finden

Bisher kennen wir die überladenen statischen Methoden min() und max() der Utility-Klasse Math für numerische Datentypen. Es gibt aber auch statische Methoden min() und max() in Collections und Arrays, die das kleinste und größte Element einer Sammlung ermitteln. Die Laufzeit ist linear zur Größe der Sammlung. Die Methoden unterscheiden nicht, ob die Elemente der Datenstruktur schon sortiert sind oder nicht.

class java.util.Collections

• 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 erforderlich ist, das den Vergleich vornimmt. Es sei auch bemerkt, dass dies mit die komplexesten Beispiele für Generics sind.

Aufbauen, Schütteln, Beschneiden, Größensuche

In unserem nächsten Beispiel geht es darum, dass zwei Spieler aus einem Kartenspiel mit 56 Karten je 10 zufällige Karten bekommen. Die Karten sind Java-enums. Derjenige mit der höchstwertigen Karte (ein Ass ist zum Beispiel mehr »wert« als eine Sieben) gewinnt, wobei auch beide gewinnen können, wenn sie die gleiche höchstwertige Karte haben. Auf die Anzahl der Karten kommt es nicht an.

Listing 13.6: com/tutego/insel/util/BestCard.java

package com.tutego.insel.util;

import java.util.*;

public class BestCard
{
  enum Cards { ONE, TWO, THREE, FOUR, FIVE, SIX, SEVEN, EIGHT,
               NINE, TEN, JACK, QUEEN, KING, ALAS }
  public static void main( String[] args )
  {
    // Initialisiere Kartenspiel, beginne mit 14 Karten
    List<Cards> cards = new ArrayList<Cards>( EnumSet.allOf( Cards.class ) );

    // Verdopple zweimal die Karten auf insgesamt 56
    cards.addAll( cards );
    cards.addAll( cards );

    // Vermische Karten
    Collections.shuffle( cards );

    // Der erste Spieler bekommt die ersten 10 Karten
    List<Cards> player1 = new ArrayList<Cards>( cards.subList( 0, 10 ) );

    // Der zweite Spieler bekommt die nächsten 10 Karten
    List<Cards> player2 = new ArrayList<Cards>( cards.subList( 11, 20 ) );

    // Größte Karte suchen, also die Karte mit der größten Ordinalzahl
    System.out.printf( "Spieler 1: %s%nSpieler 2: %s%n", player1, player2 );
    Cards bestCardPlayer1 = Collections.max( player1 );
    Cards bestCardPlayer2 = Collections.max( player2 );
    System.out.println( "Beste Karte Spieler 1: " + bestCardPlayer1 );
    System.out.println( "Beste Karte Spieler 2: " + bestCardPlayer2 );

    // Enums implementieren Comparable. Ausgeben, wer die beste Karte hat
    int winner = bestCardPlayer1.compareTo( bestCardPlayer2 );
    if ( winner > 0 )
      System.out.println( "Spieler 1 gewinnt" );
    else if ( winner < 0 )
      System.out.println( "Spieler 2 gewinnt" );
    else
      System.out.println( "Beide Spieler gewinnen" );
  }
}

Das Beispiel baut im ersten Schritt eine Liste mit Card-Objekten auf und schüttelt diese mit shuffle() durch. Dann ordnet subList() je zehn Karten dem ersten und dem zweiten Spieler zu. In dem Kontext wäre nicht unbedingt eine Kopie in eine neue ArrayList nötig gewesen, doch das ist bei einer Weiterführung des Beispiels vermutlich nützlicher, denn subList() ist eine Live-Ansicht, und wir könnten sonst keine Elemente aus der Unterliste löschen und hinzufügen, ohne dabei gleichzeitig die gesamten 56 Karten anzugreifen.

Aufzählungen sind Enum-Objekte, die Comparable implementieren und daher eine natürliche Ordnung haben. Aus diesem Grunde funktioniert max() überhaupt, was ein Ordnungskriterium zur Extremwertsuche benötigt. Aus den Karten der beiden Spieler ist so die größte Karte leicht ermittelt.

Implementierung der Extremwertmethoden bei Comparable-Objekten

Wenn wir ein String-Objekt in eine Liste packen oder ein Double-Objekt in eine Menge, werden sie korrekt gesucht, da insbesondere die Wrapper-Klassen die Schnittstelle Comparable implementieren.

An der Implementierung Collections.min() ohne extra Comparator lässt sich gut der Aufruf von compareTo() ablesen:

Listing 13.7: java/util/Collections.java, min()

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

Die generische Schreibweise verlangt, dass die Elemente in der Collection vom Typ Comparable sein müssen und somit eine compareTo()-Methode vorhanden ist.

Ihr Kommentar

Wie hat Ihnen das <openbook> gefallen? Wir freuen uns immer über Ihre freundlichen und kritischen Rückmeldungen.