Generische Listen (List<T>) und deren Charakteristik

Datentypen und insbesondere Collections sind ein wichtiger Bestandteil des .NET-Frameworks. Diese Datenstrukturen sind extrem hilfreich für viele Dinge. Bei der „normalen“ Programmierung verwendet man einfach die Datenstruktur, die für den jeweiligen Anwendungsfall passt, aber oft wird ein sehr, sehr wichtiger Punkt außer Acht gelassen: Die Charakteristik.

Jede Datenstruktur hat bestimmte Vor- und Nachteile, die gerade bei der Entwicklung von Spielen zu extremen Geschwindigkeitsproblemen führen können.

Der Einsatz einer anderen Datenstruktur kann sinnvoll sein, dazu muss man jedoch wissen, wie diese funktioniert und was die Alternativen sind.

In diesem Artikel beschreibe ich nun die Charakteristik von generischen Listen und zeige eine Alternative auf.

Eine List<T> (wie im MSDN beschrieben) ist eine stark typisierte Liste von Objekten. Die Liste hat viele Anwendungsmöglichkeiten und wird häufig benötigt und verwendet.

Viele ihrer Methoden sind sehr praktisch und auch durchaus hilfreich während der Spieleentwicklung, aber die Bequemlichkeit erkauft man sich mit einem Preis: Es gibt einen Verwaltungsoverhead. Dieser führt dazu, daß die List<T> nicht immer die beste Wahl ist und aus Performance-Sicht gibt es mehrere bessere Möglichkeiten.

Dies soll jedoch kein grundsätzliches Abraten von der Verwendung der List<T> sein. Dieser Artikel soll einfach nur beschreiben, wie die Liste funktioniert und wo die Fallstricke sind.

Kommen wir nun zum eigentlichen Thema.

Die List<T> verwendet als Basis ein eindimensionales Array des Elementes T. T ist dabei ein beliebiger Typ des .NET-Frameworks. Ein Array ist ein Speicherbereich einer definierten Größe, der ausreichend Platz für eine bestimmte Anzahl von Objekten vorhält.

Hier ein kleines Code-Beispiel zur Verdeutlichung:

int[] myIntegers = new int[100];

In diesem Beispiel wird ein Integer-Array erzeugt, daß ausreichend Platz zur Speicherung von 100 Integer-Werten bietet. Diese liegen hintereinander im Speicher und man kann über einen Index auf die einzelnen Elemente zugreifen. Mit for-Schleifen und Iteratoren kann man ebenfalls auf eine definierte Menge von Elementen innerhalb des Arrays zugreifen.

Ein derartiges Array liegt einer jeden Liste zugrunde. Die Liste gestaltet nur den Zugriff auf dieses Array deutlich komfortabler und fehlerfreier.

Die wichtigsten und auch am häufigsten verwendeten Methoden der Liste sind:

  • der Konstruktor
  • Add
  • Remove
  • Clear

Diese Methoden und deren Abwandlungen werden am meisten verwendet und werden daher im folgenden etwas genauer beleuchtet.

Der Konstruktor existiert in einer parameterlosen Variante und in einer Variante mit einem Parameter, mit dem man eine Kapazität vorgeben kann. Bei der parameterlosen Variante wird eine Standard-Kapazität von 4 angenommen, dies bedeutet, daß ein Array mit 4 Elementen erzeugt wird. Wenn wir das so machen wie im obigen Beispiel, dann sieht dies wie folgt aus:

int[] myIntegers = new int[4];

Der Kapazitätsparameter der zweiten Variante beeinflusst nun unmittelbar die Größe des zugrundeliegenden Arrays. Übergeben wir eine 40 als Parameter, so hat das Array Platz für 40 Elemente und übergeben wir eine 1000 so hat es Platz für tausend Elemente.

Gleichzeitig wird eine Variable vom Typ Integer mit dem Wert 0 initialisiert. Diese Variable size beeinhaltet die aktuelle Größe der Liste und ist im weiteren Verlauf sehr wichtig.

Warum dies wichtig ist, erfahren wir im nächsten Abschnitt bei der Beschreibung der Add-Methode.

Die Add Methode dient dem Hinzufügen von neuen Elementen zu unserer Liste. Dabei muss das Element dem Typ T, der bei der Deklaration der Liste angegeben wurde, entsprechen. Die Add-Methode speichert dabei das übergebene Array im zugrundeliegenden Array. Nur wo? Ganz einfach im nächsten freien Element. Dies können wir mittels der Größe (die oben erläuterte Integer Variable size). Diese Variable zeigt immer auf das nächste freie Element. Mit zeigen ist hier kein Zeiger wie in C++ gemeint. Die Variable enthält einfach einen Index, der die Position im zugrundeliegenden Array angibt.

Hier kommen nun die ersten wichtigen Erkenntnisse. Die Add Methode prüft nun, ob unser zugrundeliegendes Array überhaupt noch Platz hat. Wenn nicht, dann wird neuer Platz geschaffen, um das Element ablegen zu können. Dies geschieht wie folgt:

if (size == elementArray.Length)
{
  int newSize;
  // Array vergroessern
  if (elementArray.Length == 0)
    newSize = 4;
  else
    newSize = elementArray.Length * 2;
}

Wir sehen also, wenn bisher das Array noch nicht initialisiert war, so wird es mit 4 Elementen Größe initialisiert. Wenn es bereits initialisiert war, so wird dessen Größe verdoppelt.

Wenn wir dabei nun feststellen, daß das Array vergößert werden muss, so passiert folgendes:

  • Es wird ein Array der neuen Größe angelegt
  • Die Elemente des ursprünglichen Arrays werden in das neue Array kopiert
  • Das alte Array wird gelöscht und dessen Speicher freigegeben
  • Die Variable des alten Arrays wird mit der Referenz des neuen Arrays beschrieben

Da Speicher alloziert und freigegeben wird, bekommt der Garbage-Collector zu einem späteren Zeitpunkt Arbeit.

Da jetzt sichergestellt ist, daß ausreichend Platz für unser neues Element vorhanden ist bzw. Platz geschaffen wurde, so können wir das Element im Array speichern. Zu guter letzt wird die size Variable um eins erhöht.

Eine Menge Arbeit und exakt das ist einer der Fallstricke mit einer Liste. Wenn wir es mit einer ständig wachsenden Anzahl an Elementen in einer Liste zu tun haben, so stellen wir schnell fest, daß beim Vergrößern der Liste jedesmal eine Menge Arbeit anfällt. Folgende Aufgaben sind dies im Detail:

  • Kapazität prüfen
  • ggfls. Kapazität schaffen, dabei wird Speicher angefordert und freigegeben
  • Element speichern
  • size Variable erhöhen

Kommen wir nun zur Remove Methode. Diese Methode entfernt ganz einfach Elemente aus der Liste. Dies klingt im ersten Moment einfach, ist aber unter Umständen deutlich komplizierter, wie wir im folgenden sehen werden.

Es gibt unterschiedliche Ausprägungen von Remove. Ich beschreibe hier jetzt insbesondere die RemoveAt-Methode, da diese den anderen als Grundlage dient. Bei der „normalen“ Remove-Methode wird lediglich der Index des zu entfernenden Elements ermittelt und damit dann die RemoveAt-Methode aufgerufen.

Was macht RemoveAt nun im Detail? Als erstes wird geprüft, ob der übergebene Index sich überhaupt innerhalb der Listengröße befindet und wenn nicht, wird eine Exception geworfen.

Danach wird die Größe des, also die size Variable um eins erniedrigt und jetzt kommt ein wichtiger Punkt. Da man aus einem Array nicht einfach ein Element entfernen kann, so werden alle Elemente, die sich nach dem zu löschenden Element befinden um eine Position nach vorne kopiert. Dies kann unter Umständen ein recht zeitintensives Vorhaben sein. Wenn wir ein Array mit einer Größe von 1001 Element haben und das Element an Position 1 löschen, so müssen die nachfolgenden 1000 Elemente um eine Position nach vorne kopiert werden. Dadurch entsteht im Array an letzter Stelle ein Eintrag, in dem sich noch ein altes Element befindet. Dieses wird einfach durch Aufruf des Default-Konstruktors des jeweiligen Elements überschrieben.

Eine kleine „Optimierung“ gibt es noch. Wenn das letzte Element der Liste entfernt wird, so entfällt selbstverständlich das verschieben der nachfolgenden Elemente.

Auch hier gibt es eine Menge Arbeit zu tun:

  • Element-Index ermitteln
  • size Variable erniedrigen
  • ggfls. nachfolgende Elemente verschieben
  • verwaistes Element mit Default-Wert überschreiben

Kommen wir nun vor dem abschliessenden Fazit zur Clear Methode. Die Clear-Methode ist sehr einfach zu erklären: Sie löscht alle Elemente innerhalb des Arrays und setzt die size Variable auf 0 zurück. Das Löschen von Elementen des hier eingesetzten Array.Clear ist relativ langsam.

Fazit

In diesem Artikel haben wir festgestellt, welche die wichtigsten Methoden der List<T> sind und wie diese intern funktionieren. Dabei wird schnell deutlich, daß in bestimmten Fällen eine ganze Menge Arbeit anfällt, wenn diese Methoden aufgerufen werden. Schnell wird dabei auch klar, daß dies in der Spieleentwicklung zum Problem werden kann, wenn die Listengröße zu klein gewählt wird und häufig Elemente hinzugefügt und/oder entfernt werden. Nicht nur der Garbage-Collector wird dabei bemüht, sondern auch Verwaltungsarbeit und Kopierarbeit fällt an, die unter Umständen gespart werden kann.

Es ist wichtig, daß man sich genau überlegt, wofür man eine Liste benötigt. Immer dann, wenn z.B. in der Update- oder Draw-Loop regelmäßig Objekte zu einer Liste hinzugefügt und/oder entfernt werden müssen, gibt es deutlich bessere und performantere Lösungen. Die starLiGHT.Engine bietet dafür z.B. die FastList die in einigen Fällen deutlich schneller ist.

In den nächsten Teilen dieser Artikelreihe werde ich beschreiben, wie man beispielsweise mit einem Objekt-Pool viele dieser Aufwände umgehen kann und somit z.B. die Verwaltung einer variablen Anzahl von Schüssen in einem Spiel optimieren kann.

Advertisements

Veröffentlicht am 15.10.2010, in Grundlagen, XNA. Setze ein Lesezeichen auf den Permalink. Hinterlasse einen Kommentar.

Kommentar verfassen

Trage deine Daten unten ein oder klicke ein Icon um dich einzuloggen:

WordPress.com-Logo

Du kommentierst mit Deinem WordPress.com-Konto. Abmelden / Ändern )

Twitter-Bild

Du kommentierst mit Deinem Twitter-Konto. Abmelden / Ändern )

Facebook-Foto

Du kommentierst mit Deinem Facebook-Konto. Abmelden / Ändern )

Google+ Foto

Du kommentierst mit Deinem Google+-Konto. Abmelden / Ändern )

Verbinde mit %s

%d Bloggern gefällt das: