Programmierung und Speicherstrukturen
Da ich doch öfters schon mal feststellen musste, dass angehende Informatiker oder auch Informatiker recht wenig Wissen über Collections und Datensammlungen haben, möchte ich hier mal versuchen meine Erfahrungen mit Collections in der Programmiersprache Java kund zu tun. Denn die Informatik beschäftigt sich nun mal sehr stark mit der Haltung und auch der Auswertung von Datenmengen. Damit dies hochperformant gesehen kann, sollte man sich in den verschiedenen Arten der Datenstrukturen doch schon auskennen.
Was sind Collections?
Collections sind in der Programmierung Strukturen zum organisieren von Daten. Das heißt um Daten in dem Arbeitsspeicher zu halten, oder zu bearbeiten, oder oder oder. Möglichkeiten der Datennutzung gibt es ja viele. Genauso gibt es auch viele Strategien zum organisieren der Daten innerhalb der Collection. Jede Strategie hat natürlich ihre Vor- und Nachteile. Jedoch möchte man nach Möglichkeit nur die Vorteile nutzen, um ein Programm möglichst leistungsfähig umzusetzen. Einen guten Überblick über die verschiedenen Arten von Collections im Java-Framework gibt die Java-Dokumentation her[1]. Einzuteilen sind diese Strukturen in
- Array
- List
- Vector
- Queue
- Stack
- Set
- Map
Ich werde nun versuchen die einzelnen Arten der Datensammlungen anzureißen und einen Überblick über diese zu geben.
Array
Das Array oder auch Feld, ist in der Programmierung wohl eines der bekanntesten Vertreter der Datenstrukturen. Es zeichnet sich dadurch aus, dass es sehr kompakt ist. Die Zugriffe auf die einzelnen Elemente erfolgt direkt anhand eines Indexes. Somit gibt es sehr kurze Zugriffszeiten bei einem willkürlichen Zugriff. Im inneren ist ein Array ein fest reservierter, zusammenhängender Platz im Speicher. Die Elemente werden nacheinander in diesem reservierten Speicher abgelegt. Der Index, mit welchem auf die Elemente zugegriffen wird, bezeichnet dann den Abstand des Elements von dem Anfang des Arrays. Somit gibt es nur einen Verweis auf das erste Element und die Elemente selbst, welche in dem Array gespeichert werden.
List
Bei einer Liste handelt es sich um eine dynamisch wachsende Speicherstruktur. Einzelne Elemente oder auch mehrere sind wiederum mit einzelnen oder mehreren Elementen verkettet. Die Elemente liegen also nicht nacheinander im Speicher sondern können überall abgelegt werden. Das wichtige dabei ist jedoch, dass die Verweise nicht abhanden kommen. Der Vorteil liegt klar auf der Hand. Es können dynamisch Elemente hinzu gefügt werden. Die Liste besitzt also keine festen Grenzen wie Beispielsweise das Array. Jedoch habe ich keinen direkten willkürlichen Zugriff auf die Elemente. Denn um zu einem Element zu gelangen muss ich immer den Verweisen, bis zu dem gewünschten Element folgen. Somit ist eine Liste selbstverständlich langsamer als ein Array. Des weiteren werden bei Listen häufig Statusinformationen vorgehalten. Wie die Kapazität der Liste, oder auch die Anzahl der Elemente, welche sich in einer Liste befinden. Des weiteren muss Speicher für die Verweise auf Elemente zur Verfügung stehen. Somit ist noch ein Nachteil der Liste klar sichtbar. Der Overhead ist natürlich auch größer als bei einem Array. Es gibt sehr viele verschiedene Möglichkeiten eine Liste zu programmieren und man wird im Internet sehr schnell fündig über Herangehensweisen an eine Liste. So möchte ich auch eine aufzeigen, da ich vor einiger Zeit eine Liste in C implementiert habe. Dabei handelt es sich um eine einfach verkettete Liste[2].
Vector
Bei einem Vektor handelt es sich ebenfalls um eine dynamische Speicherstruktur. Jedoch wird hier versucht den Nachteil der Lesegeschwindigkeit zu kompensieren. Bei einem Vector handelt es sich im inneren um ein Array, welches nach Bedarf vergrößert wird. Ist also die Kapazität eines Vectors erschöpft, wird ein neues Array initialisiert und alle Elemente welche enthalten waren werden einfach in das neue Array kopiert. Somit hat sich die Kapazität vergrößert. Der Vorteil ist, dass es hier ebenfalls einen willkürlichen Zugriff gibt. Die Lesegeschwindigkeit ist ähnlich hoch, wie bei einem Array. Jedoch kann das einfügen sehr viel länger dauern, wenn denn die Kapazität des Vektors vergrößert werden muss. Von daher sollte man ungefähr eine Ahnung haben wie viele Elemente in dieser Datensammlung gespeichert werden sollen.
Queue
Bei der Queue handelt es sich um eine Datensammlung nach dem FIFO-Prinzip. Also First-in-first-out. Der Zugriff auf die anderen Elemente ist nachrangig. Es erfolgt immer nur direkter Zugriff auf das erste Element in der Struktur. Inwieweit hier intern die Daten organisiert werden ist ebenfalls nachrangig. Da ein Element sofort wieder verworfen wird, wenn es gelesen wurde. Wo kann man eine solche Datenstruktur einsetzten? Ich würde unter anderem sagen, wo Daten aus einem Stream kommen. Es wird dann dort gearbeitet wie bei einer Warteschlange. Die Daten, welche als erstes aus einem Stream kommen, werden als erstes verarbeitet. Die anderen müssen sich hinten anstellen und auf die Verarbeitung noch warten.
Stack
Bei einem Stack handelt es sich um ein ähnliches Prinzip wie bei der Queue. Nur das ein Stack nach dem LIFO-Prinzip arbeitet (Last-in-first-out). Also genau anders herum. Mir mag leider gerade kein Beispiel einfallen, wo ein Stapelspeicher eingesetzt wird in der Programmierung. Jedoch wird auf Prozessorebene ein Stack eingesetzt. Wenn der Prozessor in ein Unterprogramm springt, also in eine Funktion, so wird mindestens die Rücksprungadresse auf den Stack geschrieben. Wenn die Funktion abgearbeitet ist, holt er sich die letzte Rücksprungadresse aus dem Speicher und setzt dann dort seine Arbeit wieder fort.
Set
Bei einem Set handelt es sich um eine Menge. Das heißt ein Element darf in dieser Datensammlung nur ein mal vorkommen. Jetzt stellt sich mir die Frage, wie man das möglichst effizient lösen möchte. Da half mir ein kleiner Blick in die Java-Sources (Die sollten bei einer SDK Installation dabei sein). Jedes Objekt kann in der OOP einen so genannten HashCode erzeugen. Dieser HashCode ist relativ eindeutig.
Ein Hashwert wird deshalb auch als Fingerprint bezeichnet, da er eine nahezu eindeutige Kennzeichnung einer größeren Datenmenge darstellt, so wie ein Fingerabdruck einen Menschen nahezu eindeutig identifiziert.[3]
Die einzelnen Elemente in diese Speicherstruktur ermitteln also ihren Index also weitestgehend selber. Der Index erstellt sich dann weiterhin aus der Abhängigkeit zur Kapazität des Sets. Wird die Kapazität vergrößert, so liegt theoretisch auch das Element an einer anderen Stelle. Des weiteren muss das Element noch mit der Equals-Methode auf Eindeutigkeit geprüft werden. Der Vorteil dieser Speicherstruktur ist, dass ein Element auch wirklich nur ein mal vorkommt. Des weiteren ist der Zugriff auf definierte Elemente sehr schnell, da nicht jedes Element geprüft werden muss.
Map
Bei der letzten Speicherstruktur handelt es sich um eine Map, oder Tabelle. Diese arbeitet im Grunde genommen genauso wie ein Set mit Schlüssel-Wert-Beziehung. Denn es wird zu jedem Wert ein Schlüssel abgelegt. Wobei ein Schlüssel in der Datensammlung immer eindeutig sein muss. Der Zugriff auf den Wert erfolgt dann logischerweise über den Schlüssel. Die einzelnen Schlüssel sind organisiert wie die Elemente in einem Set. Somit kann auch ein Zugriff sehr schnell erfolgen. Hauptsächlich wird diese Speicherstruktur als Cache genutzt. Um sich also Daten vor zuhalten und sehr schnell wieder auf diese zuzugreifen.
Fazit
Ich hoffe eine grobe Zusammenfassung über die Arbeitsweise sowie die Vor- und Nachteile einzelner Speicherstrukturen gegeben zu haben. Somit sollten Speicherstrukturen effizient genutzt werden können. Womit ich meine, dass nur die Vorteile genutzt werden sollten!