Programmiererpraxis

2015-05-22

.NET-Collections: Erste Schritte mit C5

Ted Neward Ich muss ein Geständnis ablegen.

Am Tag arbeite ich als friedfertiger .NET-Entwickler für das Beratungsunternehmen Neudesic LLC. Aber nachts, wenn meine Frau und meine Söhne schlafen, stehle ich mich aus dem Haus, den Laptop in der Hand, und mache mich auf den Weg zu meinem geheimen Unterschlupf (einem Denny's-Restaurant in der 148sten), und schreibe ... Java-Code.

Ja, ich führe ein Doppelleben als .NET- und Java-Entwickler – oder genauer gesagt als Java Virtual Machine-Entwickler (JVM). Ein interessanter Nebeneffekt dieses dualen Lebensstils sind meine Einblicke in Bereiche, in denen Microsoft .NET Framework über hervorragende Konzepte verfügt, die in die JVM zurückgeführt werden können. So geschah es zum Beispiel mit den benutzerdefinierten Attributen, die in Java5 (ungefähr 2005) unter dem Namen „Anmerkungen“ in die JVM übernommen wurden. Aber auch die umgekehrte Richtung trifft zu: In der JVM funktionieren tatsächlich einige Aspekte ordnungsgemäß, die in der CLR und der NET-Basisklassenbibliothek nicht – oder nicht so ganz gut, wenn Sie es lieber so ausdrücken möchten – funktionieren. Ein solcher Bereich befindet sich im Kern der .NET-Basisklassenbibliothek: Collections.

Collections: Eine kritische Besprechung

Bei .NET-Collections besteht ein Fehler darin, dass das Basisklassenbibliotheks-Team unsinnige Collections zweimal schreiben musste: einmal für die .NET Framework 1.0/1.1-Version, bevor Generika verfügbar waren, und noch einmal für .NET Framework 2.0, nachdem Generika Bestandteil der CLR waren, denn Collections ohne stark typisierte Versionen sind einfach irgendwie unsinnig. Das bedeutet automatisch, dass einer der beiden Codes dazu bestimmt war, zugunsten beliebiger Verbesserungen oder Erweiterungen der Bibliothek zu verfallen. (Java hat sich vor diesem speziellen Problem gedrückt, indem die nicht generischen Versionen durch generische „ersetzt“ wurden. Dies war nur durch die Methode möglich, wie Java Generika behandelt, worauf ich in diesem Artikel nicht eingehe.) Und abgesehen von den Erweiterungen, die mit LINQ in Visual Studio 2008 und C# 3.0 eingeführt wurden, wurde der Collectionsbibliothek nach der 2.0-Version nie besonders viel Beachtung geschenkt. Die 2.0-Version selbst implementierte mehr oder weniger nur die System.Collections-Klassen in einen neuen Namespace („System.Collections.Generic“ oder SCG) mit stark typisierten Versionen.

Was jedoch wichtiger ist, der Schwerpunkt beim Entwerfen der .NET-Collections lag anscheinend mehr darauf, etwas Praktisches und Nützliches als Teil der 1.0-Version zu veröffentlichen, anstatt intensiv über das Design von Collections und deren Erweiterbarkeit nachzudenken. Dieser Bereich in .NET Framework stellte tatsächlich (und vermutlich unbeabsichtigt) einen Parallelfall zur Java-Welt dar. Java 1.0 enthielt bei Auslieferung eine Reihe grundlegender, zweckmäßiger Collections. Es gab allerdings ein paar Entwurfsfehler (der haarsträubendste davon war die Entscheidung, dass die Stack-Klasse, eine Last-in-First-out-Collection, direkt die Vector-Klasse erweiterte, die im Grunde eine „ArrayList“ war). Nach der Einführung von Java 1.1 arbeiteten einige Entwickler bei Sun Microsystems intensiv daran, die Collectionsklassen, die als die „Java Collections“ bekannt wurden, neu zu schreiben und als Teil von Java 1.2 auszuliefern.

Eine Überholung der Collectionsklassen in .NET Framework ist auf jeden Fall überfällig, am besten so, dass zumindest eine weitgehende Kompatibilität mit den vorhandenen SCG-Klassen gewährleistet ist. Erfreulicherweise haben Forscher an der dänischen IT-Universität in Kopenhagen eine Bibliothek erstellt, die ein würdiger Nachfolger und eine Ergänzung der SCG-Klassen ist: die Copenhagen Comprehensive Collection Classes for C# oder kurz C5.

C5-Logistik

Zunächst einmal finden Sie C5 im Web unter „itu.dk/research/c5“, wenn Sie den Versionsverlauf lesen möchten oder sich für den Link zu einem Buch (PDF) über C5 interessieren, wobei sich das Buch allerdings auf eine frühere Version bezieht. Sie können C5 auch über NuGet erhalten, indem Sie den (inzwischen universellen) Install-Package-Befehl verwenden und „Install-Package C5“ eingeben. C5 wurde so geschrieben, dass es für Visual Studio und Mono verfügbar ist. Wenn NuGet das Paket installiert, werden daher sowohl Verweise auf die C5.dll-Assembly als auch auf die C5Mono.dll-Assembly hinzugefügt. Die nicht gewünschte Version der beiden ist überzählig und kann gelöscht werden. Ich habe ein Visual C#-Testprojekt erstellt und diesem C5 hinzugefügt, um die C5-Collections einer Reihe von Erkundungstests zu unterziehen. Darüber hinaus besteht die einzige beachtenswerte Codeänderung in zwei using-Anweisungen, die die C5-Dokumentation auch voraussetzt:

using SCG = System.Collections.Generic;
using C5;

Der Grund für den Alias ist einfach: Einige Schnittstellen und Klassen, die in der SCG-Version denselben Namen haben, werden in C5 „neu implementiert“. Somit sind Aliase für das alte Material für uns verfügbar, aber mit einem sehr kurzen Präfix. Ein Beispiel: Die C5-Version lautet „IList<T>“, wohingegen die klassische SCG-Version „SCG.IList<T>“ ist.

Nebenbei, die Antwort auf eventuelle Fragen von Anwälten lautet, dass C5 eine Open Source-Bibliothek unter einer MIT-Lizenz ist. Sie haben daher viel umfangreichere Möglichkeiten, einige der C5-Klassen zu ändern oder zu erweitern, als dies bei einer GNU General Public-Lizenz (GPL) oder GNU Lesser General Public-Lizenz (LGPL) der Fall wäre.

Übersicht über das C5-Design

Der C5-Designansatz ist dem SCG-Stil insoweit ähnlich, dass Collections in zwei „Schichten“ unterteilt werden: eine Schnittstellenschicht, die die Schnittstelle und das erwartete Verhalten einer gegebenen Collection beschreibt, und eine Implementierungsschicht, die den eigentlichen Unterstützungscode für die gewünschte Schnittstelle oder die gewünschten Schnittstellen bereitstellt. Die SCG-Klassen nähern sich diesem Konzept, führen es aber in manchen Fällen nicht besonders gut zu Ende. Zum Beispiel fehlt die Flexibilität bei der Implementierung von „SortedSet<T>“ (d. h., die Wahl zwischen arraybasiert, auf Basis einer verknüpften Liste oder hashbasiert, wobei jede dieser Optionen unterschiedliche Merkmale hinsichtlich der Leistung von Einfügung, Traversierung usw. aufweist). In einigen Fällen mangelt es den SCG-Klassen einfach an bestimmten Collectionstypen. Es fehlt zum Beispiel eine zirkuläre Warteschlange, in der die Iteration wieder an den Anfang der Warteschlange wechselt, wenn das letzte Element in der Warteschlange durchlaufen wurde, oder eine einfache „Behälter“-Collection, die keine Funktionalität bietet, außer Elemente zu enthalten und damit unnötigen Aufwand bei Sortierungen, Indizierungen usw. zu vermeiden.

Zugegeben, für den durchschnittlichen .NET-Entwickler scheint das kein großer Verlust zu sein. Aber bei vielen Anwendungen rückt die Leistung immer mehr in den Mittelpunkt, und somit wird es zunehmend wichtiger, die richtige Collectionsklasse auszuwählen, die für das vorliegende Problem geeignet ist. Ist es eine Collection, die einmal erstellt und häufig durchlaufen wird? Oder ist es eine Collection, die häufig hinzugefügt oder entfernt, aber selten durchlaufen wird? Wenn sich diese Collection im Kern eines Anwendungsfeatures (oder der App selbst) befindet, kann der Unterschied zwischen diesen zwei Collections den Unterschied zwischen „Toll, diese App ist super!“ oder „Nun, die Benutzer fanden es gut, nur zu langsam“ ausmachen.

Eines der Kernprinzipien von C5 indes ist, dass die Entwickler für Schnittstellen, nicht für Implementierungen codieren. C5 bietet daher mehr als ein Dutzend verschiedene Schnittstellen, die beschreiben, was die zugrunde liegende Collection bereitstellen muss. „ICollection<T>“ ist die Basis für alle und gewährleistet grundlegendes Collectionsverhalten. Es folgen „IList<T>“, „IIndexed<T>“, „ISorted<T>“ und „ISequenced<T>“, um nur einige zu nennen. Die folgende vollständige Liste enthält die Schnittstellen, ihre Beziehungen zu anderen Schnittstellen und ihre Garantien:

„SCG.IEnumerable<T>“ kann ihre Elemente aufzählen lassen. Alle Collections und Wörterbücher sind aufzählbar.
„IDirectedEnumerable<T>“ ist eine Aufzählung, die umgekehrt werden kann, mit dem Ergebnis einer Rückwärtsaufzählung, die ihre Elemente in umgekehrter Reihenfolge aufzählt.
„ICollectionValue<T>“ ist ein Auflistungswert. Er unterstützt keine Änderung, ist aufzählbar, kennt die Anzahl seiner Elemente und kann diese in ein Array kopieren.
„IDirectedCollectionValue<T>“ ist ein Auflistungswert, der in einen Rückwärtsauflistungswert umgekehrt werden kann.
„IExtensible<T>“ ist eine Collection, zu der Elemente hinzugefügt werden können.
„IPriorityQueue<T>“ ist erweiterbar. Die enthaltenen Mindest- und Höchstwerte können effizient gefunden (und entfernt) werden.
„ICollection<T>“ ist erweiterbar. Es können auch Elemente entfernt werden.
„ISequenced<T>“ ist eine Collection, deren Elemente in einer bestimmten Reihenfolge auftreten (entweder von der Einfügungsreihenfolge oder von der Sortierung der Elemente bestimmt).
„IIndexed<T>“ ist eine sequenzierte Collection, auf deren Elemente über den Index zugegriffen werden kann.
„ISorted<T>“ ist eine sequenzierte Collection, deren Elemente in aufsteigender Reihenfolge auftreten. Die Reihenfolge wird durch Vergleiche der Elemente bestimmt. Die Collection kann effizient das Vorgänger- oder Nachfolgerelement eines gegebenen Elements in der Collection ermitteln.
„IIndexedSorted<T>“ ist eine indizierte und sortierte Collection. Sie kann effizient bestimmen, wie viele Elemente größer als oder gleich groß wie ein gegebenes Element „x“ sind.
„IPersistentSorted<T>“ ist eine sortierte Collection, von der effizient eine Momentaufnahme erstellt werden kann, d. h. eine schreibgeschützte Kopie, auf die Aktualisierungen der ursprünglichen Collection keine Auswirkungen haben.
„IQueue<T>“ ist eine FIFO-Warteschlange (First In First Out), die außerdem eine Indizierung unterstützt.
„IStack<T>“ ist ein LIFO-Stapel (Last In First Out).
„IList<T>“ ist eine indizierte und daher sequenzierte Collection, in der die Reihenfolge der Elemente von Einfügungen und Löschungen bestimmt wird. Sie wird von „SCG.IList<T>“ abgeleitet.

C5 bietet viele Implementierungen, darunter zirkuläre Warteschlangen, sowohl arraybasierte Listen als auch Listen auf Basis verknüpfter Listen, aber auch Arraylisten mit Hash und verknüpfte Listen mit Hash, umschlossene Arrays, sortierte Arrays, strukturbasierte Sets und Behälter und mehr.

C5-Codierstil

Glücklicherweise erfordert C5 keine wesentliche Änderung des Codierstils. Und noch besser, C5 unterstützt alle LINQ-Vorgänge (da es auf den SCG-Schnittstellen aufbaut, die die LINQ-Erweiterungsmethoden bestimmen). In einigen Fällen können Sie daher zur Erstellungszeit eine C5-Collection einfügen, ohne etwas von dem Code zu ändern, der die Collection umgibt. Abbildung 1 enthält dafür ein Beispiel.

Abbildung 1: Erste Schritte mit C5

// These are C5 IList and ArrayList, not SCG
IList<String> names = new ArrayList<String>();
names.AddAll(new String[] { "Hoover", "Roosevelt", "Truman",
  "Eisenhower", "Kennedy" });
// Print list:
Assert.AreEqual("[ 0:Hoover, 1:Roosevelt, 2:Truman, 3:Eisenhower," +
  " 4:Kennedy ]", names.ToString());
// Print item 1 ("Roosevelt") in the list
Assert.AreEqual("Roosevelt", names[1]);
Console.WriteLine(names[1]);
// Create a list view comprising post-WW2 presidents
IList<String> postWWII = names.View(2, 3);
// Print item 2 ("Kennedy") in the view
Assert.AreEqual("Kennedy", postWWII[2]);
// Enumerate and print the list view in reverse chronological order
Assert.AreEqual("{ Kennedy, Eisenhower, Truman }",
  postWWII.Backwards().ToString());

Diese Beispiele sind sogar ohne einen einzigen Blick in die C5-Dokumentation recht einfach zu verstehen.

C5 im Vergleich zu Implementierungen von SCG-Collections

Dieser Artikel über C5 enthält nur die Spitze des Eisbergs. Im nächsten Artikel befasse ich mich mit ein paar praktischen Beispielen zur Verwendung von C5 anstelle von Implementierungen von SCG-Collections und beschreibe einige der Vorteile dabei. Nutzen Sie die Zeit bis dahin: Installieren Sie C5 mit NuGet, und legen Sie los. Es gibt viel Interessantes zu entdecken.

Viel Spaß beim Programmieren!

Ted Neward ist Berater für Softwarearchitektur bei Neudesic LLC. Er hat mehr als 100 Artikel geschrieben und als Autor und Mitautor ein Dutzend Bücher verfasst, darunter „Professional F# 2.0“ (Wrox 2010). Er ist F#-MVP, ein bekannter Experte für Java, und er hält auf Java- und .NET-Konferenzen in der ganzen Welt Vorträge. Neward berät und hilft regelmäßig. Wenn Sie Interesse an seiner Mitarbeit in Ihrem Team haben, können Sie ihn unter ted@tedneward.com oder Ted.Neward@neudesic.com erreichen. Unter blogs.tedneward.com können Sie seinen Blog lesen, und Sie können Neward unter twitter.com/tedneward auf Twitter folgen.

Unser Dank gilt dem folgenden technischen Experten für die Durchsicht dieses Artikels: Immo Landwerth

Freigeben über