To Wert einer For-Schleife bearbeiten

Floooooo24

Guten Morgen zusammen,

ist es möglich den am Anfang der For-Schleife festegelegten Ziel Wert zu bearbeiten?

Mein Problem ist, das ich ein Array habe, das ich durchsuche und ggf. Zeile lösche. Allerdings nehme ich das als ziel wert.

Gibt es noch andere Wege, als diesen hier:

C

#include <Array.au3>
#include <_Dbug.au3> ;Debugger

Local $aArray[16] = [0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1]
Local $x

_ArrayDisplay($aArray)

For $i = 0 To Ubound($aArray) - 1
    $i -= $x
    If $aArray[$i] = 1 Then
        _ArrayDelete($aArray, $i)
        $i -= 1
        $x += 1
    EndIf
    $i += $x
Next
_ArrayDisplay($aArray)

Alles anzeigen

Micha_he

So pauschal würde ich sagen:

Die FOR-Schleife von hinten durchlaufen (For $i = UBound($aArray) -1 To 0 Step -1) oder

Statt der FOR eine DO-UNTIL-Schleife verwenden:

Code

$i=0
Do
  ...
  $i += 1
Until $i >= UBound($aArray)

Floooooo24

Danke, dachte ich es mir doch das es eine Sinnvollere Lösung gibt

**AspirinJunkie**

Wobei _ArrayDelete da jedesmal alles was dahinter kommt einzeln nach vorne schiebt und das bei jedem Aufruf aufs neue.

Besonders bei großen Arrays mit vielen Löschungen wäre das nicht ideal aus Performance-Sicht.

Eleganter wäre es daher alles gleich in einem Rutsch abzuarbeiten:

AutoIt

#include <Array.au3>

Local $aArray[16] = [0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1]
Local $x = 0

_ArrayDisplay($aArray, "vorher")

For $i = 0 To UBound($aArray) - 1
    If $aArray[$i] = 1 Then ContinueLoop

    $aArray[$x] = $aArray[$i]
    $x += 1
Next
Redim $aArray[$x]
_ArrayDisplay($aArray, "nachher")

Alles anzeigen

Edit: Mit der UDF "ArrayPlus.au3" sähe das ganze übrigens so aus:

AutoIt

#include "ArrayPlus.au3"


Local $aArray[] = [1, "a", 1, "b", "c", "d", 1, 1, "e", "f", 1, "g", "h", "i", 1, "j", 1, "k"]

_ArrayDisplay($aArray, "vorher")

_ArrayDeleteByCondition($aArray, __meine)

_ArrayDisplay($aArray, "nachher")

Func __meine($vEl)
    Return $vEl = 1
EndFunc

Alles anzeigen

Floooooo24

Klingt definitv Sinnvoll, Danke

**Musashi**

Du könntest auch deine For..Next Schleife beibehalten, dann musst Du nur, wie Micha_he bereits schrieb, mit dem letzten Element beginnen.

Code

#include <Array.au3>
Local $aArray[16] = [0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1]
For $i = Ubound($aArray) - 1 To 0 Step -1
    If $aArray[$i] = 1 Then _ArrayDelete($aArray, $i)
Next
_ArrayDisplay($aArray)

**BugFix**

Zitat von Musashi
Du könntest auch deine For..Next Schleife beibehalten, dann musst Du nur, wie Micha_he bereits schrieb, mit dem letzten Element beginnen.
Code
#include <Array.au3>
Local $aArray[16] = [0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1]
For $i = Ubound($aArray) - 1 To 0 Step -1
    If $aArray[$i] = 1 Then _ArrayDelete($aArray, $i)
Next
_ArrayDisplay($aArray)

Jein.

Wenn du _ArrayDelete verwendest, wird jedes mal ein ReDim ausgeführt, sollte man tunlichst vermeiden.

**AspirinJunkie**

Zitat von BugFix

Jein.
Wenn du _ArrayDelete verwendest, wird jedes mal ein ReDim ausgeführt, sollte man tunlichst vermeiden.

Doppel-Jein

_Arraydelete führt lediglich ein verkleinerndes ReDim durch.

~~Hier ist kein umkopieren nötig, so dass dies unerheblich für die Performance ist.~~ (siehe unten)

Das eigentliche "Problem" an dem mehrmaligen ArrayDelete() ist dass er alle Elemente die nach dem zu löschenden kommen eine Position nach vorn verschiebt.

Und das halt jedesmal.

Daher werden diese Elemente zig mal umkopiert anstatt gleich an seine Endposition.

**Musashi**

AspirinJunkie :

Das Problem mit den Verschiebungen bei der Nutzung von _ArrayDelete kenne ich.

Verschärfend im vorliegenden Beispiel ist, dass nur die Werte 0 und 1 vorkommen.

Bei halbwegs ausgewogener Verteilung finden daher sehr viele Verschiebungen statt.

_Timer-Messungen auf meinem älteren PC - wie immer mit etwas Vorsicht zu genießen :

(Werte wurden mit Random (0, 1, 1) erzeugt)

_ArrayDelete (Werte 0 und 1) :

1000 Elemente ca. 1,5 Sekunden

5000 Elemente ca. 30,0 Sekunden

10000 Elemente ca. 140,0 Sekunden

(Die Kurve geht also steil nach oben)

Ein Array aus Werten zwischen 0 und 20 benötigt bei 10000 Elementen z.B. 'nur' noch 18 Sekunden, da es seltener zu Verschiebungen kommt.

Bei kleineren Arrays (bis 500 Elemente +-) ist das meiner Meinung nach noch akzeptabel.

Variante von Aspirinjunkie (Werte 0 und 1) :

10000 Elemente quasi sofort

1000000 Elemente ca. 1,8 Sekunden !!!

Wie erwartet, um Dimensionen schneller .

Wer also häufig und/oder mit größeren Arrays arbeitet, dem sei die UDF von AspirinJunkie ans Herz gelegt.

**Mars**

Zitat von AspirinJunkie

Doppel-Jein
_Arraydelete führt lediglich ein verkleinerndes ReDim durch.
Hier ist kein umkopieren nötig, so dass dies unerheblich für die Performance ist.
Das eigentliche "Problem" an dem mehrmaligen ArrayDelete() ist dass er alle Elemente die nach dem zu löschenden kommen eine Position nach vorn verschiebt.
Und das halt jedesmal.
Daher werden diese Elemente zig mal umkopiert anstatt gleich an seine Endposition.

Alles anzeigen

Ich bin nicht sicher, ob sich das AutoIt-Intern geändert hat, aber kürzlich habe ich jede Menge Timings aufgenommen, und ReDim war eines davon. Und es sieht so aus, als würde ReDim grundsätzlich "alles was danach noch vorhanden ist" kopieren, egal ob man die Größe gleich lässt, vergrößert, oder verkleinert.

AutoIt

; ReDim timing

#include <Array.au3>

$a = Test()
_ArrayDisplay($a)

Func Test()
    Local $aFunctions = [_0, ReDim_Equal_Empty , ReDim_Larger_Empty, ReDim_Smaller_Empty , ReDim_Equal_Full, ReDim_Larger_Full, ReDim_Smaller_Full], $aTimings[UBound($aFunctions)][2], $r
    For $i = 0 To 999 Step 1
        $r = Random(0, UBound($aFunctions) - 1, 1)
        $aTimings[$r][0] += $aFunctions[$r]()
        $aTimings[$r][1] += 1
    Next

    Local $aResult[UBound($aFunctions) - 1][2], $Null = $aTimings[0][0] / $aTimings[0][1]
    For $i = 1 To UBound($aFunctions) - 1 Step 1
        $aResult[$i - 1][0] = FuncName($aFunctions[$i])
        $aResult[$i - 1][1] = ($aTimings[$i][0] / $aTimings[$i][1]) - $Null
    Next
    Return $aResult
EndFunc


; Default
Func _0()
    Local $t = TimerInit()
    $t = TimerDiff($t)
    Return $t
EndFunc

; ReDim ohne Größenänderung (1000 -> 1000), Array ist gefüllt
Func ReDim_Equal_Full()
    Local $a = RandomArray(1000)
    Local $t = TimerInit()
    ReDim $a[1000]
    $t = TimerDiff($t)
    Return $t
EndFunc

; ReDim Verkleinerung um 1, Array ist gefüllt
Func ReDim_Smaller_Full()
    Local $a = RandomArray(1000)
    Local $t = TimerInit()
    ReDim $a[999]
    $t = TimerDiff($t)
    Return $t
EndFunc

; ReDim Vergrößerung um 1, Array ist gefüllt
Func ReDim_Larger_Full()
    Local $a = RandomArray(1000)
    Local $t = TimerInit()
    ReDim $a[1001]
    $t = TimerDiff($t)
    Return $t
EndFunc


; ReDim ohne Größenänderung (1000 -> 1000), Array ist leer
Func ReDim_Equal_Empty()
    Local $a[1000]
    Local $t = TimerInit()
    ReDim $a[1000]
    $t = TimerDiff($t)
    Return $t
EndFunc

; ReDim Verkleinerung um 1, Array ist leer
Func ReDim_Smaller_Empty()
    Local $a[1000]
    Local $t = TimerInit()
    ReDim $a[999]
    $t = TimerDiff($t)
    Return $t
EndFunc

; ReDim Vergrößerung um 1, Array ist leer
Func ReDim_Larger_Empty()
    Local $a[1000]
    Local $t = TimerInit()
    ReDim $a[1001]
    $t = TimerDiff($t)
    Return $t
EndFunc

Func RandomArray($n)
    Local $_[$n]
    For $i = 0 To $n - 1 Step 1
        $_[$i] = Random()
    Next
    Return $_
EndFunc

Alles anzeigen

Das Ergebnis müsste sein, dass alle 3 Versionen (verkleinern, vergrößern, gleichlassen) genausoviel Zeit beanspruchen, obwohl z.B. verkleinern um 1 element intern eigentlich nur "eine einzige integer substraktion" sein sollte und damit im Nanosekundenbereich liegen sollte, genauso wie ein ReDim ohne Größenänderung...

lg

M

**AspirinJunkie**

Mann - eh.
Was soll denn der Blödsinn?
Ja ich kann deine Messung nachvollziehen und hab sie auch mal mit einem eigenen anderen Ansatz verglichen:

AutoIt

Global Const $N = 1e4
Global $iT, $fTime

Global $aArr[0]
$iT = TimerInit()
For $i = 1 To $N
    Redim $aArr[$i]
Next
$fTime = TimerDiff($iT)
ConsoleWrite(StringFormat("% 24s: %10.2f ms\n", "Redim vergrößert", $fTime))


Global $aArr[$N]
$iT = TimerInit()
For $i = $N To 1 Step -1
    Redim $aArr[$i]
Next
$fTime = TimerDiff($iT)
ConsoleWrite(StringFormat("% 20s: %10.2f ms\n", "Redim verkleinert", $fTime))

Global $aArr[$N]
$iT = TimerInit()
For $i = 1 To $N
    Redim $aArr[$N]
Next
$fTime = TimerDiff($iT)
ConsoleWrite(StringFormat("% 20s: %10.2f ms\n", "Redim gleich", $fTime))

Alles anzeigen

Ergebnis: Es ist tatsächlich wurscht ob es ein verkleinerndes oder vergrößerndes ReDim ist.
Nun die Frage: Warum?
Kann mir eigentlich nur noch als Erklärung geben, dass Fragmentierung im Speicher verhindert werden soll und deswegen an einen neuen Bereich kopiert wird.
Ansonsten kann ich das nicht wirklich nachvollziehen warum man da dennoch kopiert.

BugFix : Deine Empfehlung pauschal auf ReDim zu verzichten - egal ob größer oder kleiner ist also - entgegen meiner Aussage - doch richtig.

Hm vielleicht wäre das mal was für den BugTracker oder den technical discussion-Teil im englischen Forum.

**Mars**

Ich bin mir eigentlich auch fast sicher, dass das nicht immer so war, also dass verkleinernde ReDims früher mal deutlich schneller waren. Aber vielleicht bilde ich mir das auch nur ein...

**AspirinJunkie**

Ich überlege mir gerade wie es in C ist.

Also: Ein AutoIt-Array ist ein Pointerarray auf Variant-Strukturen.
Dieses Pointer-Array ist ein klassisches C-Array (kein C++-std::vector oder sowas).

Bei dessen Definition wird im Hintergrund malloc() verwendet um entsprechend Speicher bereitzustellen.

Müsste ich jetzt ein ReDim implementieren, würde ich hierfür realloc() verwenden.

Damit würde im Regelfall bei einer Verkleinerung eben kein Umkopieren notwendig werden.
Im alten AutoIt-Quellcode finde ich aber diese Funktion überhaupt nicht.

Ich müsste mal Zeit nehmen und anschauen wie die die ReDim damals stattdessen implementiert haben.
Ich befürchte, dass die wirklich einfach neu allozieren und eiskalt umkopieren - komme was wolle.

**Mars**

Im alten Code ist das in script_parser.cpp::Parser_Keyword_DIM (1920) mit bReDim = True. In den Kommentaren steht aber, dass ReDim eine eigene Funktion bekommen soll, also wird das nach 10+ Jahren wohl nicht mehr genau so sein wie es dort ist^^

Und so wie ich das dort sehe wird hier ebenfalls ein neues Array angelegt und eine komplette Kopie gemacht (lustigerweise "von Hand", vermutlich weil kein Standardcontainer verwendet wird, also das "Array" ist zusammengesetzt aus einem ->Data Feld (pointerliste auf Variants, also **Variant) und irgendwelchen Extras um die Indices zuzuordnen)...

Edit2: realloc? Wahre Meister verwenden "new"

Edit: In den Code schaue ich immer rein, wenn ich mich gut fühlen will

**AspirinJunkie**

Jetzt weiß ich wo mein Denkfehler lag.
realloc() geht natürlich nur wenn man den Speicherbereich selbst mit malloc() oder calloc() initialisiert hat.

Bei den reinen C-Arrays geht das nicht, dafür kümmert sich aber der Compiler darum, dass der Speicher nach Verwendung schön aufgeräumt wird.

Wöllte man also ein schnelles ReDim implementieren, müsste man die Arraydefinition speicherdynamisch per malloc() umschreiben und hätte dann noch die Aufgabe an der Backe immer schön dafür zu sorgen, dass der Speicher am Ende in jedem Fall per free() wieder freigeräumt wird und auch alle Pointer müssen immer schön nachgezogen werden bei Änderungen.

Das tut Jon sich aus nachvollziehbaren Gründen nicht an, sondern macht es stattdessen einfach per Neudefinition und Umkopieren.

Also: Ich kann nun nachvollziehen warum ein verkleinerndes ReDim ebenso lange dauert und kann mir nicht vorstellen, dass es früher mal anders gewesen sein sollte, da mir keine Möglichkeit bekannt ist ein C-Array ohne umkopieren zu resizen.

Peter S. Taler · *Ab 19-10-22 ergänzt um:*

Wir haben wirklich Fachleute hier - mir jagen manche Lösungen - manchmal Angst ein.

Gehe ich falsch in der Annahme dass die Löung für den TE doch einfach ganz einfach ist.

Nämlich eine Variable einzusetzen statt einen festen Wert? die Variable kann man befüllen wie man will? Sei es mit der "Länge" des Arrays als auch mit jeder anderen Zahl?

Wenn ich mir vorstelle als Anfänger Eure Antworten? Bitte versteht mich nicht falsch - mir ist klar, das ist eine Diskussion unter Mitgliefern die Ihr Handwerk 1A verstehen - aber ist dem TE damit geholfen?

LG

Peter

**AspirinJunkie**

Zitat von Peter S. Taler

Gehe ich falsch in der Annahme dass die Löung für den TE doch einfach ganz einfach ist.

Nämlich eine Variable einzusetzen statt einen festen Wert?

Wenn man genau liest stellt man fest, dass dies gar nicht seine eigentliche Frage ist - sein tatsächliches Problem ist ein ganz anderes.
Sein wirkliches Ziel ist es nicht die Loopgrenze während des Loops dynamisch zu halten sondern er möchte eigentlich nur mehrere Elemente aus einem Array herausfiltern - nicht mehr und nicht weniger.

Um dieses Ziel zu erreichen stieß er mit seinem Ansatz auf das Problem, dass die Arraygrenze nach dem ersten _ArrayDelete nicht mehr passte und ging daher - nachvollziehbar - davon aus, dass die Lösung all seiner Probleme darin besteht die Bereichsgrenze dynamisch während des Loops anzupassen.

Aber eigentlich war das ja gar nicht sein eigentliches Ziel, sondern lediglich ein Zwischenschritt für seine vermeintliche Lösung.

Das Grundproblem bestand weiterhin nur daraus mehrere Elemente aus einem Array zu löschen.

Wir haben hier also den Prototypen eines XY-Problems.

Daher wurde ihm anstatt die gestellte Frage zu bearbeiten, Möglichkeiten gezeigt um sein tatsächliches Problem effizienter über andere Ansätze zu lösen.

BananaJoe

Zitat von AspirinJunkie

..., dass der Speicher am Ende in jedem Fall per free() wieder freigeräumt wird ...

das machen jetzt angeblich die modernen Betriebssysteme von selbst.

Ich habe noch gelernt, auf jeden fall free() zu verwenden und auch mit valgrind zu prüfen, ob das alles sauber erfolgt ist - aber das ist scheinbar mittlerweile überholt

**Kanashius**

Zitat von BananaJoe

das machen jetzt angeblich die modernen Betriebssysteme von selbst.

Das würde mich aber sehr wundern. Ja, das Betriebssystem weiß, welcher Arbeitsspeicher zu deinem Programm gehört und räumt am Programm-Ende den Speicher auf und gibt ihn frei, genauso wie es ihn erweitert, wenn das Programm mehr Speicher benötigt.

Das ersetzt aber keinesfalls die Verwendung von free(). Wenn du free() nicht verwendest verbraucht dein Programm mehr und mehr RAM und gibt ihn nicht wieder frei. Daran ändert das Betriebssystem nichts. Valgrind ist nur ein Tool, um zu schauen, ob du allokierten Speicher wieder freigibst um sicherzugehen, dass dein Programm nicht immer mehr RAM verbraucht (bis es irgendwann abstürzt).

Einige Programmiersprachen arbeiten aber tatsächlich mittlerweile ohne free() und theoretisch auch ohne malloc,... .

Java, C#, Python,... z.B. haben einen Garbagecollector. Der läuft immer wieder zwischendurch über das Programm drüber und checkt, welche Variablen nicht mehr Referenziert sind und gibt den Speicher frei.

Andere wie z.B. Rust, C++ (teilweise),... arbeiten mit Scopes. Variablen sind nur in nem bestimmten Scope gültig und werden danach automatisch wieder freigegeben. Das sorgt dafür, dass Programmierer sich nicht selbst darum kümmern müssen (=> weniger fehlende free()). Rust ist z.B. sehr explizit, wie du Daten in einen anderen Scope geben kannst,... und es ist quasi unmöglich dort Variablen nicht freizugeben (ausgenommen mit code, der als unsafe markiert ist).

Garbage collectoren verbrauchen CPU Zeit, gehen also auf die Performance und sind auch Speicherintensiver (Referenz counter,...). Scope basierte Lösungen verbrauchen minimal mehr Compilezeit, haben aber keine extra Kosten zur Laufzeit.

Also nein, wenn man nicht gerade Programmiersprachen verwendet, die das Problem anders lösen, muss man immer noch selbst den Speicher verwalten. Das Betriebssystem kümmert sich nicht um die Speicherverwaltung deines Programmes. Es behält nur im Auge, wie viel Speicher du brauchst, wieder freigibst und übernimmt den Speicher des Programmes am Ende der Laufzeit wieder.

**AspirinJunkie**

Zitat von BananaJoe

das machen jetzt angeblich die modernen Betriebssysteme von selbst.

Hast du da vielleicht bisschen mehr Infos dazu?
Im Prinzip kann das ja nur so laufen, dass das Betriebssystem für den Pointer einen Zähler hinzufügt und schaut wenn es keine Referenzen mehr auf den Speicherbereich gibt.
Also im Grunde genau sowas wie die Pointer-Klassen std::shared_ptr oder std::unique_ptr in C++.

Das stelle ich mir aber etwas schwierig auf Betriebssystemebene vor - auf Compilerebene o.k. - der kann Pointer entsprechend konvertieren aber das BS muss halt wirklich wissen, dass an dieser Stelle im Speicher halt wirklich der Pointer für den Speicherbereich steht und nicht irgendetwas anderes.
Nur vom Variablenwert kann man auch nicht ausgehen, da es theoretisch möglich ist weiterhin den dynamischen Speicher per Pointerarithmetik zu verwalten.

Also wenn du da was hättest zum lesen wäre das prima.

Zitat von Kanashius

Einige Programmiersprachen arbeiten aber tatsächlich mittlerweile ohne free() und theoretisch auch ohne malloc,... .

Äh ja - im Grunde alle.
Die dynamische Speicherallozierung ist ja eher der Sonderfall.
Auch in C musst du bei der normalen Variablen-, bzw. Array-Definition nichts händig freigeben.
Das wird automatisch erledigt, sobald der Scope der Variable verlassen wird.

Ganz unten arbeiten aber weiterhin alle Programmiersprachen mit malloc und free (bzw. deren Windows-API-Entsprechungen HeapAlloc() und HeapFree()).

Die Compiler etc. setzen nur das free an bestimmten Stellen automatisch, wie z.b. bei Scope-Enden oder im Garbage-Collector, wenn der Referenzzähler auf 0 fällt usw.

Nur bei der manuellen Speicherallozierung muss man sich selbst darum kümmern.