Galileo Computing < openbook > Galileo Computing - Professionelle Bücher. Auch für Einsteiger.
Professionelle Bücher. Auch für Einsteiger

 << zurück
Java ist auch eine Insel von Christian Ullenboom
Programmieren für die Java 2-Plattform in der Version 5
Java ist auch eine Insel

Java ist auch eine Insel
5., akt. und erw. Auflage
1454 S., mit CD, 49,90 Euro
Galileo Computing
ISBN 3-89842-747-1
gp Kapitel 11 Datenstrukturen und Algorithmen
  gp 11.1 Datenstrukturen und die Collection-API
    gp 11.1.1 Die Schnittstelle Collection
    gp 11.1.2 Das erste Programm mit Container-Klassen
    gp 11.1.3 Die Schnittstelle Iterable und das erweiterte for
    gp 11.1.4 Generische Datentypen in der Collection-API
    gp 11.1.5 Generischer Typ bei Iterable und konkreter Typ beim erweiterten for
    gp 11.1.6 Schnittstellen, die Collection erweitern, und Map
    gp 11.1.7 Konkrete Container-Klassen
  gp 11.2 Mit einem Iterator durch die Daten wandern
    gp 11.2.1 Die Schnittstellen Enumeration und Iterator
    gp 11.2.2 Der typisierte Iterator
  gp 11.3 Listen
    gp 11.3.1 Die Schnittstelle List
    gp 11.3.2 Beispiel mit List-Methoden
    gp 11.3.3 ArrayList
    gp 11.3.4 Arrays.asList() und die »echten« Listen
    gp 11.3.5 toArray() von Collection verstehen – die Gefahr einer Falle erkennen
    gp 11.3.6 Die interne Arbeitsweise von ArrayList und Vector
    gp 11.3.7 LinkedList
  gp 11.4 Stack (Kellerspeicher, Stapel)
    gp 11.4.1 Die Methoden von Stack
    gp 11.4.2 Ein Stack ist ein Vector – aha!
  gp 11.5 Queues (Schlangen)
    gp 11.5.1 Blockierende Queues und Prioritätswarteschlangen
  gp 11.6 Assoziative Speicher HashMap und TreeMap
    gp 11.6.1 Ein Objekt der Klasse HashMap erzeugen
    gp 11.6.2 Einfügen und Abfragen der Datenstruktur
    gp 11.6.3 Wichtige Eigenschaften von Assoziativspeichern
    gp 11.6.4 Elemente im Assoziativspeicher müssen unveränderbar bleiben
    gp 11.6.5 Aufzählen der Elemente
    gp 11.6.6 Der Gleichheitstest, Hash-Wert und Klon einer Hash-Tabelle
    gp 11.6.7 Die Arbeitsweise einer Hash-Tabelle
  gp 11.7 Die Properties-Klasse
    gp 11.7.1 Properties setzen und lesen
    gp 11.7.2 Properties verketten
    gp 11.7.3 Eigenschaften ausgeben
    gp 11.7.4 Hierarchische Eigenschaften
    gp 11.7.5 Properties speichern
    gp 11.7.6 Über die Beziehung Properties und Hashtable
  gp 11.8 Mengen (Sets)
    gp 11.8.1 HashSet
    gp 11.8.2 TreeSet – die Menge durch Bäume
    gp 11.8.3 LinkedHashSet
  gp 11.9 Algorithmen in Collections
    gp 11.9.1 Datenmanipulation: Umdrehen, Füllen, Kopieren
    gp 11.9.2 Vergleichen von Objekten mit Comparator und Comparable
    gp 11.9.3 Größten und kleinsten Wert einer Collection finden
    gp 11.9.4 Sortieren
    gp 11.9.5 Elemente in der Collection suchen
    gp 11.9.6 Nicht-änderbare Datenstrukturen
    gp 11.9.7 nCopies()
    gp 11.9.8 Singletons
  gp 11.10 Synchronisation der Datenstrukturen
    gp 11.10.1 Lock-Free-Algorithmen aus java.util.concurrent
    gp 11.10.2 Wrapper zur Synchronisation
    gp 11.10.3 CopyOnWriteArrayList und CopyOnWriteArraySet
  gp 11.11 Die abstrakten Basisklassen für Container
    gp 11.11.1 Optionale Methoden
  gp 11.12 Die Klasse BitSet für Bitmengen
    gp 11.12.1 Ein BitSet anlegen und füllen
    gp 11.12.2 Mengenorientierte Operationen
    gp 11.12.3 Funktionsübersicht
    gp 11.12.4 Primzahlen in einem BitSet verwalten
  gp 11.13 Ein Design-Pattern durch Beobachten von Änderungen
    gp 11.13.1 Design-Pattern
    gp 11.13.2 Das Beobachter-Pattern (Observer/Observable)


Galileo Computing

11.9 Algorithmen in Collectiondowntop

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 doch nur mit Collection-Objekten und nicht mit Iteratoren.

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


Beispiel   Elemente gehen geordnet in eine Liste hinein und kommen durchgeschüttelt wieder heraus. Das wahllose Vertauschen der Elemente übernimmt Collections.shuffle(). Da shuffle() allgemein auf List-Objekten arbeitet, können wir hier LinkedList-, Vector- und ArrayList-Objekte einsetzen.

Listing 11.11   Shuffle.java, main()

List<String> v = new ArrayList<String>();
Collections.addAll( v, "Bube", "Dame", "König", "Ass" );
Collections.shuffle( v );
System.out.println( v );  // z. B. [König, Ass, Bube, Dame]

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


class java.util.Collections

gp  static void shuffle( List<?> list ) Würfelt die Elemente der Liste durcheinander. Dafür wird ein Standard-Generator für Zufallszahlen verwendet.
gp  static void shuffle( List<?> list, Random rnd ) Würfelt die Elemente der Liste durcheinander und benutzt dafür den Random-Generator rnd.

Galileo Computing

11.9.1 Datenmanipulation: Umdrehen, Füllen, Kopieren  downtop

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 dies 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 solche, die eventuell schon an den entsprechenden Positionen der Zielliste liegen. Die Zielliste muss mindestens so lang wie die Quellliste sein, andernfalls wird eine IndexOutOfBoundsException ausgeworfen. Hat das Ziel weitere Elemente, ist das egal, weil diese nicht angetastet werden.


class java.util.Collections

gp  static void reverse( List<?> l ) Kehrt die Reihenfolge der Elemente in der Liste um.
gp  static <T> void fill( List<? super T> list, T obj ) Überschreibt jedes vorhandene Element der Liste mit dem Element o.
gp  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.

Galileo Computing

11.9.2 Vergleichen von Objekten mit Comparator und Comparable  downtop

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?

Es mag überraschen, dass es in Java 2 zwei unterschiedliche Schnittstellen (in zwei unterschiedlichen Paketen) zur Sortierunterstützung gibt:

gp  java.util.Comparator definiert die Methode int compare(Object o1, Object o2). Eine Klasse, die sich Comparator nennt, implementiert die Schnittstelle und legt auf diese Weise die Ordnung fest.
gp  Die Schnittstelle java.lang.Comparable schreibt die Methode int compareTo(Object o) vor. Die Klasse implementiert die Schnittstelle, und ein Objekt kann sich mit einem anderen Objekt vergleichen. Da im Allgemeinen nur ein Sortierkriterium implementiert wird, heißt dieses natürliche Ordnung (engl. natural ordering).

Während Comparable im Allgemeinen nur ein Sortierkriterium umsetzt, kann es viele Extraklassen vom Typ Comparator geben, die jeweils unterschiedliche Ordnungen definieren. Ein Comparator für Diskotheken könnte zum Beispiel nach der Anzahl der Personen oder auch nach der Größe in Quadratmetern sortieren; die Implementierung von Comparable wäre nicht sinnvoll, weil hier nur ein Kriterium natürlich umgesetzt werden kann, eine Disko aber nicht die Ordnung hat.

Die Schnittstelle Comparable

Comparable definiert nur eine Methode:


interface java.lang.Comparable<T>

gp  int compareTo( T o ) Vergleicht sich mit einem Anderen.

Ganz wichtig ist neben einer Implementierung von compareTo() auch die passende Realisierung in equals(). Sie ist erst dann konsistent, wenn e1.compareTo(e2) == 0 das gleiche Ergebnis wie e1.equals(e2) liefert, wobei e1 und e2 Objekte der gleichen Klasse sind. Ein Verstoß dieser Regel kann bei sortierten Mengen schnell Probleme bereiten; ein Beispiel nennt die API-Dokumentation.

e.compareTo(null) sollte eine NullPointerException auslösen, auch wenn e.equals(null) die Rückgabe false liefert.

Die Schnittstelle Comparator

Die Schnittstelle Comparator definiert zwei Methoden:


interface java.util.Comparator<T>

gp  int compare( T o1, T o2 ) Vergleicht zwei Argumente auf ihre Ordnung.
gp  boolean equals( Object obj ) Testet, ob Comparator-Objekte gleich sind. Das testet keine Gleichheit von Objekten!

Die Methode equals() muss nicht implementiert werden, da ja schon aus Object eine Implementierung bereitgestellt wird.

Abbildung
Hier klicken, um das Bild zu Vergrößern

Comparable und Comparator in der Java-API

Eine Implementierung von Comparable findet sich genau dort, wo eine natürliche Ordnung nahe liegt, etwa bei:

gp  String
gp  BigDecimal, BigInteger, Byte, Character, Double, Float, Integer, Long, Short
gp  Date
gp  File, URI
gp  Enum
gp  TimeUnit

Von Comparator finden wir in der API-Dokumentation nur java.text.Collator vermerkt.

Um Such- oder Sortier-Operationen 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 Funktionen mit einem zusätzlichen Comparator und einmal ohne. Wird kein Comparator angegeben, so müssen die Objekte vom Typ Comparable sein.


class java.util.  Arrays  

gp  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.
gp  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.
gp  static int binarySearch( Object[] a, Object key ) Sucht binär nach key. Die Objekte im Feld müssen Comparable implementieren.
gp  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  

gp  static <T extends Comparable<? super T>> void sort( List<T> list )
gp  static <T> void sort( List<T> list, Comparator<? super T> c )
gp  static <T> int binarySearch( List<? extends Comparable<? super T>> list, T key )
gp  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 eine Implementierung von Comparable.


Galileo Computing

11.9.3 Größten und kleinsten Wert einer Collection finden  downtop

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 unterscheiden nicht, ob die Elemente der Datenstruktur schon sortiert sind oder nicht.


class java.util.Collections

gp  static <T extends Object & Comparable<? super T>> T min(Collection<? extends T> coll)
gp  static <T> T min(Collection<? extends T> coll, Comparator<? super T> comp)
gp  static <T extends Object & Comparable<? super T>> T max(Collection<? extends T> coll)
gp  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.

Bedeutung von Comparable bei min()

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, werden sie korrekt gesucht, da insbesondere die Wrapper-Klassen die Schnittstelle Comparable implementieren. In der Implementierung min() ohne extra Comparator lässt sich gut der Aufruf von compareTo() sehen.

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. Genauer steht dort, dass die Collection typisiert werden muss mit etwas, das mindestens T ist, wobei T extends Object & Comparable<? super T>. (Damit später die Methode compareTo() aufgerufen werden kann, wird das im Bytecode verankerte allgemeine java.lang.Object auf ein Comparable gecastet.)


Galileo Computing

11.9.4 Sortieredowntop

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

gp  sort(List): Die Variante nutzt die natürliche Ordnung, also Zahlen nach der Größe (19<34) und Zeichenketten alphanumerisch (Hansi<Raphael<Ulli).
gp  sort(List,Comparator): Die zweite Form arbeitet mit einem speziellen Comparator-Objekt, welches jeweils zwei Objekte mit seiner compare(Object, Object)-Methode vergleicht. Die natürliche Ordnung spielt keine Rolle.

Die Sortierfunktion arbeitet nur mit List-Objekten. Bei den anderen Datenstrukturen würde das ohnehin kaum sinnvoll sein, weil diese entweder unsortiert sind oder extern eine bestimmte Ordnung aufweisen, wie oben schon angemerkt. Eine analoge Sortierfunktion für die Elemente von Arrays, nämlich sort(), gibt es aber noch in der Klasse Array.


class java.util.Collections

gp  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.
gp  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.

Beispielprogramm zum Sortieren

Das folgende Programm sortiert eine Reihe von Zeichenketten aufsteigend. Zunächst nutzt es die Methode Arrays.asList(), um aus einem String-Feld eine Liste zu konstruieren und daraus eine veränderbare Liste aufzubauen. (Leider gibt es keinen Konstruktor für ArrayList, der ein Array von Strings direkt verarbeitet, daher dieser Umweg.) Anschließend setzten wir mit der unter Java 5 eingeführten neuen Funktion Collections.addAll() eine Reihe von weiteren Strings in die Liste. Praktisch an der Funktion addAll() ist, dass sie beliebig viele Argumente über ein Vargs annimmt.

Listing 11.12   CollectionsSortDemo.java

import java.util.*;
public class CollectionsSortDemo
{
  public static void main( String[] args )
  {
    List<String> list = new ArrayList<String>(
      Arrays.asList( new String[]{
      "Noah""Abraham""Isaak""Ismael""Moses""Jesus""Muhammed"  }
    ) );
    Collections.addAll( list,
      "Saskia""Regina",  "Angela""Astrid""Manuela""Silke",
      "Linda",  "Daniela""Silvia""Samah",  "Radhia",  "Mejda"
    );
      Collections.sort  ( list );
    System.out.println( list );
  }
}

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.

Implementierung von sort() über Arrays.sort()

Die sort()-Methode arbeitet intern mit der toArray()-Funktion der Klasse List. Die Elemente der Liste werden immer erst in ein temporäres Array kopiert und anschließend wird die sort()-Methode der Arrays-Klasse zum Sortieren genutzt. Am Ende überträgt ein ListIterator den sortierten Array-Inhalt zurück in die Liste.

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

Stabiles 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 demonstrieren. 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.

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() und alle Strings in Collection-Objekten über Collections.sort() sortiert werden.

Kommen weitere Sortierkriterien hinzu – und die gibt es in den unterschiedlichen Ländern allemal –, so helfen die Collator-Objekte, da sie spezielle Comparator-Objekte sind.

Comparator deutschCollator = Collator.getInstance( Locale.GERMAN );

Zum Sortieren unabhängig von der Groß- und Kleinschreibung 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.)

Daten in umgekehrter Reihenfolge sortieren

Da es keine spezielle Methode reverseSort() gibt, ist hier ein spezielles Comparator-Objekt im Einsatz, 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.13   CollectionsReverseSortDemo.java

import java.util.*;
public class CollectionsReverseSortDemo
{
  public static void main( String[] args )
  {
    List<String> list = new ArrayList<String>();
    Collections.addAll( list"Adam""Eva""Set""Enosch""Kenan""Mahalalel");
      Comparator<String> comparator = Collections.<String>reverseOrder();
      Collections.sort( listcomparator );
    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 sort() zu sortieren und anschließend mit Collections.reverse(List<?> list) umzudrehen. Die Lösung mit einem Comparator über reverseOrder() ist jedoch stabil. Für einen existierenden Comparator liefert Collections.reverseOrder(Comparator<T> cmp) einen Comparator<T>, der genau umgekehrt arbeitet.


Galileo Computing

11.9.5 Elemente in der Collection suchedowntop

Die Collection-Klassen enthalten mit contains(Object) eine Methode, die entweder true oder false zurückgibt, wenn ein Element gefunden wurde oder nicht. Wenn allerdings eine Liste sortiert ist, lässt sich eine Suche schneller 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 oft, bis das Element gefunden wurde. Auf diese Weise ist die Suche sehr schnell und benötigt höchstens log(n) Listenhalbierungen, bei einer Liste mit n Elementen. Es ist jedoch gut möglich, dass das gesuchte Element in der Liste nicht 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 die Liste etwa 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 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( lkey );
if ( pos < 0 )
  l.add( -pos – 1key);

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 lässt sich jedoch mit sort() sortieren. 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 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.


class java.util.Collections

gp  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.
gp  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 Elements

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


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


class java.util.Collections

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

Galileo Computing

11.9.6 Nicht-änderbare Datenstrukturen  downtop

So wie synchronizedXXX() einen Wrapper um existierende Datenstrukturen legt, verfahren auch diverse unmodifiableXXX()-Methoden der Utility-Klasse Collections. Sie lassen die Lese-Methoden zu dem Container durch, blocken Modifizierungsmethoden wie add() aber durch eine UnsupportedOperationException ab.


Galileo Computing

11.9.7 nCopies()  downtop

Die statische Funktion nCopies(int number, Object element) erzeugt eine Liste mit der gewünschten Anzahl von 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, doch keine Veränderungen. Infolgedessen ist der Einsatzbereich der Liste beschränkt, jener der Funktion 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, der sie die Werte entnimmt.


Beispiel   Initialisiere eine Liste mit 10 Leer-Strings und hänge an eine Liste 2 Zeichenketten mit ».« an.
List<String> list = new ArrayList<String>(   Collections.nCopies  (10, "") );
list.addAll(   Collections.nCopies  (2, ".") );
System.out.println( list );   // [, , , , , , , , , , ., .]


Galileo Computing

11.9.8 Singletons  toptop

Singletons sind Objekte, die genau ein Exemplar realisieren. singleton(T o) liefert ein Set<T> 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 erwartet sie als Argument eine Collection, die wir ja gerade durch singleton() bekommen, da ein Set eine Erweiterung von Collection ist!


Beispiel   Eine Funktion removeAll(Collection c, Object o), die jedes Vorkommen eines Objektes aus der Datenstruktur entfernt.
void removeAll( Collection<?> c, Object o )
{
  c.removeAll(   Collections.singleton(o)   );
}

Neben der einfachen Methode singleton(T o) gibt es noch singletonList(T o), die eine List<T> liefert, und singletonMap(K key, V value) für eine Map<K,V>.




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

 << zurück




Copyright © Galileo Press GmbH 2005
Für Ihren privaten Gebrauch dürfen Sie die Online-Version natürlich ausdrucken. Ansonsten unterliegt das <openbook> denselben Bestimmungen, wie die gebundene Ausgabe: Das Werk einschließlich aller seiner Teile ist urheberrechtlich geschützt. Alle Rechte vorbehalten einschließlich der Vervielfältigung, Übersetzung, Mikroverfilmung sowie Einspeicherung und Verarbeitung in elektronischen Systemen.


[Galileo Computing]

Galileo Press GmbH, Rheinwerkallee 4, 53227 Bonn, Tel.: 0228.42150.0, Fax 0228.42150.77, info@galileo-press.de