Rheinwerk Computing < openbook >


 
Inhaltsverzeichnis
Materialien
Vorwort
1 Java ist auch eine Sprache
2 Imperative Sprachkonzepte
3 Klassen und Objekte
4 Arrays und ihre Anwendungen
5 Der Umgang mit Zeichenketten
6 Eigene Klassen schreiben
7 Objektorientierte Beziehungsfragen
8 Ausnahmen müssen sein
9 Geschachtelte Typen
10 Besondere Typen der Java SE
11 Generics<T>
12 Lambda-Ausdrücke und funktionale Programmierung
13 Architektur, Design und angewandte Objektorientierung
14 Java Platform Module System
15 Die Klassenbibliothek
16 Einführung in die nebenläufige Programmierung
17 Einführung in Datenstrukturen und Algorithmen
18 Einführung in grafische Oberflächen
19 Einführung in Dateien und Datenströme
20 Einführung ins Datenbankmanagement mit JDBC
21 Bits und Bytes, Mathematisches und Geld
22 Testen mit JUnit
23 Die Werkzeuge des JDK
A Java SE-Module und Paketübersicht
Stichwortverzeichnis


Download:

- Listings, ca. 2,7 MB


Buch bestellen
Ihre Meinung?



Spacer
<< zurück
Java ist auch eine Insel von Christian Ullenboom

Einführung, Ausbildung, Praxis
Buch: Java ist auch eine Insel


Java ist auch eine Insel

Pfeil 4 Arrays und ihre Anwendungen
Pfeil 4.1 Einfache Feldarbeit
Pfeil 4.1.1 Grundbestandteile
Pfeil 4.1.2 Deklaration von Array-Variablen
Pfeil 4.1.3 Array-Objekte mit new erzeugen
Pfeil 4.1.4 Arrays mit { Inhalt }
Pfeil 4.1.5 Die Länge eines Arrays über das Attribut length auslesen
Pfeil 4.1.6 Zugriff auf die Elemente über den Index
Pfeil 4.1.7 Typische Array-Fehler
Pfeil 4.1.8 Arrays an Methoden übergeben
Pfeil 4.1.9 Mehrere Rückgabewerte *
Pfeil 4.1.10 Vorinitialisierte Arrays
Pfeil 4.2 Die erweiterte for-Schleife
Pfeil 4.3 Methode mit variabler Argumentanzahl (Varargs)
Pfeil 4.3.1 System.out.printf(…) nimmt eine beliebige Anzahl von Argumenten an
Pfeil 4.3.2 Durchschnitt finden von variablen Argumenten
Pfeil 4.3.3 Varargs-Designtipps *
Pfeil 4.4 Mehrdimensionale Arrays *
Pfeil 4.4.1 Nichtrechteckige Arrays *
Pfeil 4.5 Bibliotheksunterstützung von Arrays
Pfeil 4.5.1 Klonen kann sich lohnen – Arrays vermehren
Pfeil 4.5.2 Warum »können« Arrays so wenig?
Pfeil 4.5.3 Array-Inhalte kopieren
Pfeil 4.6 Die Klasse Arrays zum Vergleichen, Füllen, Suchen und Sortieren nutzen
Pfeil 4.6.1 Eine lange Schlange
Pfeil 4.7 Der Einstiegspunkt für das Laufzeitsystem: main(…)
Pfeil 4.7.1 Korrekte Deklaration der Startmethode
Pfeil 4.7.2 Kommandozeilenargumente verarbeiten
Pfeil 4.7.3 Der Rückgabetyp von main(…) und System.exit(int) *
Pfeil 4.8 Zum Weiterlesen
 

Zum Seitenanfang

4.6    Die Klasse Arrays zum Vergleichen, Füllen, Suchen und Sortieren nutzen Zur vorigen ÜberschriftZur nächsten Überschrift

Die Klasse java.util.Arrays deklariert nützliche statische Methoden für den Umgang mit Arrays. So bietet sie Möglichkeiten zum Vergleichen, Sortieren und Füllen von Arrays sowie zur binären Suche.

String-Repräsentation eines Arrays

Nehmen wir an, wir haben es mit einem Array von Hundenamen zu tun, das wir auf dem Bildschirm ausgeben wollen:

Listing 4.13    DogArrayToString, main()

String[] dogs = {

"Flocky Fluke", "Frizzi Faro", "Fanny Favorit", "Frosty Filius",

"Face Flash", "Fame Friscco"

};

Soll der Array-Inhalt zum Testen auf den Bildschirm gebracht werden, so kommt eine Ausgabe mit System.out.println(dogs) nicht infrage, denn toString() ist auf dem Objekttyp Array nicht sinnvoll definiert:

System.out.println( dogs );                  // [Ljava.lang.String;@10b62c9

Die statische Methode Arrays.toString(array) liefert für unterschiedliche Arrays die gewünschte String-Repräsentation des Arrays:

System.out.println( Arrays.toString(dogs) ); // [Flocky Fluke, ...]

Das spart nicht unbedingt eine for-Schleife, die durch das Array läuft und auf jedem Element printXXX(…) aufruft, denn die Ausgabe ist immer von einem bestimmten Format, das mit [ beginnt, jedes Element mit Komma und einem Leerzeichen trennt und mit ] abschließt.

Die Klasse Arrays deklariert die toString()-Methode für unterschiedliche Array-Typen:

class java.util.Arrays
  • static String toString(XXX[] a)

    Liefert eine String-Repräsentation des Arrays. Der Typ XXX steht stellvertretend für boolean, byte, char, short, int, long, float, double.

  • static String toString(Object[] a)

    Liefert eine String-Repräsentation des Arrays. Im Fall des Objekttyps ruft die Methode auf jedem Objekt im Array toString() auf.

  • static String deepToString(Object[] a)

    Ruft auch auf jedem Unter-Array Arrays.toString(…) auf und nicht nur toString() wie bei jedem anderen Objekt.

Sortieren

Diverse statische Arrays.sort(…)/Arrays.parallelSort(…)-Methoden ermöglichen das Sortieren von Elementen im Array. Bei primitiven Elementen (kein boolean) gibt es keine Probleme, da sie eine natürliche Ordnung haben.

[zB]  Beispiel

Sortiere zwei Arrays:

int[] numbers = { -1, 3, -10, 9, 3 };

String[] names = { "Xanten", "Alpen", "Wesel" };

Arrays.sort( numbers );

Arrays.sort( names );

System.out.println( Arrays.toString( numbers ) ); // [-10, -1, 3, 3, 9]

System.out.println( Arrays.toString( names ) ); // [Alpen, Wesel, Xanten]

Besteht das Array aus Objektreferenzen, müssen die Objekte vergleichbar sein. Das gelingt entweder mit einem Extra-Comparator, oder die Klassen implementieren die Schnittstelle Comparable, wie zum Beispiel Strings. Kapitel 10, »Besondere Typen der Java SE«, beschreibt diese Möglichkeiten im Detail.

class java.util.Arrays
  • static void sort(XXX[] a )

  • static void sort(XXX[] a, int fromIndex, int toIndex)

    Sortiert die gesamte Liste vom Typ XXX (wobei XXX für byte, char, short, int, long, float oder double steht) oder einen ausgewählten Teil. Bei angegebenen Grenzen ist fromIndex wieder inklusiv und toIndex exklusiv. Sind die Grenzen fehlerhaft, löst die Methode eine IllegalArgumentException (im Fall fromIndex > toIndex) oder eine ArrayIndexOutOfBoundsException (fromIndex < 0 oder toIndex > a.length) aus.

  • static void sort(Object[] a)

  • static void sort(Object[] a, int fromIndex, int toIndex)

    Sortiert ein Array von Objekten. Die Elemente müssen Comparable implementieren.[ 127 ](Das stimmt nicht wirklich: Besteht das Array aus keinem oder nur einem Element, ist nichts zu vergleichen, also ist folglich auch nicht relevant, ob der Objekttyp Comparable ist. ) Bei der Methode gibt es keinen generischen Typparameter, der das zur Übersetzungszeit erzwingt!

  • static <T> void sort(T[] a, Comparator<? super T> c)

  • static <T> void sort(T[] a, int fromIndex, int toIndex, Comparator<? super T> c)

    Sortiert ein Array von Objekten mit gegebenem Comparator.

Paralleles Sortieren

Spezielle Sortiermethoden sind für sehr große Arrays gedacht. Bei den parallelSort(…)-Methoden verwendet die Bibliothek mehrere Threads, um Teile parallel zu sortieren, was die Geschwindigkeit erhöhen kann. Eine Garantie ist das aber nicht, denn ein Performance-Vorteil ergibt sich wirklich nur bei großen Arrays.

class java.util.Arrays
  • static void parallelSort(byte[] a)

  • static void parallelSort(byte[] a, int fromIndex, int toIndex)

  • static void parallelSort(char[] a)

  • static void parallelSort(char[] a, int fromIndex, int toIndex)

  • static void parallelSort(short[] a)

  • static void parallelSort(short[] a, int fromIndex, int toIndex)

  • static void parallelSort(int[] a)

  • static void parallelSort(int[] a, int fromIndex, int toIndex)

  • static void parallelSort(long[] a)

  • static void parallelSort(long[] a, int fromIndex, int toIndex)

  • static void parallelSort(float[] a)

  • static void parallelSort(float[] a, int fromIndex, int toIndex)

  • static void parallelSort(double[] a)

  • static void parallelSort(double[] a, int fromIndex, int toIndex)

  • static <T extends Comparable<? super T>> void parallelSort(T[] a)

  • static <T extends Comparable<? super T>> void parallelSort(T[] a, int fromIndex,

    int toIndex)

  • static <T> void parallelSort(T[] a, Comparator<? super T> c)

  • static <T> void parallelSort(T[] a, int fromIndex, int toIndex,

    Comparator<? super T> c)

Der verwendete Algorithmus ist einfach zu verstehen: Zunächst wird das Array in Teil-Arrays partitioniert, diese werden parallel sortiert und dann zu einem größeren sortierten Array zusammengelegt. Das Verfahren nennt sich im Englischen auch parallel sort-merge.

Arrays von Primitiven mit Arrays.equals(…) und Arrays.deepEquals(…) vergleichen *

Die statischen Methoden Arrays.equals(…) vergleichen, ob zwei Arrays die gleichen Inhalte besitzen; dazu ist die überladene Methode für alle wichtigen Typen definiert. Wenn zwei Arrays tatsächlich die gleichen Inhalte besitzen, ist die Rückgabe der Methode true, sonst false. Natürlich müssen beide Arrays schon die gleiche Anzahl von Elementen besitzen, sonst ist der Test sofort vorbei und das Ergebnis false.

[zB]  Beispiel

Vergleiche drei Arrays:

int[] array1 = { 1, 2, 3, 4 };

int[] array2 = { 1, 2, 3, 4 };

int[] array3 = { 9, 9, 2, 3, 9 };

System.out.println( Arrays.equals( array1, array2 ) ); // true

System.out.println( Arrays.equals( array2, 1, 3, array3, 2, 4 ) ); // true

Ein Vergleich von Teil-Arrays ist erst in Java 9 hinzugekommen.

Bei unterreferenzierten Arrays (Arrays zeigen auf Arrays) betrachtet Arrays.equals(…) das innere Array als einen Objektverweis und vergleicht es auch mit equals(…) – was jedoch bedeutet, dass nicht identische, aber mit gleichen Elementen referenzierte innere Arrays als ungleich betrachtet werden. Die statische Methode deepEquals(…) bezieht auch unterreferenzierte Arrays in den Vergleich mit ein.

[zB]  Beispiel

Der Unterschied zwischen equals(…) und deepEquals(…):

int[][] a1 = { { 0, 1 }, { 1, 0 } };

int[][] a2 = { { 0, 1 }, { 1, 0 } };

System.out.println( Arrays.equals( a1, a2 ) ); // false

System.out.println( Arrays.deepEquals( a1, a2 ) ); // true

System.out.println( a1[0] ); // zum Beispiel [I@10b62c9

System.out.println( a2[0] ); // zum Beispiel [I@82ba41

Dass die Methoden unterschiedlich arbeiten, zeigen die beiden letzten Konsolenausgaben: Die von a1 und a2 unterreferenzierten Arrays enthalten die gleichen Elemente, sind aber zwei unterschiedliche Objekte, also nicht identisch.

[»]  Hinweis

deepEquals(…) vergleicht auch eindimensionale Arrays:

Object[] b1 = { "1", "2", "3" };

Object[] b2 = { "1", "2", "3" };

System.out.println( Arrays.deepEquals( b1, b2 ) ); // true
class java.util.Arrays
  • static boolean equals(XXX[] a, XXX[] a2)

    Vergleicht zwei Arrays gleichen Typs und liefert true, wenn die Arrays gleich groß und die Elemente paarweise gleich sind. XXX steht stellvertretend für boolean, byte, char, int, short, long, double oder float.

  • static boolean equals(XXX[] a, int aFromIndex, int aToIndex, XXX[] b,  int bFromIndex, int bToIndex)

    Vergleicht zwei Arrays, bleibt jedoch in den gewählten Ausschnitten. In Java 9 kamen diverse neue überladene Methoden hinzu.

Objekt-Arrays mit Arrays.equals(…) und Arrays.deepEquals(…) vergleichen *

Die Arrays.equals(…)-Methode kann auch Arrays mit beliebigen Objekten vergleichen, doch nutzt sie dann nicht die Identitätsprüfung per ==, sondern die Gleichwertigkeit per equals(…). Eine seit Java 9 hinzugekommene Methode fragt einen Comparator.

[zB]  Beispiel

Enthalten zwei String-Arrays die gleichen Wörter, wobei Groß-/Kleinschreibung keine Rolle spielt?

String[] words1 = { "Zufriedenheit", "übertrifft" , "Reichtum" };

String[] words2 = { "REICHTUM", "übertrifft" , "ZuFRIEDEnheit" };

Arrays.sort( words1, String.CASE_INSENSITIVE_ORDER );

Arrays.sort( words2, String.CASE_INSENSITIVE_ORDER );

System.out.println( Arrays.equals( words1, words2,

String.CASE_INSENSITIVE_ORDER ) );
class java.util.Arrays
  • static boolean equals(Object[] a, Object[] b)

    Vergleicht zwei Arrays mit Objektverweisen. Ein Objekt-Array darf null enthalten; dann gilt für die Gleichwertigkeit, dass für alle Elemente e1 aus a und e2 aus b an gleicher Stelle gilt: e1==null ? e2==null : e1.equals(e2).

  • static boolean deepEquals(Object[] a, Object[] b)

    Liefert true, wenn die beiden Arrays ebenso wie alle Unter-Arrays – rekursiv im Fall von Unter-Objekt-Arrays – gleich sind.

  • static <T> boolean equals(T[] a, T[] b, Comparator<? super T> cmp)

    Vergleicht zwei Arrays mit einem Comparator, und cmp.compare(a[i], b[i]) muss für alle Pärchen 0 sein, damit beide Elemente als gleich gelten. Die Angabe <? super T> können wir erst einmal ignorieren.

  • static <T> boolean equals(T[] a, int aFromIndex, int aToIndex, T[] b, int bFromIndex, int bToIndex, Comparator<? super T> cmp)

    Vergleicht Ausschnitte von Arrays mit einem Comparator.

Unterschiede suchen mit mismatch (…) *

Weiterhin gibt es die folgenden Methoden:

  • int mismatch(XXX[] a, XXX[] b)

  • int mismatch(XXX[] a, int aFromIndex, int aToIndex, XXX[] b, int bFromIndex, int bToIndex)

Sie geben den Index auf das erste Element zurück, das ungleich ist. Sind beide Arrays gleich, ist die Rückgabe –1.

Für Objekt-Array gibt es weiterhin:

  • int mismatch(Object[] a, Object[] b)

  • int mismatch(Object[] a, int aFromIndex, int aToIndex, Object[] b, int bFromIndex, int bToIndex)

  • <T> int mismatch(T[] a, T[] b, Comparator<? super T> cmp)

  • <T> int mismatch(T[] a, int aFromIndex, int aToIndex, T[] b, int bFromIndex, int bToIndex, Comparator<? super T> cmp)

Die erste und zweite Methode nutzt direkt equals(…), die dritte und vierte verwendet einen externen Comparator.

Füllen von Arrays *

Arrays.fill(…) füllt ein Array mit einem festen Wert. Der Start-End-Bereich lässt sich optional angeben.

[zB]  Beispiel

Fülle ein char-Array mit Sternchen:

char[] chars = new char[ 4 ];

Arrays.fill( chars, '*' );

System.out.println( Arrays.toString( chars ) ); // [*, *, *, *]
class java.util.Arrays
  • static void fill(XXX[] a, XXX val)

  • static void fill(XXX[] a, int fromIndex, int toIndex, XXX val)

    Setzt das Element val in das Array. Mögliche Typen für XXX sind boolean, char, byte, short, int, long, double, float oder mit Object beliebige Objekte. Beim Bereich ist fromIndex inklusiv und toIndex exklusiv.

Neben der Möglichkeit, ein Array mit festen Werten zu füllen, gibt es außerdem die Methoden setAll(…)/parallelSetAll(…). Die Methoden durchlaufen ein gegebenes Array und rufen eine bestimmte Methode für jeden Index auf, die zur Initialisierung verwendet wird.

[zB]  Beispiel *

Fülle ein double-Array mit Zufallszahlen:

double[] randoms = new double[ 10 ];

Arrays.setAll( randoms, v -> Math.random() );

System.out.println( Arrays.toString( randoms ) );

Das Beispiel nutzt Lambda-Ausdrücke, um die Funktion zu beschreiben. Wir kommen in Kapitel 12, »Lambda-Ausdrücke und funktionale Programmierung«, auf diese Syntax noch einmal zurück.

class java.util.Arrays
  • static void setAll(int[] array, IntUnaryOperator generator)

  • static void setAll(double[] array, IntToDoubleFunction generator)

  • static void setAll(long[] array, IntToLongFunction generator)

  • static <T> void setAll(T[] array, IntFunction<? extends T> generator)

  • static void parallelSetAll(double[] array, IntToDoubleFunction generator)

  • static void parallelSetAll(int[] array, IntUnaryOperator generator)

  • static void parallelSetAll(long[] array, IntToLongFunction generator)

  • static <T> void parallelSetAll(T[] array, IntFunction<? extends T> generator)

    Läuft ein gegebenes Array komplett ab und übergibt dabei dem generator Schritt für Schritt den Index. Der Generator bildet den Index auf einen Wert ab, der wiederum zur Array-Initialisierung genutzt wird.

Array-Abschnitte kopieren *

Die Klasse Arrays bietet eine Reihe von copyOf(…)- und copyOfRange(…)-Methoden, die gegenüber clone() den Vorteil haben, dass sie auch Bereichsangaben erlauben und das neue Array größer machen können; im letzten Fall füllen die Methoden das Array je nach Typ mit null, false oder 0.

[zB]  Beispiel
String[] snow = { "Neuschnee", "Altschnee", "Harsch", "Firn" };

String[] snow1 = Arrays.copyOf( snow, 2 ); // [Neuschnee, Altschnee]

String[] snow2 = Arrays.copyOf( snow, 5 ); // [Neuschnee, Altschnee, Harsch,

// Firn, null]

String[] snow3 = Arrays.copyOfRange( snow, 2, 4 ); // [Harsch, Firn]

String[] snow4 = Arrays.copyOfRange( snow, 2, 5 ); // [Harsch, Firn, null]
class java.util.Arrays
  • static boolean[] copyOf(boolean[] original, int newLength)

  • static byte[] copyOf(byte[] original, int newLength)

  • static char[] copyOf(char[] original, int newLength)

  • static double[] copyOf(double[] original, int newLength)

  • static float[] copyOf(float[] original, int newLength)

  • static int[] copyOf(int[] original, int newLength)

  • static long[] copyOf(long[] original, int newLength)

  • static short[] copyOf(short[] original, int newLength)

  • static <T> T[] copyOf(T[] original, int newLength)

  • static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType)

  • static boolean[] copyOfRange(boolean[] original, int from, int to)

  • static byte[] copyOfRange(byte[] original, int from, int to)

  • static char[] copyOfRange(char[] original, int from, int to)

  • static double[] copyOfRange(double[] original, int from, int to)

  • static float[] copyOfRange(float[] original, int from, int to)

  • static int[] copyOfRange(int[] original, int from, int to)

  • static long[] copyOfRange(long[] original, int from, int to)

  • static short[] copyOfRange(short[] original, int from, int to)

  • static <T> T[] copyOfRange(T[] original, int from, int to)

  • static <T,U> T[] copyOfRange(U[] original, int from, int to,

    Class<? extends T[]> newType)

    Erzeugt ein neues Array mit der gewünschten Größe bzw. dem angegebenen Bereich aus einem existierenden Array. Wie üblich ist der Index from inklusiv und to exklusiv.

[zB]  Beispiel *

Hänge zwei Arrays aneinander. Das ist ein gutes Beispiel für copyOf(…), wenn das Ziel-Array größer ist:

public static <T> T[] concat( T[] first, T[] second ) {

T[] result = Arrays.copyOf( first, first.length + second.length );

System.arraycopy( second, 0, result, first.length, second.length );



return result;

}

Hinweis: Das Beispiel nutzt Generics (siehe Kapitel 11, »Generics<T>«), um den Typ flexibel zu halten. Zum einfacheren Verständnis können wir uns T als Typ Object vorstellen und das, was in spitzen Klassen steht, löschen.

Halbierungssuche *

Ist das Array sortiert, lässt sich mit Arrays.binarySearch(…) eine binäre Suche (Halbierungssuche) durchführen. Ist das Array nicht sortiert, ist das Ergebnis unvorhersehbar. Findet binarySearch(…) das Element, ist der Rückgabewert der Index der Fundstelle, andernfalls ist die Rückgabe negativ.

[zB]  Beispiel

Suche ein Element im sortierten Array:

int[] numbers = { 1, 10, 100, 1000 };

System.out.println( Arrays.binarySearch( numbers, 100 ) ); // 2

Ist das Array nicht aufsteigend sortiert, ist ein falsches Ergebnis die Folge.

binarySearch(…) liefert in dem Fall, dass das Element nicht im Array ist, eine kodierte Position zurück, an der das Element eingefügt werden könnte. Damit der Index nicht mit einer normalen Position einer Fundstelle kollidiert, die immer ≥ 0 ist, ist die Rückgabe negativ und als -Einfügeposition - 1 kodiert.

[zB]  Beispiel

Das Element 101 ist nicht im Array:

int[] numbers = { 1, 10, 100, 1000 };

System.out.println( Arrays.binarySearch( numbers, 101 ) ); // -4

Die Rückgabe ist –4, denn –4 = –3 – 1, was eine mögliche Einfügeposition von 3 ergibt. Das ist korrekt, denn 101 käme wie folgt ins Array: 1 (Position 0), 10 (Position 1), 100 (Position 2), 101 (Position 3).

[+]  Tipp

Da das Array bei Arrays.binarySearch(…) zwingend sortiert sein muss, kann ein vorangehendes Arrays.sort(…) dies vorbereiten:

int[] numbers = { 10, 100, 1000, 1 };

Arrays.sort( numbers );

System.out.println( Arrays.toString( numbers ) ); // [1, 10, 100, 1000]

System.out.println( Arrays.binarySearch( numbers, 100 ) ); // 2

Die Sortierung ist nur einmal nötig und sollte nicht unnötigerweise wiederholt werden.

class java.util.Arrays
  • static int binarySearch(XXX[] a, XXX key)

    Sucht mit der Halbierungssuche nach einem Schlüssel. XXX steht stellvertretend für byte, char, int, long, float oder double.

  • static int binarySearch(Object[] a, Object key)

    Sucht mit der Halbierungssuche nach key. Die Objekte müssen die Schnittstelle Comparable implementieren. Das bedeutet im Allgemeinen, dass die Elemente vom gleichen Typ sein müssen – also nicht Strings und Hüpfburg-Objekte gemischt.

  • static <T> int binarySearch(T[] a, T key, Comparator<? super T> c)

    Sucht mit der Halbierungssuche ein Element im Objekt-Array. Die Vergleiche übernimmt ein spezielles Vergleichsobjekt c.

  • static <T> int binarySearch(T[] a, int fromIndex, int toIndex,

    T key, Comparator<? super T> c)

    Schränkt die Binärsuche auf Bereiche ein.

Die API-Dokumentation von binarySearch(…) ist durch Verwendung der Generics (mehr darüber folgt in Kapitel 11, »Generics<T>«) etwas schwieriger. Wir werden in Kapitel 17, »Einführung in Datenstrukturen und Algorithmen«, auch noch einmal auf die statische Methode binarySearch(…) für beliebige Listen zurückkommen und insbesondere die Bedeutung der Schnittstellen Comparator und Comparable in Kapitel 10, »Besondere Typen der Java SE«, genau klären.

Lexikografische Array-Vergleiche mit compare(…) und compareUnsigned(…)

Diverse in Java 9 eingeführte int compareXXX(XXX[] a, XXX[] b)-Methoden gehen die Arrays ab und testen alle Paare auf ihre Ordnung. Es gibt die von Comparator bekannte Rückgabe: Ist jedes a[i] == b[i], ist die Rückgabe 0. Ist in der Abfragefolge ein a[i] kleiner als b[i], dann ist die Rückgabe negativ; ist ein a[i] größer als b[i], ist die Rückgabe positiv. Die Methode ist überladen mit einer Variante, die einen Bereich im Array auswählt: compare(XXX[] a, int aFromIndex, int aToIndex, XXX[] b, int bFromIndex, int bToIndex). Für byte, short, int und long gibt es weiterhin eine Vergleichsmethode ohne Vorzeichen über den gesamten Wertebereich:

  • int compareUnsigned(XXX[] a, XXX[] b)

  • int compareUnsigned(XXX[] a, int aFromIndex, int aToIndex, XXX[] b, int bFromIndex, int bToIndex)

Für Objekte gibt es eigene Methoden:

  • static <T extends Comparable<? super T>> int compare(T[] a, T[] b)

    Vergleicht zwei Objekt-Arrays, wobei der Comparator die Ordnung der Objektpaare feststellt.

  • static <T extends Comparable<? super T>> int compare(T[] a, int aFromIndex, int aToIndex, T[] b, int bFromIndex, int bToIndex)

    Vergleicht Ausschnitte.

  • static <T> int compare(T[] a, T[] b, Comparator<? super T> cmp)

  • static <T> int compare(T[] a, int aFromIndex, int aToIndex,T[] b, int bFromIndex, int bToIndex, Comparator<? super T> cmp)

    Vergleicht mithilfe eines externen Comparator-Objekts.

Arrays zu Listen mit Arrays.asList(…) – praktisch für die Suche und zum Vergleichen *

Ist das Array unsortiert, funktioniert binarySearch(…) nicht. Die Klasse Arrays hat für diesen Fall keine Methode im Angebot – eine eigene Schleife muss her. Es gibt aber noch eine Möglichkeit: Die statische Methode Arrays.asList(…) dekoriert das Array als Liste vom Typ java.util.List, die dann praktische Methoden wie contains(…), equals(…) oder subList(…) anbietet. Mit den Methoden sind Dinge auf Arrays möglich, für die Arrays bisher keine Methoden definierte.

[zB]  Beispiel

Teste, ob auf der Kommandozeile der Schalter -? gesetzt ist. Die auf der Kommandozeile übergebenen Argumente übergibt die Laufzeitumgebung als String-Array an die main(String[] args)-Methode:

if ( Arrays.asList( args ).contains( "-?" ) )

...
[zB]  Beispiel

Teste, ob Teile zweier Arrays gleich sind:

// Index         0                1          2

String[] a = { "Asus", "Elitegroup", "MSI" };

String[] b = { "Elitegroup", "MSI", "Shuttle" };



System.out.println( Arrays.asList( a ).subList( 1, 3 ).

equals( Arrays.asList( b ).subList( 0, 2 ) ) ); // true

Im Fall von subList(…) ist der Start-Index inklusiv und der End-Index exklusiv (das ist die Standardnotation von Bereichen in Java, etwa auch bei substring(…) oder fill(…)). Somit werden im obigen Beispiel die Einträge 1 bis 2 aus a mit den Einträgen 0 bis 1 aus b verglichen.

class java.util.Arrays
  • static <T> List<T> asList(T... a)

    Liefert eine Liste vom Typ T bei einem Array vom Typ T.

Die statische Methode asList(…) nimmt über das Vararg entweder ein Array von Objekten (kein primitives Array!) an oder aufgezählte Elemente.

[»]  Hinweis

Im Fall der aufgezählten Elemente ist auch kein oder genau ein Element erlaubt:

System.out.println( Arrays.asList() );                // []

System.out.println( Arrays.asList("Chris") ); // [Chris]
[»]  Hinweis

Ein an Arrays.asList(…) übergebenes primitives Array liefert keine Liste von primitiven Elementen (es gibt keine List, die mit primitiven Werten gefüllt ist):

int[] nums = { 1, 2 };

System.out.println( Arrays.asList(nums).toString() ); // [[I@82ba41]

System.out.println( Arrays.toString(nums) ); // [1, 2]

Der Grund ist einfach: Arrays.asList(…) erkennt nums nicht als Array von Objekten, sondern als genau ein Element einer Aufzählung. So setzt die statische Methode das Array mit Primitiven als ein Element in die Liste, und die Objektmethode toString() eines java.util.List-Objekts ruft lediglich auf dem Array-Objekt toString() auf, was die kryptische Ausgabe zeigt.

Parallele Berechnung von Präfixen *

Stehen mehrere Prozessoren oder Kerne zur Verfügung, können bestimmte Berechnungen bei Arrays parallelisiert werden. Ein Algorithmus nennt sich parallele Präfix-Berechnung und basiert auf der Idee, dass eine assoziative Funktion – nennen wir sie f – auf eine bestimmte Art und Weise auf Elemente eines Arrays – nennen wir es a – angewendet wird, nämlich so:

  • a[0]

  • f(a[0], a[1])

  • f(a[0], f(a[1], a[2]))

  • f(a[0], f(a[1], f(a[2], a[3])))

  • f(a[0], f(a[1],f(a[n-2], a[n-1])…))

In der Aufzählung sieht das etwas verwirrend aus, daher soll ein praktisches Beispiel das Verständnis erleichtern. Das Array sei [1, 3, 0, 4] und die binäre Funktion die Addition.

Index

Funktion

Ergebnis

0

a[0]

1

1

a[0] + a[1]

1 + 3 = 4

2

a[0] + (a[1] + a[2])

1 + (3 + 0) = 4

3

a[0] + (a[1] + (a[2] + a[3]))

1 + (3 + (0 + 4)) = 8

Tabelle 4.2    Präfix-Berechnung des Arrays [1, 3, 0, 4] mit Additionsfunktion

Auf den ersten Blick wirkt das wenig spannend, doch kann der Algorithmus parallelisiert werden und somit im besten Fall in logarithmischer Zeit (mit n Prozessoren) gelöst werden. Voraussetzung dafür ist allerdings eine assoziative Funktion, wie Summe und Maximum. Ohne ins Detail zu gehen, könnten wir uns vorstellen, dass ein Prozessor/Kern 0 + 4 berechnet, ein anderer zeitgleich 1 + 3 und dass dann das Ergebnis zusammengezählt wird.

[zB]  Beispiel *

Das Beispiel unserer Präfix-Berechnung mithilfe einer Methode aus Arrays:

int[] array = {1, 3, 0, 4};

Arrays.parallelPrefix( array, (a, b) -> a + b );

System.out.println( Arrays.toString( array ) ); // [1, 4, 4, 8]

Die Implementierung nutzt die fortgeschrittene Syntax der Lambda-Ausdrücke. Statt (a + b) ‐> a + b verkürzt es Integer::sum sogar noch.

Ein weiteres Beispiel: Finde das Maximum in einer Menge von Fließkommazahlen:

double[] array = {4.8, 12.4, -0.7, 3.8 };

Arrays.parallelPrefix( array, Double::max );

System.out.println( array[array.length -1 ] ); // 12.4

Das Beispiel nutzt schon die Methode, die Arrays für die parallele Präfix-Berechnung bietet:

class java.util.Arrays
  • static void parallelPrefix(int[] array, IntBinaryOperator op)

  • static void parallelPrefix(int[] array, int fromIndex, int toIndex,

    IntBinaryOperator op)

  • static void parallelPrefix(long[] array, LongBinaryOperator op)

  • static void parallelPrefix(long[] array, int fromIndex, int toIndex,

    LongBinaryOperator op)

  • static void parallelPrefix(double[] array, DoubleBinaryOperator op)

  • static void parallelPrefix(double[] array, int fromIndex, int toIndex,

    DoubleBinaryOperator op)

  • static <T> void parallelPrefix(T[] array, BinaryOperator<T> op)

  • static <T> void parallelPrefix(T[] array, int fromIndex, int toIndex,

    BinaryOperator<T> op)

 

Zum Seitenanfang

4.6.1    Eine lange Schlange Zur vorigen ÜberschriftZur nächsten Überschrift

Das neu erworbene Wissen über Arrays wollen wir für unser Schlangenspiel nutzen, um die Schlange länger zu machen. Bisher hatte die Schlange keine Länge, sondern nur eine Position auf dem Spielbrett. Das wollen wir ändern: Ein Programm im Array soll sich immer die letzten Positionen merken. Folgende Änderungen sind dazu nötig:

  • Anstatt die Position in einem Point-Objekt zu speichern, liegen die letzten fünf Positionen in einem Point[] snakePositions.

  • Trifft der Spieler einen dieser fünf Schlangenpunkte, ist das Spiel verloren. Ist bei der Bildschirmausgabe eine Koordinate gleich einem der Schlangenpunkte, zeichnen wir ein »S«. Der Test, ob eine der Schlangenkoordinaten einen Punkt p trifft, wird mit Arrays.asList(snakePositions).contains(p) durchgeführt.

Ein weiterer Punkt ist, dass die Schlange sich bewegt, aber das Array mit den fünf Punkten immer nur die letzten fünf Bewegungen speichert – die alten Positionen werden verworfen. Das Programm realisiert das mit einem Ringspeicher – zusätzlich zu den Positionen verwalten wir einen Index, der auf den Kopf zeigt. Jede Bewegung der Schlange setzt den Index eine Position weiter, bis am Ende des Arrays der Index wieder bei 0 steht.

Eine symbolische Darstellung mit möglichen Punkten verdeutlicht dies:

snakeIdx = 0

snakePositions = { [2,2], null, null, null, null }

snakeIdx = 1

snakePositions = { [2,2], [2,3], null, null, null }

...

snakeIdx = 4

snakePositions = { [2,2], [2,3], [3,3], [3,4], [4,4] }

snakeIdx = 0

snakePositions = { [5,5], [2,3], [3,3], [3,4], [4,4] }

Alte Positionen werden überschrieben und durch neue ersetzt.

Hier ist das ganze Spiel mit den Änderungen (die fett hervorgehoben sind):

Listing 4.14    src/main/java/com/tutego/insel/array/LongerZZZZZnake.java

package com.tutego.insel.array; 



import java.awt.Point;

import java.util.Arrays;



public class LongerZZZZZnake {



public static void main( String[] args ) {

Point playerPosition = new Point( 10, 9 );

Point goldPosition = new Point( 6, 6 );

Point doorPosition = new Point( 0, 5 );

Point[] snakePositions = new Point[5];

int snakeIdx = 0;

snakePositions[ snakeIdx ] = new Point( 30, 2 );

boolean rich = false;



while ( true ) {

if ( rich && playerPosition.equals( doorPosition ) ) {

System.out.println( "Gewonnen!" );

break;

}

if ( Arrays.asList( snakePositions ).contains( playerPosition ) ) {

System.out.println( "ZZZZZZZ. Die Schlange hat dich!" );

break;

}

if ( playerPosition.equals( goldPosition ) ) {

rich = true;

goldPosition.setLocation( -1, -1 );

}



// Raster mit Figuren zeichnen



for ( int y = 0; y < 10; y++ ) {

for ( int x = 0; x < 40; x++ ) {

Point p = new Point( x, y );

if ( playerPosition.equals( p ) )

System.out.print( '&' );

else if ( Arrays.asList( snakePositions ).contains( p ) )

System.out.print( 'S' );

else if ( goldPosition.equals( p ) )

System.out.print( '$' );

else if ( doorPosition.equals( p ) )

System.out.print( '#' );

else

System.out.print( '.' );

}

System.out.println();

}



// Konsoleneingabe und Spielerposition verändern



switch ( new java.util.Scanner( System.in ).next() ) {

case "h" : playerPosition.y = Math.max( 0, playerPosition.y - 1 ); break;

case "t" : playerPosition.y = Math.min( 9, playerPosition.y + 1 ); break;

case "l" : playerPosition.x = Math.max( 0, playerPosition.x - 1 ); break;

case "r" : playerPosition.x = Math.min( 39, playerPosition.x + 1 ); break;

}



// Schlange bewegt sich in Richtung Spieler



Point snakeHead = new Point( snakePositions[snakeIdx].x,

snakePositions[snakeIdx].y );



if ( playerPosition.x < snakeHead.x )

snakeHead.x--;

else if ( playerPosition.x > snakeHead.x )

snakeHead.x++;

if ( playerPosition.y < snakeHead.y )

snakeHead.y--;

else if ( playerPosition.y > snakeHead.y )

snakeHead.y++;



snakeIdx = (snakeIdx + 1) % snakePositions.length;

snakePositions[snakeIdx] = snakeHead;

} // end while

}

}

Wer wieder etwas vorarbeiten möchte, kann Folgendes tun:

  • Ersetze das Array durch eine dynamische Datenstruktur vom Typ ArrayList<Point>.

  • Nach jedem zweiten Schritt vom Benutzer soll die Länge der Schlage um eins wachsen.

  • Wenn der Spieler ein Goldstück einsammelt, soll die Länge der Schlange um eins schrumpfen.

 


Ihre Meinung?

Wie hat Ihnen das Openbook gefallen? Wir freuen uns immer über Ihre Rückmeldung. Schreiben Sie uns gerne Ihr Feedback als E-Mail an kommunikation@rheinwerk-verlag.de

<< zurück
 Zum Rheinwerk-Shop
Zum Rheinwerk-Shop: Java ist auch eine Insel Java ist auch eine Insel

Jetzt Buch bestellen


 Buchempfehlungen
Zum Rheinwerk-Shop: Captain CiaoCiao erobert Java

Captain CiaoCiao erobert Java




Zum Rheinwerk-Shop: Java SE 9 Standard-Bibliothek

Java SE 9 Standard-Bibliothek




Zum Rheinwerk-Shop: Algorithmen in Java

Algorithmen in Java




Zum Rheinwerk-Shop: Objektorientierte Programmierung

Objektorientierte Programmierung




 Lieferung
Versandkostenfrei bestellen in Deutschland, Österreich und in die Schweiz

InfoInfo



 

 


Copyright © Rheinwerk Verlag GmbH 2021

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.

 

[Rheinwerk Computing]



Rheinwerk Verlag GmbH, Rheinwerkallee 4, 53227 Bonn, Tel.: 0228.42150.0, Fax 0228.42150.77, service@rheinwerk-verlag.de



Cookie-Einstellungen ändern