Dynamische Array vs. Zeigerverkettung

[hugh]

Tach zusammen!

Mir ist in Erinnerung, dass dynamische Arrays langsame sind als zeigerverkettete Listen. Kann mir jemand sagen, wie gross dieser Geschwindigkeitsunterschied ist bzw. wann er sich bemerkbar macht?

Besten Dank im Voraus.

Gruss Andreas

[neolithos]

Wenn ein Dynamisches Array um ein Element erweitert wird, kann es passieren das das Gesamte Array in einen neuen größeren Speicherbereich kopiert werden muss.

[Chewie]

Die Entscheidung "A ist schneller als B" ist so allgemein schwer zu treffen. Beide Ideen, Arrays oder Verkettungen haben Vor- und Nachteile.

Bei Arrays kann die Speicheradresse eines jeden Elementes exakt berechnet werden, und das muss sie auch. Bei jedem Zugriff wird also die Rechnung

Code:

Startadresse + Index * Elementgröße

durchgeführt, bei mehrdimensionalen Arrays muss das für jede Dimension gemacht werden! Insbesondere die Multiplikationen brauchen dabei vergleichsweise lange.
Bei verketteten Liste ist ja mindestens ein Zeiger auf ein weiteres Element enthalten, der Zugriff ist also einfaches Rumkopieren von Speicheradressen ohne, dass der Rechner rechnen muss.
Allerdings kann man eine verkettete Struktur immer nur von Element zu Element durchlaufen, in einem Array dagegen kann mit dem gleichen Aufwand auf das 1. Element zugreifen wie auf ein beliebiges anderes.

Bei verketteten Listen wird ja häufig neuer Speicher alloziert. Wenn man dazu eine Speicherverwaltung benutzt, die die Speicherblöcke über den ganzen Speicher verteilt, riskiert man eine Speicherfragmentierung. Dadurch verteilen sich die Speicherzugriffe auf viele Speicherseiten, jede einzelne Speicherseite hat nur wenige Zugriffe. Da der VirtualMemoryManager bevorzugt die Speicherseiten, die am wenigsten genutzt werden, auslagert, kann hier sehr viel Rechenzeit verloren gehen (da die Daten evtl. erst von der Festplatte geholt werden müssen).

Weiterhin ist bei dynamischen Arrays das tödlich:

Delphi-Quellcode:

var
  i: Integer;
  a: Array of Integer;
begin
  for i := 1 to 1000 do
    SetLength(a, i);

Dabei wird das komplette Array nämlich jedes Mal an eine andere Stelle im Speicher kopiert, was erstmal sehr lange dauert. Und durch eine Eigenart im Speichermanager von Delphi wird der alte Speicher nicht oder nur unvollständig freigegeben (zu diesem Thema gab es neulich eine Diskussion, ich find den Beitrag aber nicht mehr).