interne Funktionsweise eines Arrays

[Gargamel]

Hi

Ich frage mich, wie der Zugriff über einen Index auf ein Array intern funktioniert. Ich könnte mir vorstellen, daß, je länger ein Array ist, umso langsamer der Zugriff auf ein Element erfolgt.
Ist ein Array eine einfach verkettete Liste, wo jedes Element jeweils über einen Zeiger seinen linken und rechten Nachbarn kennt? Müsste dann, ausgehend vom ersten Element, der jeweile rechte Nachbar 5x ermittelt werden (in einer Schleife), um das Element bei Index 5 zu erhalten?

Ein Compiler kann ja sicherlich optimieren, aber bei einem dynamischen Array gäbe es diese Möglichkeit doch nicht, da die Länge des Arrays zu diesem Zeitpunkt noch nicht bekannt ist.

Kann jemand darüber Aufschluß geben?

Vielen Dank

[Namenloser]

Ein Array ist keine verkettete Liste sondern ein Array

Das Array ist ein einziger „Speicherblock“, in dem seine Element alle schön zusammenhängend hintereinander stehen.

Z.B. ein arr: Array[0..4] of Integer sieht im Speicher so aus (ein Integer ist 4 Bytes lang):

Code:

Adresse 00 01 02 03 04 05 06 07 08 09 0A 0B 0C 0D 0E 0F 10 11 12 13 ...
Inhalt |   arr[0] .|   arr[1] .|   arr[2] .|   arr[3] .|   arr[4] .|

(Wobei die Adresse hier relativ zur Startadresse des Array ist)

Da jedes Element die gleiche Länge hat, kann man ein bestimmtes Element einfach adressieren, indem man seine Position im Array mit der Länge eines Elements multipliziert.

Delphi-Quellcode:

arr: array of T;
arr[i] = (^T(@arr[0] + i * sizeof(T)))^;

Somit erfolgt der Zugriff auf ein beliebiges Element in konstanter Zeit.

Dynamische Arrays funktionieren genau so wie Arrays mit fester Größe, nur dass der vom Array allozierte Speicherbereich nachträglich vergrößert werden kann, wenn sich das Array füllt. Je nach Speichermanager kann das bedeuten, dass jedes mal, wenn die Länge vergrößert wird, ein neuer Speicherbereich alloziert wird und alle Elemente vom alten, kleineren Speicherbereich in den neuen, größeren umkopiert werden müssen. Deshalb sollte man auch nicht Elemente so einfügen:

Delphi-Quellcode:

var
  arr: array of Integer;
  i: integer;
begin
  for i := 1 to 100 do
  begin
    SetLength(arr, Length(arr)+1);
    arr[high(arr)] := i;
  end;
end;

Stattdessen sollte man gleich die richtige Länge setzen:

Delphi-Quellcode:

var
  arr: array of Integer;
  i: integer;
begin
  SetLength(arr, 100);
  for i := 1 to 100 do
    arr[i-1] := i;
end;

Wenn man die Länge nicht von Anfang an weiß, dann sollte man möglichst in größeren Blöcken allozieren (und sich ggf. die echte Anzahl der Elemente in einer Extra-Variablen merken... TList macht es auch so (siehe Capacity vs. Count)).

Genaueres dazu kannst du auf Wikipedia lesen.

[Gargamel]

Vielen Dank.
Der Knackpunkt war demnach, daß sich die Elemente eines Arrays zusammenhängend im RAM befinden und nicht einzeln irgendwo verstreut. Und durch die Multiplikation des Index mit der Byte-Größe eines Elementes kann jedes Element schnell angesprochen werden.

Jetzt ergibt sich jedoch die Frage, was man macht, wenn die Anzahl der Elemente sehr stark variiert und es durchaus sein kann, daß viele Elemente in einem Rutsch hinzugefügt werden müssen.

Eine ausreichende Dimensionierung des Arrays ist in bestimmten Fällen nicht möglich, zumal wenn man auf einen mehr oder weniger effektiven Speicherverbrauch achten möchte.

[Bjoerk]

Das geht z.B wie bei der von Namenloser angesprochen TList. Dort wird bei jedem Hinzufügen geprüft ob die Liste vergrößert werden muß. Werden Items aus der Liste rausgelöscht passiert sozusagen nichts, außer daß Count um eins verkleinert wird (beim TListNachfolger TObjectList wird ggf. das noch Object freigegeben).

In Delphi wird die Liste nach folgender Function vergrößert:

Delphi-Quellcode:

function DeltaCapacity: integer;
begin
  if FCapacity > 64 then
    Result := FCapacity div 4
  else
    if FCapacity > 8 then
      Result := 16
    else
      Result := 4;
end;

[Gargamel]

Ja, das mit Capacity vs. Count kenne ich aus dem .net Framework.

[Bjoerk]

Gut. Dann würd' ich satt des Array aber ein kleine Klasse schreiben? Beispiel:

Delphi-Quellcode:

  TIntegerList = class
  private
    FCount, FCapacity: integer;
    FItems: array of integer;
    function GetItems(Index: integer): integer;
    procedure SetItems(Index: integer; const Value: integer);
    function DeltaCapacity: integer;
    procedure SetCapacity(const Value: integer);
  public
    function Add(const Value: integer): integer;
    procedure Insert(const Index: integer; const Value: integer);
    procedure Delete(const Index: integer);
    procedure Clear;
    property Items[Index: integer]: integer read GetItems write SetItems; default;
    property Count: integer read FCount;
    property Capacity: integer read FCapacity write SetCapacity;
    destructor Destroy; override;
  end;

{ TIntegerList }

destructor TIntegerList.Destroy;
begin
  Clear;
  inherited Destroy;
end;

procedure TIntegerList.Clear;
begin
  SetCapacity(0);
  FCount := 0;
end;

function TIntegerList.DeltaCapacity: integer;
begin
  if FCapacity > 64 then
    Result := FCapacity div 4
  else
    if FCapacity > 8 then
      Result := 16
    else
      Result := 4;
end;

procedure TIntegerList.SetCapacity(const Value: integer);
begin
  FCapacity := Value;
  SetLength(FItems, FCapacity);
end;

function TIntegerList.Add(const Value: integer): integer;
begin
  Result := FCount;
  Insert(Result, Value);
end;

procedure TIntegerList.Insert(const Index: integer; const Value: integer);
var
  I: integer;
begin
  if (Index >= 0) and (Index <= FCount) then
  begin
    if FCount = FCapacity then
      SetCapacity(FCapacity + DeltaCapacity);
    Inc(FCount);
    for I := FCount - 1 downto Index + 1 do
      FItems[I] := FItems[I - 1];
    FItems[Index] := Value;
  end;
end;

procedure TIntegerList.Delete(const Index: integer);
var
  I: integer;
begin
  if (Index >= 0) and (Index < FCount) then
  begin
    for I := Index to FCount - 2 do
      FItems[I] := FItems[I + 1];
    Dec(FCount);
    FItems[FCount] := 0;
  end;
end;

function TIntegerList.GetItems(Index: integer): integer;
begin
  Result := FItems[Index];
end;

procedure TIntegerList.SetItems(Index: integer; const Value: integer);
begin
  FItems[Index] := Value;
end;

[Aphton]

Zitat von Gargamel:

Jetzt ergibt sich jedoch die Frage, was man macht, wenn die Anzahl der Elemente sehr stark variiert und es durchaus sein kann, daß viele Elemente in einem Rutsch hinzugefügt werden müssen.

Eine ausreichende Dimensionierung des Arrays ist in bestimmten Fällen nicht möglich, zumal wenn man auf einen mehr oder weniger effektiven Speicherverbrauch achten möchte.

Kommt ganz drauf an, was man mit dem Array (oder lieber Container) machen will.
Es ist ein Tradeoff zwischen Speicher & Geschinwidgkeit:
Entweder du kannst schnell über Index lesen/schreiben, dafür aber langsam einfügen/löschen - oder umgekehrt!

Array:
O(1) Lesen/Schreiben (Iteration)
O(n) Einfügen/Löschen

Verkettete Liste:
O(n) Lesen/Schreiben (Iteration)
O(1) Einfügen/Löschen

Wichtig ist noch, dass man bedenken muss, dass eine Liste für jedes Element einen Overhead von 4 (32bit) / 8 (64bit) Byte (Next Pointer - einfach verkettet) oder 8 (32bit) / 16 (64bit) (Next, Prev Pointer - doppelt verkettet) hat.

Wenn man nun eine Liste verwendet und beispielsweise darin 1.000 Integer Elemente hat, dann hat man insgesamt eine Größe von 1000 * SizeOf(Integer) * SizeOf(Prev/Next) = (32bit) 1000 * 4 * 8 = 32.000
Beim Array: 4 + 1000 * 4 = 4.004
(4 Bytes werden von Delphi insgeheim an der Adresse (ArrayPtr-4) angelegt, um die Länge zu merken)

Man kann übrigens noch schneller als O(n) sein, dafür ein Beispiel mit einem Binärbaum:
O(N * log N) Lesen/Schreiben
O(log N) Einfügen/Löschen

Du kannst ja mal erläutern, um was für Daten es sich handelt und in welcher Relation diese zueinander stehen.

[BUG]

@Aphton: Ich glaube es war mehr eine Verständnisfrage.

Verkettete Listen kennen und über Laufzeiten nachdenken, aber keine Ahnung von den technischen Grundlagen ... Kinder heutzutage ... das hätte es früher nicht gegeben ... müsste man alle mal zum Assembler programmieren schicken nichts

[himitsu]

Die Größe des Arrays ist vollkommen egal, da der Zugriff über einen Index (Offset) immer gleich schnell ist.
SpeicherAdresse = Array-Pointer + Index * SizeOf(...)
Aus diesem Grund besteht ein Array auch immer nur aus einem zusammenhängendem Block, welcher die Maximalgröße bestimmt, da sie durch den größten freien Speicherblock bestimmt wird, welcher verwendet werden kann -> Speicherfragmentierung.

Was langsamer wird, je größer das Array (und auch eine TList<>, welche intern ebenfalls ein Array nutzt) wird, die Änderung der Größe.
Wenn der Speicher nicht inplace verändert werden kann (was der FastMM beherscht), weil z.B. dahinter kein freier Platz mehr ist, dann muß der Speicher umkopiert werden, was natürlich bei mehr Daten etwas länger dauert.


Bei einer verketteten Liste wäre zwar die Größe durch den gesamten belegbaren Speicher wesentlich unbegenzter und die Größenänderung (Speicherreservierung/-freigabe) hängt nicht von der Größe der Liste ab, aber dafür ist der Zugriff langsamer, außer man baut parallel einen Index auf.

[Gargamel]

@Aphton (und natürlich alle anderen auch)

Zitat:

Du kannst ja mal erläutern, um was für Daten es sich handelt und in welcher Relation diese zueinander stehen.

Es geht darum, daß eine KI innerhalb einer DLL ausgeführt/berechnet werden soll. Die Host-Anwendung ist Unity3D. Die Programmierung innerhalb dieser 3D-Engine erfolgt mit C# und damit managed Code. Das Thema 'Ausführungsgeschwindigkeit managed Code vs. nativer Code' liefert im Internet gerne mal widersprüchliche Aussagen. Aber lassen wir das mal aussen vor.
Jetzt ist es so, daß ein reger Datenaustausch zwischen der Engine und der KI-DLL stattfindet. Mein Gedanke war der, daß jedes Objekt innerhalb der Engine, welches durch KI gesteuert werden soll, ein Schwester-Objekt innerhalb der DLL besitzt und diesem immer seine aktuellsten Werte übermittelt. Also Position, Rotation, Sichtbarkeiten (Portale), Kollision mit Objekt XY usw. ...
Das Schwester-Objekt rechnet irgendwelche Dinge auf Basis von State-Machines, Pathfinding, Fuzzy-Logic, Schwarmverhalten, etc. aus und liefert dem zugehörigen Objekt in der 3D-Engine alle nötigen Informationen, was es denn nun tun soll (drehe Dich in diese Richtung, schieße da hin, spiele Animation XY mit, usw. ...).

Jedes Objekt in der Engine, was durch die KI gesteuert wird, erhält von der DLL eine eindeutige ID-Nummer (und damit den Index eines Arrays), um mit seinem Schwester-Objekt kommunizieren zu können. Und genau an dieser Stelle war ich mir unschlüssig, ob der ständige Zugriff über ein Array-Index u.U. zu langsam ist. Wobei 'langsam' natürlich relativ ist.

Zudem kommt noch, daß es je nach Spiel bzw. Gameplay vorkommen kann, daß KI-Objekte in einem kurzen Turnus erstellt und wieder gelöscht werden. Und das bedeutet, daß es recht schnell Lücken innerhalb des Arrays geben kann, die man sich irgendwie merken muß, um diese mit später erzeugten KI-Objekten wieder befüllen zu können.

Um das zu umgehen, fielen mir einfach verkettete Listen ein, da man schnell Elemente entfernen und hinzufügen kann.
Gestern testete ich die Möglichkeit, mir von diversen Variablen in der DLL die Speicheradressen liefern zu lassen. Auf diese Weise konnte ich aus der 3D-Engine heraus den Speicherinhalt der DLL-Variablen direkt manipulieren (was dem Aktualisieren der Schwester-Objekte für Positon. Rotation, ... entsprechen würde).