von Roman Seibold

Beitrag als PDF

 

Es ist oft so, dass man gewisse Erkenntnisse zu einem Thema genau dann erlangt, wenn man eigentlich zu einem ganz anderen Sachverhalt etwas erfahren wollte. Genau dies passierte mir, als ich die in Java 6 neu hinzugekommene copyOf-Methode für Arrays ausprobierte und mit einem weiteren Mosaiksteinchen hinsichtlich Java 5 Generics "belohnt" wurde.
Ausgangspunkt war eine zu Spiel- und Testzwecken erstellte Klasse, die eine sortierte Zahlenfolge intern mit Arrays implementiert. Mit Arrays deshalb, weil ich ja die copyOf- Methode der Klasse java.util.Arrays ausprobieren wollte. Hier die Testklasse in ihrer ganzen Schönheit:

import java.util.Arrays;

public class SortedArray
{ 
  private int[] array;  

  public SortedArray()  
  {    
    this.array = new int[0];  
  }  

  public void add(int i)  
  {    
    int index = Arrays.binarySearch(this.array, i);    

    if (index < 0)    
    {    
      index = -(index + 1);

      int[] headArray = 
        Arrays.copyOfRange(this.array, 0, index);
      int[] tailArray = 
        Arrays.copyOfRange(this.array, index, 
                             this.array.length);

      this.array = new int[this.array.length + 1];

      System.arraycopy(headArray, 
                         0, this.array, 
                         0, headArray.length);
      System.arraycopy(tailArray, 
                         0, this.array, 
                         index + 1, tailArray.length);

      this.array[index] = i;
    }
  }

  public int[] toArray()
  {
    return Arrays.copyOf(this.array, this.array.length);
  }

  @Override
  public String toString()
  {
    return Arrays.toString(this.array);
  }
}

Das meiste der Implementierung spricht entweder für sich selbst, oder ist sogar für das weitere Verständnis unnötig. Erwähnenswert vielleicht der eigentliche Zweck der Übung, nämlich dass ein intern zunächst minimales Array (Größe 0) stetig um eine weitere hinzugefügte Zahl wächst und diese Zahl wird gleich an der richtigen Stelle einsortiert. Dazu wird mit der Binärsuche die Einfügestelle bestimmt, ein linkes und rechtes Teilarrayauskopiert und das neue Array so wieder zusammengefügt.
Die Implementierung lässt mehrfaches Einfügen des selben Wertes nicht zu.

Die Zeile mit -(index+1) habe ich absichtlich nicht kommentiert, damit ich mich in 3 Wochen wieder von neuem fragen kann, was ich mir dabei eigentlich gedacht hatte. Der interessierte Leser findet aber Hinweise in der Dokumentation der binarySearch- Methode. Ich glaube, ein negativer Wert hatte irgendwas mit einer potentiellen Einfügeposition zu tun.

Als dieser Code geschrieben war und zu meiner Zufriedenheit funktionierte, begann sich die Neugier zu regen: das müsste sich doch allgemeingültiger formulieren lassen. Wohlmöglich mit Generics! Für alles, was sich vergleichen und somit sortieren lässt. Gewünscht, getan. 

 

1. Schritt. Einführung einer Typ-Variablen.

Alle Vorkommen des bisherigen Inhaltstyps "int" werden durch eine Typ-Variable T ersetzt. Das sieht dann grob so aus:

public class SortedArray<T>
{
  private T[] array;

  public SortedArray()
  {
    this.array = new T[0];
  }

  public void add(T i)
  {
    int index = Arrays.binarySearch(this.array, i);
    if (index < 0)
    {
      index = -(index + 1);

      T[] headArray = 
        Arrays.copyOfRange(this.array, 0, index);
      T[] tailArray = 
        Arrays.copyOfRange(this.array, index, 
                             this.array.length);

      this.array = new T[this.array.length + 1];

      System.arraycopy(headArray, 
                         0, this.array, 
                         0, headArray.length);
      System.arraycopy(tailArray, 
                         0, this.array, 
                         index + 1, tailArray.length);

      this.array[index] = i;
    }
  }

  public T[] toArray()
  {
    return Arrays.copyOf(this.array, this.array.length);
  }

  //...
}

Wenn Sie das so mit Java ausprobieren wollen, werden Sie bemerken, dass die Zeilen mit new T[] ein Problem darstellen. Mein erster Ansatz war der

 

2. Schritt: Minimierung der Problemstelle

Eigentlich keine Lösung, aber Verlagerung. Alle Zeilen, die ein Compile-Problem darstellen, in eine Hilfsmethode verlagern. Also dergestalt:

private T[] createArray(int size)
{
  return new T[size];
}

und alle Aufrufe schnell so ersetzt:

this.array = this.createArray(this.array.length + 1);

Das hilft zwar nicht, man fühlt sich danach aber besser, weil man etwas zur Minimierung der Fehleranzahl getan hat. Aktionismus muss ja nicht immer etwas schlechtes sein.

 

3. Schritt: Array-Erzeugung

Wie aber erzeugt man nun das typisierte Array? Die Antwort ist so verblüffend wie enttäuschend: gar nicht. Das geht schlichtweg mit den Sprachmitteln von Java 5 nicht. Die Lösung sieht in ihrer vollen Schrecklichkeit so aus:

private T[] createArray(int size)
{
  return (T[]) new Object[size];
}

Was heißt das nun?

Die Java 5 Generics bestehen ja im Grunde genommen nur aus einem Compiler-Feature. Zur Compile-Zeit werden eben die konkret gewählten Typ-Parameter mit den gegebenen Typvariablen verglichen, auf gewisse Einschränkungen geprüft und dann sukzessive, nach bestandenen Prüfungen, wieder entfernt. Die Spezifikation spricht hier von Auslöschung,"type erasure". Also werden alle typisierten Stellen wieder auf den schon von Java-Versionen vor Java 5 bekannten Code gebracht.

Dass der new-Operator, der eben zur Laufzeit Objekte erzeugt und ein Phänomen, das nur zur Compile-Zeit existiert, miteinander Probleme haben, liegt so betrachtet eigentlich auf der Hand. Daher behilft man sich lapidar damit, einfach das hinzuschreiben, was nachher sowieso dastehen wird, nämlich new Object[]. Zudem versichert man dem Compiler, dass man schon weiß, was man tut. Dies drückt der Java-Programmierer ja gerne durch einen Cast aus, hier also (T[]).

Die Macher von Java haben sich hierzu schon Gedanken gemacht und sind eigentlich soweit übereingekommen, dass dies unschöner Code sei und dass man das selber zu Hause nicht nachmachen soll. Deswegen haben sie dieses Stück Code ganz tief in die Klasse ArrayList gesteckt, sozusagen als Tresor für schlechtes Java, und die Java-Entwickler dieser Welt seien angehalten für typisierte Arrays immer die ArrayList zu verwenden. Dort ist das Übel dann gekapselt und fertig.

Hier ein Link auf eine typische Diskussion. Dort hat auch ein gewisser C. Scott Ananian erklärende Beiträge verfasst. Ein Auszug aus dem erklärenden Statement (siehe courses.csail.mit.edu/6.170/old-www/2006-Spring/forum/index.php%3Ftopic=324.msg1131.html ):

"Please avoid the Object[] -> T[] cast at all costs in your code. The reason why array variance was dropped is that you can do the same thing with (Array)List<T>, with almost identical performance. Arrays of generics don't offer such a compelling benefit over List of generics that they merited the risk to the release. If you remember, I asked Gilad when he was here if he thought T[] would ever be supported, and he said no -- it just doesn't fundamentally do anything you couldn't otherwise do.

If you're curious, you can look at the implementation of ArrayList<T> in Sun's library, where you'll indeed find an Object[] -> T[] cast at the heart of it. You can think of using ArrayList<T> as a means to wrap this fundamental ugliness with an interface that has been proven type-safe, so that you don't have to do the ugly thing in your own code."

 

4. Schritt: Aufräumarbeiten

Die Stelle mit (T[]) new Object[] macht uns immer noch Ärger, weil Java hier, nichtzu unrecht, ein potentielles Problem sieht.

Das lässt sich mit einem eleganten @SuppressWarnings("unchecked") vor der Hilfsmethode beheben. Auch damit, analog zum oben gewählten Cast, macht der Java-Profi dem mosernden Compiler klar, dass er hier alles unter Kontrolle habe und der Compiler seine kleinen Nörgeleien bitte einstellen solle.

 

5. Schritt: Oops - noch mehr Aufräumarbeiten

Ein Problem habe ich aber noch in meinem Enthusiasmus für Generics übersehen. Wenn man den entstandenen Code ausprobiert und für T einen Typ einsetzt, der sich nicht so einfach sortieren lässt, also in Java gesprochen, nicht Comparable implementiert, wird man Schiffbruch erleiden. Dieser manifestiert sich in Form einer handfesten Exception, natürlich zur Laufzeit.

java.lang.ClassCastException: 
  XXX cannot be cast to java.lang.Comparable
        at java.util.Arrays.binarySearch0

Also muss man noch klären, dass für den Typ T nur Typen in Frage kommen, die das Interface Comparable in ihren Reihen haben. Da Comparable aber seit Java 5 als Comparable<T> deklariert ist, sieht unsere Klassendeklaration nun – etwas gewöhnungsbedürftig – so aus:

public class SortedArray<T extends Comparable<T>>
{
  ...
}

Das konkrete T muss also, mehr oder weniger, mit sich selbst vergleichbar sein. Genauer gesagt muss T typkompatibel zu einem anderen Typ sein, der den Vergleichsmechanismus für T definiert. Verwirrend. Ist aber so.

Nachdem ich nun erfolgreich die copyOf-Methode, die Einführung einer Typvariablen, die Diskussion um generische Arrays, das Ausblenden von potentiellen Fehlerquellen mit SupressWarnings und die Vergleichbarkeit eines generischen Typs mit sich selber oder soähnlich in einem Zug erleben durfte, dachte ich mir, ich teile meine Erfahrungen mit Ihnen. Vielleicht hat es Ihnen ja was gebracht oder auch nur ein wenig Spaß gemacht, hier ein wenig zu schmökern.

In diesem Sinne wünsche ich Ihnen alles Gute.

 

Haftungsausschluss:

Die Artikel und Beiträge wurden mit großer Sorgfalt hergestellt und geprüft. Trotzdem können Fehler nicht vollkommen ausgeschlossen werden. aformatik kann für fehlerhafte Angaben und deren Folgen weder eine juristische Verantwortung noch irgendeine Haftung übernehmen. Die in den Beiträgen erwähnten Soft- und Hardwarebezeichnungen sind in den meisten Fällen auch eingetragene Marken und unterliegen als solche den gesetzlichen Bestimmungen.