Arrays und Listen

Valid XHTML 1.0!


Inhaltsverzeichnis:

Einführung
Arrays
Listen
Pointer-Arrays
Gegenüberstellung
Quasidynamische Arrays
Arrays in Object Pascal
Klassen in der VCL
Vergleich zwischen TList und array of
Mehrdimensionale Arrays

Letzte Änderung am 05.04.2003. zurück zum Artikel-Index,    zurück zur Delphi-Seite


Einführung

Dieser Artikel behandelt Arrays und Listen, ihre Unterschiede, ihre Eigenschaften und die konkrete Anwendung in Delphi.

Ein Array ist eine geordnete Menge gleichartiger Datentypen. Eine Liste ist eine geordnete Menge möglicherweise verschiedener Datentypen.

Es gibt bestimmte Operationen, die mit geordneten Mengen vorgenommen werden können. Dazu gehört der Zugriff auf ein bestimmtes Element, das Suchen nach einem bestimmten Element und das Einfügen und Löschen von Elementen. Eine weitere Operation ist das Sortieren, der Sortiervorgang besteht aus einer bestimmten Menge von Lösch- und Einfügeoperationen.

Hinweise zu den Angaben zum Speicherbedarf
n ist die Anzahl der Elemente
m ist die maximale Anzahl der Elemente
x steht für den Zuwachs durch die Speicherverwaltung. Die aktuelle Speicherverwaltung von Delphi reserviert vor dem Block noch ein DWord (4 Byte) für die Größe und benötigt mindestens 12 Byte und durch vier teilbare Größen.
zurück zum Inhaltsverzeichnis


Arrays

Arrays sind dadurch gekennzeichnet, daß die Elemente über einen Index angesprochen werden. Die Elemente liegen hintereinander im Speicher.

Arrays sind statisch, d.h. Arrays können ihre Größe nicht ändern. Damit haben sie eine maximale Anzahl von Elementen, die nicht überschritten werden kann. Werden weniger Elemente benutzt, dann ist der restliche Speicher verschwendet. Die maximal mögliche Größe ist vom Speicher abhängig. Die Größe des Arrays wird beim Anlegen festgelegt.

Der Zugriff auf ein bestimmtes Element kann direkt erfolgen. Bei einer Suche muß jedes Element des Arrays durchsucht werden, bis der Eintrag gefunden ist. Ist das Array entsprechend dem Suchkriterium sortiert, dann kann eine binäre Suche angewendet werden.

Beim Einfügen oder Löschen eines Elementes müssen alle nachfolgenden Elemente im Array verschoben werden.

Bei einem Array muß nur einmal für alle Elemente gleichzeitig Speicher reserviert und freigegeben werden. Der Speicherbdarf beträgt: m * SizeOf(Element) + x
zurück zum Inhaltsverzeichnis


Listen

Listen sind dadurch gekennzeichnet, das die Elemente über Zeiger miteinander verbunden werden. Die Elemente liegen an unterschiedlichen Stellen im Speicher.

Listen sind dynamisch, d.h. Listen können ihre Größe problemlos ändern. Die maximale Anzahl von Elementen ist nur vom Speicher abhängig.

Der Zugriff auf ein bestimmtes Element kann nicht direkt erfolgen. Ausgehend vom ersten Element muß die Liste bis zum gewünschten Element durchgegangen werden. Bei einer Suche muß jedes Element des Arrays durchsucht werden, bis der Eintrag gefunden ist. Eine binäre Suche kann nicht angewendet werden.

Es gibt einfach und doppelt verkettete Liste. Einfach verkettete Listen erlauben nur eine Bewegung vom ersten Element zum nächsten. Doppelt verkette Listen erlauben auch eine Bewegung in die andere Richtung.

Beim Einfügen oder Löschen eines Elementes müssen nur die Zeiger für Verkettung geändert werden.

Bei einer Liste muß für jedes Element einzeln Speicher reserviert und freigegeben werden. m * SizeOf(Pointer) + x + n * SizeOf(Element) + x

Auch wenn der Name es vermuten ließe, TList ist keine verkettete Liste, sondern die Kapselung eines Pointer-Arrays.

Eine gute Beschreibung zu verketteten Listen und die ihre Programmierung in Pascal habe ich als Teil eines Pascal Kurses im Internet gefunden, darum spare ich mir das hier.

Wer sich für den gesamten Kurs interessiert, er ist in Teil1 und Teil 2 aufgeteilt.
zurück zum Inhaltsverzeichnis


Pointer-Arrays

Pointer-Arrays sind ein Kompromiß zwischen Arrays und Listen. Sie sind dadurch gekennzeichnet, daß die Elemente über ein Array von Pointern verwaltet werden. Die Elemente können dadurch, wie bei einem Array, über einen Index angesprochen werden. Die Elemente liegen an unterschiedlichen Stellen im Speicher.

Pointer-Arrays sind statisch, d.h. sie können ihre Größe nicht ändern. Damit haben sie eine maximale Anzahl von Elementen, die nicht überschritten werden kann. Werden weniger Elemente benutzt, dann ist der restliche Speicher verschwendet. Diese Verschwendung bezieht sich aber nur auf den Platz für einen Pointer pro Element. Die maximal mögliche Größe ist vom Speicher abhängig. Die Größe des Arrays wird beim Anlegen festgelegt.

Der Zugriff auf ein bestimmtes Element kann direkt erfolgen. Bei einer Suche muß jedes Element des Arrays durchsucht werden, bis der Eintrag gefunden ist. Ist das Pointer-Array entsprechend dem Suchkriterium sortiert, dann kann eine binäre Suche angewendet werden.

Beim Einfügen oder Löschen eines Elementes müssen alle Pointer für die nachfolgenden Elemente im Pointer-Array verschoben werden.

Bei einem Pointer-Array muß einmalig für das Pointer-Array und für jedes Element einzeln Speicher reserviert und freigegeben werden. Der Speicherbedarf beträgt: n * (SizeOf(Element) + SizeOf(Pointer) + x)
zurück zum Inhaltsverzeichnis


Gegenüberstellung

Eigenschaft Array Liste Pointer-Array
Größenänderung nicht möglich problemlos möglich nicht möglich
Einfügen / Löschen langsam schnell mittel
Zugriff auf n-tes Element schnell langsam schnell
binäre Suche möglich nicht möglich möglich
Typ des Elementes muß gleich sein kann unterschiedlich sein kann unterschiedlich sein
zurück zum Inhaltsverzeichnis


Quasidynamische Arrays

Wie man erkennen kann, leiden Arrays im wesentlichen unter der Größenbeschränkung. Es gibt eine Möglichkeit diese Beschränkung zu umgehen. Es wird ein neues Array angelegt die Elemente in das neue Array kopiert und dann das alte Array gelöscht.

Dieser Vorgang kostet natürlich Zeit und benötigt während des Kopierens doppelt so viel Speicher. Hier haben die Pointer-Arrays auch wieder entsprechende Vorteile, da nur die Pointer kopiert werden müssen, nicht die (größeren) Elemente.

Ein kleines technisches Problem am Rande. Da sich der Ort des Arrays ändert, kommen für dieses Vorgehen nur dynamisch erzeugte Arrays in Frage. Die Pointervariable zeigt anschließend auf das neue Array, das bedeutet, daß auch nur eine Pointervariable gleichzeitig auf das Array zeigen darf, da eine weitere sonst auf das freigegebene alte Array zeigt.
zurück zum Inhaltsverzeichnis


Arrays in Object Pascal

In Object Pascal gibt es verschiedene Möglichkeiten mit Arrays zu arbeiten.

Konstanten-Array
Die Elemente liegen direkt im Code. Das Array und sein Inhalt können nicht verändert werden. Der Compiler erzeugt Code für die Bereichsprüfung, wenn der entsprechende Compilerschalter gesetzt ist.

const
  Bitmask: array[0..3] of Integer = ($01, $02, $04, $08);


Array-Variable
Die Elemente liegen im Stack (lokale Variable) oder im 'Datensegment' (globale Variable). Der Speicher wird automatisch reserviert und freigegeben. Die (maximale) Anzahl der Elemente muß zur Entwicklungszeit bekannt sein. Der Compiler erzeugt Code für die Bereichsprüfung, wenn der entsprechende Compilerschalter gesetzt ist.

procedure ...
var
  arr: array[0..10] of Double;


dynamisch erzeugtes Array
Die Elemente liegen im Heap. Die (maximale) Anzahl der Elemente muß erst zur Laufzeit bekannt sein. Der Programmierer muß sich selbst um Speicherreservierung, Freigabe und Resourcenschutz kümmern. Der Programmierer muß eigenen Code zur Bereichsprüfung schreiben. Der Programmierer kann bei Bedarf die Größe des Arrays verändern, siehe quasidynamische Arrays. Der entsprechende Code dafür muß vom Programmierer selbst erzeugt werden.

type
  TMyItem = Double;
  PMyArray = ^TMyArray;
  TMyArray = array[0..16000] of TMyItem;

var
  arr: PMyArray;
  ..
begin
  ...
  GetMem(arr, ItemCount * SizeOf(TMyItem));
  try
    ...
    arr^[0] := 0.0;
    ...
  finally
    FreeMem(arr);
  end;

Die in TMyArray festgelegte Größe ist rein fiktiv und kann beliebig gewählt werden.


Delphi's dynamisches Array
Hierbei handelt es sich um ein dynamisch erzeugtes Array. Der Compiler fügt jedoch automatisch Code ein, um dem Programmierer die Arbeit zu erleichtern. Zusätzlich dazu gibt es einen Referenzmechanismus.

Die Elemente liegen im Heap. Die (maximale) Anzahl der Elemente muß erst zur Laufzeit bekannt sein. Der Programmierer muß sich selbst um die Speicherreservierung kümmern. Der Compiler erzeugt Code für die Bereichsprüfung, wenn der entsprechende Compilerschalter gesetzt ist. Der Programmierer kann bei Bedarf die Größe des Arrays verändern, siehe quasidynamische Arrays. Für Speicherreservierung, Größenänderung und Freigabe steht die Procedure SetLength zur Verfügung. Mit Length kann die aktuelle Größe abgefragt werden.

Dynamische Array-Variablen sind Zeiger, auch wenn man ihnen das nicht ansieht. Das hat entsprechende Auswirkungen. Wird eine normale Array Variable zugewiesen, dann wird deren Inhalt kopiert. Bei einer Dynamische Array-Variablen wird nur der Zeiger kopiert und der Referenzzähler erhöht. Wird anschließend ein Element geändert, dann ist dieses Element bei beiden Array-Variablen geändert. Anders sieht es bei SetLength aus. Wird nach einer Zuweisung die Größe des Arrays verändert, dann geschieht dies nur bei der einen Variablen. Die andere zeigt immer noch auf das alte Array. Das kann man sich zunutze machen und nach einer Zuweisung SetLength mit der aktuellen Größe (Length) aufrufen, um Änderungen in der anderen Variable zu verhindern. Ein solcher Aufruf stellt sicher, daß das Array einen Referenzzähler von 1 hat.

type
  TMyItem = Double;

var
  arr: array of TMyItem;
  ..
begin
  ...
  SetLength(arr, ItemCount);
  ...
  arr[0] := 0.0;
  ...

Es wird semantisch gleicher Code erzeugt, wie beim Beispiel mit dem dynamisch erzeugtes Array.
zurück zum Inhaltsverzeichnis


Klassen in der VCL

Die VCL stellt mehrere Klassen zur Verfügung, die intern mit Pointer-Arrays arbeiten. Die Klassen arbeiten quasidynamisch und verfügen über getrennte Eigenschaften für Kapazität (Capacity) und Größe (Count). Unter Größe wird dabei die Anzahl der verwendeten Elemente verstanden, unter Kapazität die maximale Anzahl.

Die Klassen stellen Methoden für die Veränderung der Größe, das Einfügen, Löschen, Vertauschen und Sortieren von Elementen zur Verfügung. Die Klassen führen generell eine Bereichsüberprüfung durch, der Speicher für das Pointerarray wird automatisch verwaltet. Der Programmierer muß sich selbst um Speicherreservierung, Freigabe und Resourcenschutz für die Klasse kümmern.

TList
TList ist die Kapselung eines Pointerarrays. Der Programmierer muß sich selbst um Speicherreservierung, Freigabe und Resourcenschutz für die Elemente kümmern. Der Zugriff auf die Elemente erfolgt über den Typ Pointer.

TThreadList
TThreadList ist eine threadsichere Kapselung für eine TList.

TObjectList
TObjectList ist eine Klasse, die sehr ähnlich, wie TList arbeitet. Der Unterschied ist, daß TObjectList anstelle des Typs Pointer den Typ TObject verlangt. TObjectList enthält eine Eigenschaft OwnsObjects, über welche festgelegt werden kann, ob die Elemente (vom Typ TObject abgeleitete Klassen) freigegeben werden sollen oder nicht.

TStringList
TStringList ist von TStrings abgeleitet. Das intern verwendete Array enthält zwei Pointer. Der eine zeigt auf einen String, der andere ist für eine Instanz gedacht, die von TObject abgeleitet ist. Diese Klasse ist besonders für Elemente geeignet, die über einen String angesprochen werden sollen.

TCollection
TCollection sorgt sich komplett um die Verwaltung von Instanzen, die von TCollectionItem abgeleitet sind. Der Programmierer muß sich nicht um die Reservierung oder Freigabe von Elementen kümmern. Suche und Sortierung sind nicht implementiert.

TBits
TBits ist eine ganze spezielle Form eines Arrays. Die Elemente dieses Arrays sind Bits. Der Speicherbedarf für TBits ist ((n + 7 div 8) + x) + 16.
zurück zum Inhaltsverzeichnis


Vergleich zwischen TList und array of

Double (8 Byte), 10 000 Elemente TList Array
Speicherbedarf (in Byte) 160 024 80 012
10 000 Elemente auf einmal einfügen (leeres Array) 2 500 280
10 000 Elemente einzeln an ein leeres Array anhängen 2 700 3 400
10 000 Elemente lesen (bilden einer Summe) 290 160
10 000 Elemente mit 0 initialisieren (schreiben) 200 90
Einfügen von 1 000 Elementen verteilt über das gesamte Array 24 000 50 000
Löschen von 1 000 Elementen verteilt über das gesamte Array 23 500 50 000
Sortieren 7 500 3 430

Struktur 256 Byte, 10 000 Elemente TList Array
Speicherbedarf (in Byte) 2 560 012 2 640 020
Array mit 10 000 Elementen auf einmal anlegen 9 150 7 100
10 000 Elemente einzeln an ein leeres Array anhängen 10 100 17 100
Einfügen von 1 000 Elementen verteilt über das gesamte Array 25 000 4 720 000
Löschen von 1 000 Elementen verteilt über das gesamte Array 25 000 4 480 000
Sortieren 21 300 19 400

Struktur 1 024 Byte, 10 000 Elemente TList Array
Speicherbedarf (in Byte) 10 280 012 10 320 020
Array mit 10 000 Elementen auf einmal anlegen 33 300 30 000
10 000 Elemente einzeln an ein leeres Array anhängen 34 000 44 000
Einfügen von 1 000 Elementen verteilt über das gesamte Array 27 400 19 450 000
Löschen von 1 000 Elementen verteilt über das gesamte Array 24 000 17 250 000
Sortieren 72 000 73 000

Die Zeiten sind Durchschnittswerte. Sie sollten als Tendenz verstanden werden. Wenn es interessiert, es handelt sich bei den Werten um Vielfache von 2,857 Mikrosekunden, in dieser Einheit sind sie jedoch auf meinen Rechner bezogen.
zurück zum Inhaltsverzeichnis


Mehrdimensionale Arrays

Mehrdimensionale Arrays lassen sich als Arrays von Arrays zusammensetzen. Je nach Speicheralloziierung ergeben sich daraus zwei Modelle. Das eine tastet sich Dimension für Dimension vor, bis es zum Element kommt. Das andere überführt ein mehrdimensionales Array in ein eindimensionales.

In Delphi kommen mehrdimensionale Arrays bei Array-Variablen und bei den dynamischen Array-Variablen vor. Erstere benutzen ein eindimensionales Array und berechnen die Indizies entsprechend. Bei den dynamischen Array-Variablen wird ein Array auf ein Array angelegt. Da es sich bei den dynamischen Array-Variablen um Zeiger handelt, also Array auf Pointer. Daraus ergibt sich die verwirrende Situation, das auch ungleichförmige Arrays angelegt werden können. Werden bei SetLength alle Dimensionen angegeben, entsteht ein gleichförmige Array. Wird Beispielsweise nur eine Dimension angegeben, dann kann für jedes Element für die nächste Dimension eine unterschiedliche Größe festgelegt werden.
zurück zum Inhaltsverzeichnis

Mails an mich unter webmaster@pjh2.de. Haftungsausschluss
Bitte keine E-Mails zu Delphi, die sich nicht auf diese Seiten beziehen. Sie werden von mir nicht beantwortet.