Collections -> Ansammlungen von Werten. Fast alle Programmiersprachen kennen derartige Konstrukte, um Operationen mit mehreren gleichartigen Werten zu vereinfachen. Für die meisten Sprachen scheint das Array als technisch einfachste und schnellste Datenstruktur das Mittel der Wahl zu sein. Dies mag einer der Gründe sein, warum es meist auch die einzige Datenstruktur ist, die mit syntaktischem Zucker direkt auf dem Sprachlevel supported wird.
Allerdings wissen die meisten Entwickler auch, dass Arrays nicht die einzigen Collections sind. Es gibt neben Arrays noch Sequenzen, Mengen und natürlich auch Map-Strukturen, die bestimmten Keys entsprechende Values zuordnen, und all diese Typen meist in zahlreichen Ausprägungen . Viele moderne Sprachen bilden für diese unterschiedlichen Strukturen bereits Typen an, die drei Hauptkategorien bilden:
- Sequence[A] (Seq[A], List[A](Java-Kuriosum) )
- Abfolge von Elementen. Mehrfachvorkommen ist möglich, da primäre Eigenschaft die "Reihenfolge" ist
- Die bekanntesten Vertreter dieser Art sind das Array, der Vektor (Array mit automatischer Vergrößerung), die Single-Linked-List und die Double-Linked List.
- Es lässt sich für Sequenzen anhand der Reihenfolge stets ein indexbasierter Zugriff implementieren. Allerdings ist dieser nur bei Arrays effizient und sollte bei anderen Strukturen vermieden werden. Besser sind stets generische Iterationsmechanismen
- Set[A]
- Enthält (mathematische) Mengen, in denen jedes Element nur einmal vorkommen kann.
- Sets können wie Sequenzen iteriert werden, jedoch ist die Reihenfolge nur selten deterministisch und kann deshalb unter keinen Umständen vorrausgesetzt werden. Aus diesen Gründen bieten Sets auch, obwohl theoretisch möglich, keinen Indexzugriff an.
- Die Schnittstellen von Sequenzen und Sets sind meist recht ähnlich. Der Hauptunterschied liegt hier in der Verwendung.
- Map[A,B]
- Dient dem Mapping von Key auf Value. Keys müssen unique sein, für Values gilt diese Beschränkung hingegen nicht.
- Am häufigsten werden hashcode- oder baumbasierte Strukturen zum Mappen eingesetzt.
- Ähnlich wie Sets lassen sich auch Maps nur meist nur nicht-deterministisch iterieren. Anstatt über einzelne Elemente iteriert man hier über (Key,Value)-Paare (auch Tupel genannt).
Iterable[A] (auch: Traversable, Collection, ..)
Enthält die Basisstruktur, um über 1..n Elemente aus einer Folge, Menge, Folge von Schlüssel-Wert-Paaren zu iterieren. Zusätzlich werden oft noch Funktionen angeboten, die sich direkt durch die Eigenschaft der Iterierbarkeit implementieren lassen (isEmpty-Prüfung, Filtern von Werten, Umwandeln der Werte, ...)
1. Anforderungen an die Sprache
Collections sind grundsätzlich ein Feature, dass für fast alle Sprachen elementar sein sollte. Es sollte aber nicht so elementar sein, dass es auf dem Sprachlevel implementiert wird. Syntaktischer Zucker für einige der Strukturen ist nicht sinnvoll oder wünschenswert. Dies führt meist zu einer bevorzugten Verwendung derselben, obwohl es grundsätzlich nicht die "richtige" Collection für jeden Anwendungsfall gibt. Außerdem schränkt es die Flexibilität der Sprache ein und macht den Zugriff auf unterschiedliche Arten von Collections uneinheitlich!
Collections sollten immer als zum Grundumfang der Sprache gehörende API's realisiert werden, die sich an der obigen Dreiteilung orientiert. Es gibt keinen Grund, sie wirklich auf das Sprachlevel zu packen. Wenn eine native und einfache Verwendung von Collections ermöglicht werden soll, dann muss die Sprache Operatorenüberladung unterstützen. Nur mit Operatoren lassen sich Collections wirklich in eine Sprache auf dem richtigen Level integrieren.
Damit Collections sinnvoll in einer statisch typisierten Sprache eingesetzt werden können, muss die Sprache Typparameter (Generics) anbieten. Wie oben aufgezeigt verwenden Collections immer denselben Typ bzw. sollten es zumindest. Falls die Sprache nun statisch typisiert ist und Typparameter nicht zur Verfügung stehen... muss die Typsicherheit durch casts bei jedem Zugriff sichergestellt werden. Das ist absurd, da diese Konstrukte aufwändig sind, aber keine Typsicherheit bieten! Populäre Beispiele hierfür sind Java 1.4 und .NET 1.0. Hier ist man meist besser beraten, mit Arrays zu arbeiten (die hier auch keine Collections sind?),
Collections sind einer der Hauptgründe, wegen denen jede statisch typisierte Sprache Typparameter anbieten muss! Sonst ist ihr Typsystem an den entscheidenden Stellen so schwach, dass man besser darauf verzichtet und einfach dynamisch typisiert.
Man kann sogar noch weitergehen: Dies ist einer der Hauptgründe, wegen denen eine Sprache, die statisch typisiert ist, von vornherein Typparameter in ihrem Sprachumfang enthalten muss! Ansonsten werden sie zwangsläufig später aus den genannten Gründen "nachgerüstet", können sich aber nicht mehr so gut in die Sprache integrieren, als wenn sie von vorn herein da gewesen wären. (-> JDK 1.5). Dazu werde ich noch mal einen eigenen Beitrag verfassen...
2. Ünveränderlichkeit
Ein weiteres entscheidendes Kriterium von Collections ist die Unveränderlichkeit: Collections stellen immer Werte dar. Werte sind aber per Definition unveränderlich. Will ich einen Wert verändern, dann muss ich stattdessen durch eine Operation einen neuen Wert erstellen. Wenn ich z.B. zwei Collections verbinde sollte das Ergebnis nicht in einer der beiden Collections gespeichert werden, sondern eine neue Collection ergeben.
Diese Eigenschaft lässt sich aber nur dann sicherstellen, wenn Collections grundsätzlich unveränderlich sind. Im kleinen Rahmen hat sich diese Erkenntnis bereits bei vielen Sprachdesignern durchgesetzt, die aus den Fehlern von C gelernt haben. So sind Strings in den meisten modernen Sprachen bereits unveränderlich. Das ist einzige komische an der Sache ist nur, dass die Sprachdesigner in dem Zug nicht auch daran gedacht haben, Strings als Collections (Seq[Char]) zu deklarieren und das Konzept gleich für alle Collections zu übernehmen!
Die fehlende Unveränderlichkeit ist nun einer der Hauptschwachpunkte fast aller Collection-Libraries:
Alle Standardcollections basieren meist auf Arrays. Arrays sind aber schon per Definition mutable Datenstrukturen, die sich nur begrenzt für immutable Implementatierungen eignen.
Einige imperativen Sprachen verzichten zudem auf die nötige Zweiteilung in mutable und immutable Collections auf der Interface-Ebene: Java z.B. kennt nicht einmal immutable Interfaces für seine Collections. Stattdessen werden Exceptions geworfen, wenn eine als unveränderlich gekennzeichnete Collection verändert werden soll. Und wieder mal ein Fall, in dem das Typsystem von Java zu schwach ist..
Die Stärke der immutable Collections liegt darin, dass sie threadsicher, zwischen beliebig vielen Funktionen ausstauschbar und leichter in einem Ablauf nachzuvollziehen sind. Dadurch können sie sicher an allen Schnittstellen verwendet werden, ohne dass es zu versehentlichen Veränderungen kommen kann. Diese Vorteile sind für Code, der leicht verständlich und bereits zur Compile-Zeit verständlich sein soll, entscheidend.
Mutable Collections haben hingegen auch Vorteile, aber viel weniger als oft postuliert wird. Wenn Werte häufig verändert werden sollen und die Collection zudem noch sehr groß sind, sind mutable Datenstrukturen meist schneller. Da sie aber keine der bei immutable Collections genannten Vorteile haben, müssen sie in sehr begrenzten Scopes gehalten werden. Üblicherweise wird man mutable Collections im inneren (privaten) Scope eines Typs "einsperren" müssen, wenn man wirklich sicher entwickeln möchte. Ihr Anwendungsfall ist also grundsätzlich ein spezialisierter. Immutable Collections hingegen eignen sich generisch für alle Arten von Problemen, weshalb sie grundsätzlich immer vorzuziehen sind.
3. Threadsicherheit ?
Eine weitere oft genannte wünschenswerte Eigenschaft ist, das Collections threadsicher sein sollten. Dieses Forderung ist aus der imperativen Entwicklung heraus entstanden und .. vollkommener Blödsinn!
Threadsicherheit erreicht man über immutable Collections.
Will man mutable Collections synchronisieren, muss man manuell alle Blöcke synchronisieren, in denen auf die Collection zugegriffen wird. Es reicht nie, nur die Collection zu synchronisieren, da sich weder die Iteration noch der Indexzugriff sauber auf dem Collection-Niveau abbilden lässt! Ebensowenig das gleichzeitige Durchführen mehrere Operationen, z.B. Lesen und Schreiben. Ergo muss man, schon allein aus Effizienzgründen, ohnehin fast immer manuell synchronisieren!
Deshalb: Vergesst threadsichere Collections!
Zusammenfassung
- Collections sollten eine saubere Klassenhierarchie anhand der obigen "Dreiteilung" aufweisen. (Keine Sonderregeln, auch nicht für Arrays)
- Realisierung sollte als API und nicht in der Sprache erfolgen. Collections müssen erweiterbar sein!
- Sprache: Operatorenüberladung sollte möglich sein
- Statische Sprache: Typparameter müssen möglich sein (und auch für Arrays gelten)
- Die Sprache sollte sowohl mutable als auch immutable Collections anbieten.
- Threadsicherheit ist masslos überschätzt und muss in Collections nicht berücksichtigt werden. (Erklärung s. oben)
Links
Eine der schönsten und vollständigsten Collections-Libraries hat meiner Meinung nach Scala, deshalb hier ein Link auf das sehr gute Tutorial zu der Collection-Hierarchie. Auch für Nicht-Scala-Fans empfehlenswert!
Scala Collections Overview
No comments:
Post a Comment