Speicherallokation / Geschwindigkeit beim speichern und auslesen

[Kishmet]

Guten Morgen zusammen,

ich habe mir gerade eine Funktion geschrieben und tue mich gerade etwas schwer, weil mir hier vielleicht ein wenig Grundlagen fehlen über Delphi und vielleicht auch allgemein. Daher dachte ich, ich frage einfach mal.

Folgende Funktion hab ich grade geschrieben, um einfach mal die lokalen Minima zu finden

Code:

function Find_local_minima(Values: TIntegerDynArray; var res_pos: TIntegerDynArray): Boolean;
begin
  //Achtung: ersten und letzten Wert nicht überprüfen!
  for var i  := 1 to length(Values)-2 do
  begin
    if (Values[i-1] > Values[i]) and (Values[i+1] > Values[i]) then
    begin
      res_pos := res_pos + [i];
    end;
  end;
end;

soweit so gut. (Sei mal dahingestellt ob die Funktion so schon gut ist, darum soll es hier nicht gehen, nehme aber natürlich gerne Vorschläge entgegen wie das besser gehen könnte. Muss aber dazu sagen, das ich erst vor ein paar Minuten angefangen habe und dann Zeit auf eine Google suche zu meiner Frage verschwendet habe. Darum ist bspw. auch das Result noch nicht gemacht).

Ich frage mich gerade ob es einen Unterschied für die Speicherallokation und vielleicht auch die Geschwindigkeit macht, wenn ich dem Array res_pos die Werte einfach hinten anhänge. Gibt es hier etwas das Schneller ist (sowohl bezüglich anhängen/hinzufügen als auch dann beim Auslesen)? Ich bin mir nicht sicher wie die Allokation hier funktioniert. Wird jedesmal wenn ich einen Wert hinzufüge ein neues Array angelegt und alle Werte dahin übertragen oder sind das nur Pointer die dann auf den jeweiligen Wert zeigen?

Vielen lieben dank für alle die bis hier gelesen haben. Über Antworten wäre ich super dankbar!

[jaenicke]

Es geht deutlich schneller, wenn du die Größe des Arrays zuerst setzt, dann die Werte setzt und am Ende das Array ggf. auf die korrekte Größe reduzierst. Oder du vergrößerst das Array in Schritten, wenn du die Größe vorher nicht abschätzen kannst.

[Kishmet]

@jaenicke: Super danke dir! Kannst du auch erklären warum? Was passiert hier im Hintergrund? bzw. was ist der Unterschied zwischen

Code:

res_pos := res_pos + [Wert];

und

Code:

Res_pos[Index] := Wert;

[Der schöne Günther]

Der Kernpunkt eines Arrays (im Vergleich zu bspw. einer Liste, einem Stack und anderen), ist, dass es eine feste Länge hat. Ein Array wächst oder schrumpft nicht - Der Speicherverbrauch ist immer gleich.

Mit der Zeile

Delphi-Quellcode:

res_pos := res_pos + [Wert];

legst du ein neues Array an, das den Inhalt von

Delphi-Quellcode:

res_pos

enthält, plus

Delphi-Quellcode:

Wert

hintendran. Dann steckst du dieses neue Array in die Variable

Delphi-Quellcode:

res_pos

, und das alte Array wird gelöscht.

[Kishmet]

@Günther: Ok, dann ist das wirklich so wie ich das ganz oben schon angefragt hatte. Vielen Dank!

[Gausi]

Etwas mehr Hintergrund:

Die "Listen" in Delphi (d.h. TList u.ä.) sind meistens auch intern als dynamisches Array implementiert. Dort wird das Problem der hohen Laufzeit beim wiederholten Hinzufügen neuer Elemente dadurch beschleunigt, dass diese internen Arrays nicht bei jeder Einfüge-Operation nur um 1 vergrößert werden, sondern um deutlich mehr, iirc um 25% der alten Größe (falls nötig).

D.h. wenn man in eine (volle) Liste mit 100 Elementen ein neues Element einfügt, wird das interne Array so vergrößert, dass nicht nur 101 Elemente, sondern 125 Elemente hineinpassen. Dadurch ist die amortisierte Laufzeit für das wiederholte Einfügen dann vergleichbar mit Listen, die auch als (doppelt) verkettete Liste implementiert sind. Aber auch in dem Fall ist es sinnvoll, die Größe vorher festzulegen, wenn man sie kennt. Dafür gibt es bei TList die Property Capacity.

[Kishmet]

@Gausi: ah! Das erklärt mir gerade an einer anderen Stelle ein Verhalten, das ich mir nicht erklären konnte! Super! Vielen lieben Dank!

[Mavarik]

Wenn es noch schneller werden kann, nimm Pointer auf die Elemente und nicht den Array-Zugriff.

Mavarik

[himitsu]

Bei einem Integer-Array gibt es aber kaum noch einen Unterschied.

Bei einem String (intern fast sowas wie ein Char-Array) ist der Zugriff auf die Zeichen dadurch langsam, dass ständig ein UniqueString eingefügt wird,
aber bei normalen Arrays ist schon seit Anfang an in diesem Fall die Referenzprüfung im Arsch (garnicht erst eingebaut).

[Der schöne Günther]

Zitat:

Zitat von Mavarik (Beitrag 1535697)

Wenn es noch schneller werden kann, nimm Pointer auf die Elemente und nicht den Array-Zugriff.

Das halte ich für ein Gerücht.

[himitsu]

Kommt auch drauf an, wie man pointert ... ja, es kann einen Hauch ausmachen.

[Der schöne Günther]

Ich kann zwar keinen Assemblercode lesen, aber ich würde jetzt Geld wetten dass der Compiler den gleichen Code aus

Delphi-Quellcode:

meinArray[meinePosition] := 42

und irgendeiner wilden Pointer-Arithmetik macht.

[jaenicke]

Zitat:

Zitat von Der schöne Günther (Beitrag 1535717)

Ich kann zwar keinen Assemblercode lesen, aber ich würde jetzt Geld wetten dass der Compiler den gleichen Code aus

Delphi-Quellcode:

meinArray[meinePosition] := 42

und irgendeiner wilden Pointer-Arithmetik macht.

Wenn du einen wahlfreien Zugriff hast, dann ist es relativ egal, aber das ist in diesem Fall ja gar nicht gefordert. Hier geht es darum der Reihe nach Werte zu schreiben.

Der Zugriff über den Index beinhaltet dabei immer die Berechnung der Speicherposition, während du bei Verwendung eines Pointers lediglich den Pointer inkrementieren musst. Das bedeutet ca. halb so viele Assemblerbefehle. In manuellem Assembler ginge es denke ich noch besser. Der generierte Code sieht auf den ersten Blick nicht optimal aus.

[Michael II]

Frage: Wenn die Reihe 4 5 2 2 6 1 7 lautet, sollen dann 2 2 als Minima ausgegeben werden oder suchst du (wie in deinem Code) nur nach der 1?

[Michael II]

Zitat:

Zitat von Kishmet (Beitrag 1535628)

Sei mal dahingestellt ob die Funktion so schon gut ist, darum soll es hier nicht gehen, nehme aber natürlich gerne Vorschläge entgegen wie das besser gehen könnte.

Du vergleichst hier jeden Wert immer mit dem links und dem rechts. Du könntest die Anzahl Vergleiche minimieren.

Durchwandere die Liste - wie du es auch tust - von links nach rechts. Merk dir aber, ob du zuletzt aufwärts, abwärts oder gerade marschiert bist.
Solange es aufwärts geht musst du nicht auf Minimum prüfen (da es ja links von dir abwärts geht); solange es abwärts geht auch nicht (da es ja links von dir aufwärts und rechts von dir abwärts geht). Genau dann wenn deine Wanderung von abwärts direkt nach aufwärts wechselt, hast du ein Minimum gemäss deinem Algo gefunden. Ich habe es getestet. Dein Algo benötigt (Compiler:nicht vollständige boolesche Auswertung) im Schnitt mindestens (mindestens, weil es sicher schnelleren Code gibt als meinen) 28% mehr Zeit. Wenn du den Algo in eine Auto- oder Flugzeugsteuerung einbaust lohnt sich eine Anpassung und sonst (O(N) sind öde Probleme ;-)) nicht.