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;

[Dejan Vu]

Bitte nicht durcheinander bringen: Listen vs. Array. Du hast einen Integer-Array, keine Liste.

Soviel Aufwand muss man da aber auch nicht machen, finde ich. Ein Array ist so generisch, das man das nicht kapseln sollte, denn wer ein Array will, der will auch Performance.

[Bjoerk]

Irgendein internes Array braucht halt jede Liste? Aber soviel ist auch klar: So eine Liste braucht kein Mensch, sollte nur ein Beispiel sein..

[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