Beiträge von AspirinJunkie
-
-
Ich möchte eine Reihe eines dynamischen erstellen Arrays direkt adressieren. (Thematitel)
"Dynamisch erstellt" - wie? woher?
Ergebnis?Ich habe ein 1-D-Array. Jede Zeile ist eine Reihe im Array.
Zeilen in einem 1D-Array?
Was ist mit der unterschiedlichen Begrifflichkeit Reihe vs. Zeile gemeint? (subjektiv das selbe)Gibt es eine Möglichkeit eine Reihe anzusprechen, und zwar nicht mit $aArray[1400] sondern mit $aArray[$x] wobei dann $x eine beliebige Zahl ist?
Klar - genauso wie du es hingeschrieben hast.
In Autohotkey gibt es zumindest die Möglichkeit, den aktuellen Index des Arrays auszugeben, dass würde mir schon reichen.
Was meinst du mit aktuell?
Du bestimmst doch wo du dich im Array befindest - ergo kennst du den Index sowieso schon. Z.B. in der For-To-Schleife.
Oder iterierst du über eine For-In-Schleife?Nochmal zusammengefasst: Je unkonkreter du fragst umso unkonkreter können wir dir helfen (falls auf dem Weg zum konkreten dabei nicht die Lust verloren geht).
-
Weißt du was das X-Y-Problem ist?
Es tritt sehr häufig in Foren wie diesem auf und man kann es ungefähr so beschreiben:- Ein User möchte X erreichen.
- Er glaubt die Lösung des Problems wäre Y.
- Da es dabei Probleme gibt stellt er eine Frage Y betreffend aber ohne X zu erwähnen.
- Auch wenn für die Helfenden Y ziemlich schräg erscheint bemühen sich alle irgendwie Y hinzubiegen.
- Effektiver wäre es aber gewesen die Fragestellung von Anfang an anders zur formulieren: Ich möchte X erreichen dazu habe ich schon Y probiert aber noch immer nicht das gewünschte erreicht.
Dein Y ist die variable Indizierung eines Arrays.
Dein X kennen wir hingegen noch nicht.Es würde uns (und damit dann vor allem dir) sehr viel helfen wenn du das eigentliche Grundproblem mal darlegst und dein wirkliches Ziel dazu mal formulierst.
Ich habe hier nämlich bisschen Probleme das eigentliche Problem herauszuarbeiten.
Was ist z.B. mit "Array variabel aus dem Zwischenspeicher" erstellen exakt gemeint?
Wie sieht das Array aus? - was soll mit ihm gemacht werden?
Was meinst du nun mit aktueller Index? In dem Beispiel von dir ist i (auch wenn syntaktisch noch das "$" fehlt) der aktuelle Index während $aktuellerIndex den Inhalt an dieser Stelle enthält. -
Sowas?:
SQLSELECT boxid AS ID, boxname as Name FROM box JOIN box_item USING (boxid) JOIN item USING(itemid) WHERE itemid IN (1, 3) GROUP BY boxid HAVING Count(itemid) = 2;Hinter das In kommen in Klammern die möglichen Item-IDs.
Und das Count ganz unten muss die selbe Anzahl haben wie Elemente in der In-Anweisung.Edit: Alternative:
SQLSELECT boxid AS ID, boxname as Name FROM box JOIN box_item USING (boxid) JOIN item USING(itemid) GROUP BY boxid HAVING COUNT(itemid NOT IN (1, 2) OR NULL) = 0 AND COUNT(itemid) = 2Hinter das NOT IN kommen die itemids, hinter das Count(itemid) kommt die Anzahl der gesuchten itemids.
Edit 2: Und noch ne Alternative:
SQLSELECT boxid AS ID, boxname as Name FROM box JOIN box_item USING (boxid) JOIN item USING(itemid) GROUP BY boxid HAVING group_concat(itemid, ",") = "1,2"Hier werden die itemids als String eingetragen.
Eventuell wäre ein Order by innerhalb des group_concat notwendig.
Dieses wäre in MySQL z.B. möglich in Sqlite hingegen nicht.
Hier geht es also dann schon langsam um die Frage welches DBMS Verwendung finden soll. -
-
deshalb suche ich nach einer funktion, die das array erstmal bei einer größe von 1 startet, und jedes mal wenn ein neuer wert erkannt wird, wird die arraygröße um 1 erweitert.
Aus der AutoIt-Hilfe: _ArrayAdd()
Zum Sinn/Unsinn des ganzen siehe die Argumente vorher. -
Und wenn ich das nun per F5 laufen lasse, dann bekomme ich immer eine '0', egal ob es den Text irgendwo gibt oder nicht
Dann kommt kein Fenster in den Vordergrund(! - wichtig - nicht die bloße Existenz eines solchen Fensters reicht - es muss auch in den Vordergrund) in dem der Text "Setup is complete" als Visible-Text vorhanden ist.
Hier mal ein kurzes Video, welches zeigt, dass das Skript prinzipiell funktioniert: http://ge.tt/5YVpG6h2 -
Dein Programmcode besteht wirklich nur aus dieser Zeile?
Du startest das Skript und innerhalb der 5-Sekundenfrist bringst du ein Fenster mit dem Text "fseafs" bzw. "'Setup is complete'" in den Vordergrund (also das Fenster wird aktiv) welches nicht das Scite-Fenster ist.Dennoch erschein eine 0?
-
Wenn das so ist, dann müsste ich es ja hinbekommen wenn ich das Script anders ausführe, also ohne das der Editor offen ist. Da ich absoluter Anfänger was AutoIT ist, weiß ich nicht genau wie ich das anstellen soll?
Irgendwie kompilieren und dann laufen lassen oder so ähnlich?Bingo. Skript kompilieren. Scite schließen (oder dafür sorgen, dass es nicht in den Vordergrund rückt). Die exe starten und fertig.
Alternativ könntest du auch das Scite-Fenster von der Suche ausnehmen.
Z.B. so (etwas krude Methode sollte aber funktionieren): -
Na klar bekommst du eine 1.
Es gibt doch ein aktives Fenster in dem der Text "fseafs" vorkommt - dein Scite-Fenster!
Es ist aktiv da du das Skript aus diesem heraus startest und es enthält den Text "fseafs" da es ja im Editor für den Programmcode steht. -
-
Welche Codezeile?
Wie exakt geändert? -
Tja die Setups.ini konnte halt nicht korrekt gelesen werden.
Mögliche Fehlerquellen:
- Falscher Dateiname ("Setups.ini" vs. "Setup.ini")
- Kein Zugriffsrechte auf die Datei
- Falscher Pfad z.B. wenn das Working-Directory ein anderes als das Skriptverzeichnis ist.
- Section oder Schlüssel existieren in der Ini-Datei nicht.
-
@UEZ
Ähnlicher Ansatz wie bei mir aber meine Version kommt im Gegensatz zu dieser Lösung auch mit escapeten (durch Dopplung) Anführungszeichen innerhalb einer Anführungszeichengruppe klar. -
Vielleicht auch interessant:
AutoIt#include <Array.au3> Global $s_String = '"AHI_";;;;"Apnoe-Hypopnoe-Index";;;;;;;;;"";"Apnoe-Hypopnoe-Index $m1\c:FF\____$m0\c:-\/Stunde [normal: >5; Störungen: „mild“: AHI 5-15,\r„moderat“: AHI 15-30, schwer“: AHI > 30/Stunde nach der Amerikanischen Gesellschaft für Schlafmedizin (AASM)].$m0";"";"";"";"";"";"GKIRSCH";FALSE;FALSE;FALSE;TRUE;FALSE;FALSE;"";FALSE;""' $a_Splitted = StringSplit(StringRegExpReplace($s_String, ';(?=([^"]*"[^"]*")*[^"]*$)', @CR), @CR, 2) _ArrayDisplay($a_Splitted)setzt allerdings voraus dass alle Anführungszeichen komplett ausbalanciert sind. (Einzelne durch Dopplung auskommentierte Anführungszeichen innerhalb von Anführungszeichen würden nicht mehr klappen)
-
Sleep() ist blockierend und deine Hotkeys werden erst ausgeführt wenn die Sleep() Funktion beendet wird.
Sicher?:
-
Auch der von mir hier verwendete Quick-Select hat noch deutliches Optimierungspotential. Das dürfte sich allerdings erst bei sehr großen Arrays und ungewöhnlichen Elementanordnungen bemerkbar machen.
Aktuell handelt es sich um einen Quick-Select der per Hoare partiniert und das Pivot-Element als Median des ersten, mittleren und letzten Elementes auswählt.
Hoare ist schon ganz gut aber bei der Auswahl des Pivot-Elementes kann man noch bisschen was rausholen. Wer da Lust hat kann sich ja mal an Introselect oder dem Floyd-Rivest Algorithmus machen.Auch hatte ich ganz kurz überlegt ähnlich wie bei QuickSort auf einen Zwei-Pivot Algorithmus umzuschwenken. Nennt sich dann Dual Pivot QuickSelect. Gibt auch ziemlich aktuelle Paper dazu. Allerdings siegte die Vernunft dann ziemlich schnell. Habe sowas schonmal bei meiner Sortierfunktion in der DynArray-UDF implementiert und bin mir daher sicher das ich mir das nicht nochmal antue

Aber wer unbedingt auf Teufel komm raus noch ein paar Prozente rauskitzeln will (und sei es nur in der Theorie bei der Laufzeitanalyse anstatt in der Praxis) der kann sich gerne daran versuchen.
Edit:
diese mit Swapsort (Weil man den für kleine Arrays gut hardcoden kann, sodass man keine Schleifen oder ähnliches hat) sortieren
Wenn man auf Spezialfallebene weiter optimieren will ist dein Hinweis echt gut.
Hab mir mal angeschaut, was es ausmacht 5 Elemente per Abfragen zu sortieren statt per Insertion-Sort (welcher bei der Größe der schnellste Algorithmus sein sollte).
Und siehe da:AutoIt
Alles anzeigen#include <Array.au3> Global Const $N = 50000 Global $f_DecimalPlaces = 5 Global $iT, $f_Overhead, $a_Results[0][3] Global $a_Array[5] ; determine the overhead of loop [and optional other stuff] $iT = TimerInit() For $i = 1 To $N For $j = 0 To 4 $a_Array[$j] = Random(1, 100, 1) Next Next $f_Overhead = TimerDiff($iT) ; the first measurement ReDim $a_Results[UBound($a_Results) + 1][3] $a_Results[UBound($a_Results) - 1][0] = "_5Sort" $iT = TimerInit() For $i = 1 To $N For $j = 0 To 4 $a_Array[$j] = Random(1, 100, 1) Next _5Sort($a_Array[0], $a_Array[1], $a_Array[2], $a_Array[3], $a_Array[4]) Next $iT = TimerDiff($iT) $a_Results[UBound($a_Results) - 1][1] = ($iT - $f_Overhead) / $N ; the first measurement ReDim $a_Results[UBound($a_Results) + 1][3] $a_Results[UBound($a_Results) - 1][0] = "__5Sort" $iT = TimerInit() For $i = 1 To $N For $j = 0 To 4 $a_Array[$j] = Random(1, 100, 1) Next __5Sort($a_Array) Next $iT = TimerDiff($iT) $a_Results[UBound($a_Results) - 1][1] = ($iT - $f_Overhead) / $N ; the third measurement ReDim $a_Results[UBound($a_Results) + 1][3] $a_Results[UBound($a_Results) - 1][0] = "ISort" $iT = TimerInit() For $i = 1 To $N For $j = 0 To 4 $a_Array[$j] = Random(1, 100, 1) Next _ISort($a_Array) Next $iT = TimerDiff($iT) $a_Results[UBound($a_Results) - 1][1] = ($iT - $f_Overhead) / $N ; calculate results and print them out _ArraySort($a_Results, 0, 0, 0, 1) For $i = 0 To UBound($a_Results) - 1 $a_Results[$i][2] = Round($a_Results[$i][1] / $a_Results[0][1], 2) $a_Results[$i][1] = Round($a_Results[$i][1], $f_DecimalPlaces) Next _ArrayDisplay($a_Results, "Measurement Results", "", 16 + 64, Default, "name|time [ms]|factor") Func _ISort(ByRef $A) Local $t1, $t2 For $i = 1 To UBound($A) - 1 $t1 = $A[$i] For $j = $i - 1 To 0 Step -1 $t2 = $A[$j] If $t1 > $t2 Then ExitLoop $A[$j + 1] = $t2 Next $A[$j + 1] = $t1 Next EndFunc ;==>_ISort ;~ Global $B[] = [3, 1, 2, 5, 4] ;~ __5Sort($B) ;~ _ArrayDisplay($B) Func __5Sort(ByRef $A) Local $t If $A[0] < $A[1] Then ; if a < b: a, b = b, a $t = $A[1] $A[1] = $A[0] $A[0] = $t EndIf If $A[2] < $A[3] Then ; if c < d: c, d = d, c $t = $A[2] $A[2] = $A[3] $A[3] = $t EndIf If $A[0] < $A[2] Then ; if a < c: a, b, c, d = c, d, a, b $t = $A[2] $A[2] = $A[0] $A[0] = $t $t = $A[3] $A[3] = $A[1] $A[1] = $t EndIf If $A[4] < $A[2] Then ;~ if e < c: If $A[4] > $A[3] Then ; if e > d: d, e = e, d $t = $A[3] $A[3] = $A[4] $A[4] = $t EndIf ElseIf $A[4] < $A[0] Then ; if e < a: c, d, e = e, c, d $t = $A[2] $A[2] = $A[4] $A[4] = $A[3] $A[3] = $t Else ;~ else: a, c, d, e = e, a, c, d $t = $A[0] $A[0] = $A[4] $A[4] = $A[3] $A[3] = $A[2] $A[2] = $t EndIf If $A[1] < $A[3] Then ; if b < d: If $A[1] < $A[4] Then ; if b < e: return b, e, d, c, a Local $B[5] = [$A[1], $A[4], $A[3], $A[2], $A[0]] $A = $B Else ; else: return e, b, d, c, a Local $B[5] = [$A[4], $A[1], $A[3], $A[2], $A[0]] $A = $B EndIf Else If $A[1] < $A[2] Then ; if b < c: return e, d, b, c, a Local $B[5] = [$A[4], $A[3], $A[1], $A[2], $A[0]] $A = $B Else ; else: return e, d, c, b, a Local $B[5] = [$A[4], $A[3], $A[2], $A[1], $A[0]] $A = $B EndIf EndIf EndFunc ;==>_5Sort ;~ Global $X[] = [5, 3, 4, 2, 1] ;~ _5Sort($X[0], $X[1], $X[2], $X[3], $X[4]) ;~ _ArrayDisplay($X) Func _5Sort(ByRef $A, ByRef $B, ByRef $C, ByRef $D, ByRef $E) Local $t, $t2 If $A < $B Then ; if a < b: a, b = b, a $t = $B $B = $A $A = $t EndIf If $C < $D Then ; if c < d: c, d = d, c $t = $C $C = $D $D = $t EndIf If $A < $C Then ; if a < c: a, b, c, d = c, d, a, b $t = $C $C = $A $A = $t $t = $D $D = $B $B = $t EndIf If $E < $C Then ;~ if e < c: If $E > $D Then ; if e > d: d, e = e, d $t = $D $D = $E $E = $t EndIf ElseIf $E < $A Then ; if e < a: c, d, e = e, c, d $t = $C $C = $E $E = $D $D = $t Else ;~ else: a, c, d, e = e, a, c, d $t = $A $A = $E $E = $D $D = $C $C = $t EndIf If $B < $D Then ; if b < d: If $B < $E Then ; if b < e: return b, e, d, c, a $t = $A $A = $B $B = $E $E = $t $t = $C $C = $D $D = $t Else ; else: return e, b, d, c, a $t = $A $A = $E $E = $t $t = $C $C = $D $D = $t EndIf Else If $B < $C Then ; if b < c: return e, d, b, c, a $t = $A $A = $E $E = $t $t = $B $B = $D $D = $C $C = $t Else ; else: return e, d, c, b, a $t= $A $A = $E $E = $t $t = $B $B = $D $D = $t EndIf EndIf EndFunc ;==>_5SortEs geht also auf der Ebene noch was.
Eher interessant für meine Sortierfunktion aber wollte es dennoch -
Danke für den Hinweis.
Das Pivot-Elemement lag noch im falschen Bereich. Ein ">" in ein "<" geändert und schon sollte es wieder klappen:AutoIt
Alles anzeigen#include <Array.au3> For $i = 0 To 9 Step 1 Test() Next Func Test() Local $sDump = '' Local $a = RandomNumbers(10) Local $QS = __Quicksort($a, 5) Local $AS = _ArrayGetNBiggestElements($a, 5) For $i = 0 To UBound($QS) - 1 Step 1 If $QS[$i] <> $AS[$i] Then $sDump &= Hex($i, 8) & '|' Next If $sDump Then $sDump = StringTrimRight($sDump, 1) If $sDump Then ConsoleWrite(@CRLF & ' Array[' & StringFormat('%3d', UBound($a)) & ']' & @CRLF) For $i = 0 To UBound($a) - 1 Step 1 ConsoleWrite('! ' & StringFormat('%.17f', $a[$i]) & @CRLF) Next ConsoleWrite(@CRLF & ' Quicksort[' & StringFormat('%3d', UBound($QS)) & '] | Aspirin02[' & StringFormat('%3d', UBound($AS)) & ']' & @CRLF) For $i = 0 To UBound($QS) - 1 Step 1 ConsoleWrite((StringInStr($sDump, Hex($i, 8), 0, 1) ? '! ' : '+ ') & StringFormat('%.17f', $QS[$i]) & ' | ' & StringFormat('%.17f', $AS[$i]) & @CRLF) Next ConsoleWrite(@CRLF) Exit EndIf EndFunc ;==>Test ;~ Global $a_Array[] = [2, 6, 8, 1, 1, 5, 8, 9, 31, 41, 163, 13, 67, 12, 74, 17, 646, 16, 74, 12, 35, 98, 12, 43] ;~ Global $N = 5 ;~ $a_Biggest = _ArrayGetNBiggestElements($a_Array, $N) ;~ _ArrayDisplay($a_Biggest, "Die " & $N & " größten Elemente im Array") Func _ArrayGetNBiggestElements($a_A, $d_Nth = 1) ; by AspirinJunkie Local $i_Min = 0, $i_Max = UBound($a_A) - 1 If $d_Nth = $i_Max + 1 Then _ArraySort($a_A, 1) Return $a_A EndIf Do Local $iMiddle = Floor(($i_Max + $i_Min) / 2) Local $a = $a_A[$i_Min], $b = $a_A[$i_Max], $c = $a_A[$iMiddle] ; calculate the pivot element by median(Array[min], Array[middle], Array[max]) Local $p_Value = $a > $b ? $a > $c ? $c > $b ? $c : $b : $a : $a > $c ? $a : $c > $b ? $b : $c ; = Median(a,b,c) Local $p_Index = $p_Value = $a ? $i_Min : $p_Value = $b ? $i_Max : $iMiddle ; = Index(p_Value) ; move the pivot-element to the end of the array If $p_Index < $i_Max Then $a_A[$p_Index] = $a_A[$i_Max] $a_A[$i_Max] = $p_Value EndIf ; Partition with Hoare's algorithm: Local $i = $i_Min - 1 Local $j = $i_Max + 1 Local $t Do ; start from right and go left until the next element which is greater than pivot: Do $j -= 1 Until $a_A[$j] > $p_Value Or $j = $i_Min ; start from left and go right until the next element which is smaller than pivot: Do $i += 1 Until $a_A[$i] < $p_Value Or $i = $i_Max ; swap if elements are on the wrong side of the lists If $i < $j Then $t = $a_A[$j] $a_A[$j] = $a_A[$i] $a_A[$i] = $t EndIf Until $i >= $j ; swap with pivot-element if pivot is at the wrong list-side: If $a_A[$i] < $p_Value Then $a_A[$i_Max] = $a_A[$i] $a_A[$i] = $p_Value EndIf If $i = $d_Nth Then If $d_Nth > 16 Then _ArraySort($a_A, 1, 0, $d_Nth) Else Local $t1, $t2 ; sort with insertion sort (faster than Quicksort for small element count) For $i = 1 To $d_Nth - 1 $t1 = $a_A[$i] For $j = $i - 1 To 0 Step -1 $t2 = $a_A[$j] If $t1 < $t2 Then ExitLoop $a_A[$j + 1] = $t2 Next $a_A[$j + 1] = $t1 Next EndIf ReDim $a_A[$d_Nth] Return $a_A ElseIf $i > $d_Nth Then $i_Max = $i - 1 Else $i_Min = $i + 1 EndIf Until 0 EndFunc ;==>_ArrayGetNBiggestElements Func RandomNumbers($iCnt = 1) Local $aArray[$iCnt] For $i = 0 To $iCnt - 1 Step 1 $aArray[$i] = Random() Next Return $aArray EndFunc ;==>RandomNumbers Func __Quicksort($aArray, $iSubSetSize = 1) _ArraySort($aArray, 1) ; Rocket Science ReDim $aArray[$iSubSetSize] ; Oberen Teil abschneiden, fertig. Return $aArray EndFunc ;==>__Quicksort
OT: Super Testskript - da macht debuggen Spaß
-
Wenn man das ganze als Spezialfall behandelt kann man noch bisschen was rausholen.
Z.B. indem man absteigend partitioniert und sortiert damit man einfach per ReDim das Ergebnis bekommt.
Sieht dann z.B. so aus:AutoIt
Alles anzeigen#include <Array.au3> Global $a_Array[] = [2, 6, 8, 1, 1, 5, 8, 9, 31, 41, 163, 13, 67, 12, 74, 17, 646, 16, 74, 12, 35, 98, 12, 43] Global $N = 5 $a_Biggest = _ArrayGetNBiggestElements($a_Array, $N) _ArrayDisplay($a_Biggest, "Die " & $N & " größten Elemente im Array") Func _ArrayGetNBiggestElements($a_A, $d_Nth = 1) ; by AspirinJunkie Local $i_Min = 0, $i_Max = UBound($a_A) - 1 If $d_Nth = $i_Max + 1 Then _ArraySort($a_A, 1) Return $a_A EndIf Do Local $iMiddle = Floor(($i_Max + $i_Min) / 2) Local $a = $a_A[$i_Min], $b = $a_A[$i_Max], $c = $a_A[$iMiddle] ; calculate the pivot element by median(Array[min], Array[middle], Array[max]) Local $p_Value = $a > $b ? $a > $c ? $c > $b ? $c : $b : $a : $a > $c ? $a : $c > $b ? $b : $c ; = Median(a,b,c) Local $p_Index = $p_Value = $a ? $i_Min : $p_Value = $b ? $i_Max : $iMiddle ; = Index(p_Value) ; move the pivot-element to the end of the array If $p_Index < $i_Max Then $a_A[$p_Index] = $a_A[$i_Max] $a_A[$i_Max] = $p_Value EndIf ; Partition with Hoare's algorithm: Local $i = $i_Min - 1 Local $j = $i_Max + 1 Local $t Do ; start from right and go left until the next element which is smaller than pivot: Do $j -= 1 Until $a_A[$j] > $p_Value Or $j = $i_Min ; start from left and go right until the next element which is greater than pivot: Do $i += 1 Until $a_A[$i] < $p_Value Or $i = $i_Max ; swap if elements are on the wrong side of the lists If $i < $j Then $t = $a_A[$j] $a_A[$j] = $a_A[$i] $a_A[$i] = $t EndIf Until $i >= $j ; swap with pivot-element if pivot is at the wrong list-side: If $a_A[$i] > $p_Value Then $a_A[$i_Max] = $a_A[$i] $a_A[$i] = $p_Value EndIf If $i = $d_Nth Then If $d_Nth > 16 Then _ArraySort($a_A, 1, 0, $d_Nth) Else ; sort with insertion sort (faster than Quicksort for small element count) For $i = 1 To $d_Nth $t1 = $a_A[$i] For $j = $i - 1 To 0 Step -1 $t2 = $a_A[$j] If $t1 < $t2 Then ExitLoop $a_A[$j + 1] = $t2 Next $a_A[$j + 1] = $t1 Next EndIf ReDim $a_A[$d_Nth] Return $a_A ElseIf $i > $d_Nth Then $i_Max = $i - 1 Else $i_Min = $i + 1 EndIf Until 0 EndFunc ;==>_ArrayGetNBiggestElements@UEZ
Bei der Variante wird das Array sortiert und dann der entsprechende Eintrag zurückgegeben.
Hier suchen wir jedoch nach einer Variante welche eben ohne Sortierung auskommt und somit schneller arbeiten soll. -
Na dann ich mal.
Hab meinen erwähnten Ansatz mal mit Hilfe meiner DynArray-UDF umgesetzt.
Wenn ich das Testskript von oben richtig verstanden habe müsste ich es dann folgendermaßen in die Platzhalterfunktion einbauen:AutoIt
Alles anzeigen#include <Array.au3> #include <DynArray.au3> Global $bErrCheck = False ; Nur für "kleine" Runden einschalten, sonst wird die Konsole überflutet falls Fehler auftreten. Global $iSmooth = 0 ; Nur falls man die Ergebnisse Plotten will und keine Lust hat so viele Versuche zu machen bis die Kurve halbwegs glatt ist. ;~ Func Test($iStart = 10, $iEnd = 15, $iSubSetSize = 3, $iVersuche = 25) Global $aTest = Test(150, 400, 150, 1) For $x = 0 To UBound($aTest) - 1 Step 1 For $y = 0 To UBound($aTest, 2) - 1 Step 1 $aTest[$x][$y] = StringReplace($aTest[$x][$y], '.', ',', 0, 1) Next Next _ArrayDisplay($aTest, '', '', 0, @TAB) Func Runde($iArraySize = 100, $iSubSetSize = 5, $iVersuche = 25) ; $iArraySize - Größe des zu untersuchenden Arrays ; $iSubSetSize - Anzahl der gesuchten Werte ; $iVersuche - Anzahl durchgänge aus denen der Mittelwert gebildet wird (um die Laufzeit besser analysieren zu können) ; Runde() lässt die Funktionen einige Male mit gleichen Einstellungen laufen. ; Return - Array mit der Durchschnittlichen Zeit in Millisekunden für jede Funktion. Local $aTime[4][2] ; Beim Hinzufügen die Arraygröße anpassen. $aTime[0][0] = 'Mars 01' ; Arraysort + Redim... easy $aTime[1][0] = 'Platzhalter' $aTime[2][0] = 'Mars 03' $aTime[3][0] = 'Mars 04' Local $aResult[UBound($aTime)], $aCheck, $t, $s, $aTest For $i = 1 To $iVersuche Step 1 $aTest = RandomNumbers($iArraySize) ; Die Funktionen dürfen das Originalarray nicht verändern. Daher muss es nur 1x erzeugt werden. ;~ _ArrayDisplay($aTest) Switch Random(0, 1, 1) ; Da man nie weiß was AutoIt intern betreibt kann es sein, dass Funktionen standardmäßig je nach Position im Code Case 0 ; schneller oder langsamer laufen. Daher ist an dieser Stelle ein Switch um die Reihenfolgen durchzumischen. $t = TimerInit() $aResult[0] = __Mars01($aTest, $iSubSetSize) $aTime[0][1] += TimerDiff($t) $t = TimerInit() $aResult[1] = Platzhalter($aTest, $iSubSetSize) $aTime[1][1] += TimerDiff($t) $t = TimerInit() $aResult[2] = __Mars03($aTest, $iSubSetSize) $aTime[2][1] += TimerDiff($t) $t = TimerInit() $aResult[3] = __Mars04($aTest, $iSubSetSize) $aTime[3][1] += TimerDiff($t) Case 1 $t = TimerInit() $aResult[3] = __Mars04($aTest, $iSubSetSize) $aTime[3][1] += TimerDiff($t) $t = TimerInit() $aResult[2] = __Mars03($aTest, $iSubSetSize) $aTime[2][1] += TimerDiff($t) $t = TimerInit() $aResult[1] = Platzhalter($aTest, $iSubSetSize) $aTime[1][1] += TimerDiff($t) $t = TimerInit() $aResult[0] = __Mars01($aTest, $iSubSetSize) $aTime[0][1] += TimerDiff($t) EndSwitch ; Überprüfen ob alle das gleiche raushaben. If $bErrCheck Then For $e = 0 To UBound($aResult) - 1 Step 1 $aCheck = $aResult[$e] $s = 0 For $o = 0 To UBound($aCheck) - 1 Step 1 $s += $aCheck[$o] Next $aResult[$e] = $s ; $aResult ist nur noch die Summe aller Elemente -> Einfacher zu vergleichen und nahezu genauso aussagekräftig. Next ; Dann wird nicht überprüft ob die Resultatliste Sortiert vorliegt, das ist aber zweitrangig. For $e = 1 To UBound($aResult) - 1 Step 1 ; Wir nehmen mal an, dass Quicksort IMMER richtig liegt (ist immerhin milliardenfach erprobt diese Methode) If $aResult[0] <> $aResult[$e] Then ConsoleWrite('!ERROR: ' & '[' & StringFormat('%5s', $iArraySize) & '|' & StringFormat('%4s', $iSubSetSize) & '] ' & $aTime[$e][0] & (Random(0, 1, 1) ? (Random(0, 1, 1) ? ' hat groben Unfug gebaut.' : ' hat keine Ahnung von Mathe.') : (Random(0, 1, 1) ? ' macht seinen verdammten Job nicht.' : ' steht in der Ecke und weint.')) & @CRLF) Next EndIf Next For $i = 0 To UBound($aTime) - 1 Step 1 $aTime[$i][1] /= $iVersuche Next Return $aTime EndFunc ;==>Runde #Region - Funktionen Func Platzhalter($aArray, $iSubSetSize = 1) Local $i_Pos = UBound($aArray) - $iSubSetSize _ArrayGetNthBiggestElement($aArray, $i_Pos) _ArraySort($aArray, 1, $i_Pos, UBound($aArray) - 1) Local $a_Ret[$iSubSetSize] Local $x = 0 For $i = $i_Pos To $i_Pos + $iSubSetSize - 1 $a_Ret[$x] = $aArray[$i] $x += 1 Next Return $a_Ret ; Das hier dient nur als Beispiel. EndFunc ;==>Platzhalter Func __Mars04($aArray, $iSubSetSize = 1) $iSubSetSize += 1 ; Weil intern teilweise mit Startindex 1 gearbeitet wird. Local $aRet[$iSubSetSize], $l, $r, $m, $v For $i = 0 To UBound($aArray) - 1 Step 1 ; Komplettes Array durchlaufen For $e = $iSubSetSize - 1 To 0 Step -1 ; Jedes Element mit der Resultatliste vergleichen. If $aArray[$i] < $aRet[$e] Then ExitLoop ; Falls es kleiner ist als das kleinste Teil der Resultatliste passiert nichts. $v = $aArray[$i] ; Suchmethode die in einer sortierten Liste deutlich schneller ist, als jedes Element einzeln zu überprüfen. $l = 0 $r = $iSubSetSize - 1 $m = Int(($l + $r) / 2) While 1 If $r - $l = 1 Then ExitLoop ; in $r ist der gesuchte Index If $aRet[$m] > $v Then $l = $m Else $r = $m EndIf $m = Int(($l + $r) / 2) WEnd For $q = $iSubSetSize - 2 To $r - 1 Step -1 ; Rückwärtslaufen um Platz zu machen $aRet[$q + 1] = $aRet[$q] ; Verschieben in linearer Laufzeit. Das ist schlecht, in einem Tree wäre die Sache angenehmer, kommt beim nächsten Mal. Next $aRet[$r] = $aArray[$i] ; Positionieren ExitLoop ; Läuft Next Next For $i = 0 To $iSubSetSize - 2 Step 1 ; Weil intern teilweise mit Startindex 1 gearbeitet wird. $aRet[$i] = $aRet[$i + 1] Next ReDim $aRet[$iSubSetSize - 1] Return $aRet EndFunc ;==>__Mars04 Func __Mars03($aArray, $iSubSetSize = 1) Local $aRet[$iSubSetSize] For $i = 0 To UBound($aArray) - 1 Step 1 ; Komplettes Array durchlaufen For $e = $iSubSetSize - 1 To 0 Step -1 ; Jedes Element mit der Resultatliste vergleichen. If $aArray[$i] < $aRet[$e] Then ExitLoop ; Falls es kleiner ist als das kleinste Teil der Resultatliste passiert nichts. For $o = 0 To $iSubSetSize - 1 Step 1 ; Abwandlung von Insertion Sort verwenden If $aArray[$i] >= $aRet[$o] Then ExitLoop ; um in eine Sortierte Liste ein Element einzufügen. Next For $q = $iSubSetSize - 2 To $o Step -1 ; Rückwärtslaufen um Platz zu machen $aRet[$q + 1] = $aRet[$q] Next $aRet[$o] = $aArray[$i] ; Positionieren ExitLoop ; Läuft Next Next Return $aRet EndFunc ;==>__Mars03 Func __Mars02($aArray, $iSubSetSize = 1) Local $aRet[$iSubSetSize] For $i = 0 To UBound($aArray) - 1 Step 1 ; Komplettes Array durchlaufen For $e = 0 To $iSubSetSize - 1 Step 1 ; Jedes Element mit der Resultatliste vergleichen. If $aArray[$i] >= $aRet[$e] Then ; Dabei wird zuerst das größte, dann das 2te usw verglichen. For $o = $iSubSetSize - 2 To $e Step -1 ; Falls was gefunden wurde: Resultatliste um 1 nach unten verschieben. $aRet[$o + 1] = $aRet[$o] ; Rückwärtslaufen nicht vergessen, sonst knackts im Gebälk. Next $aRet[$e] = $aArray[$i] ; Der freigewordene Platz bekommt nun das neue größte Element. ExitLoop ; Fertig. Jeder Treffer wird nur 1x eingespeichert. EndIf ; Hier wird gezaubert, die Resultatliste ist zu jeder Zeit vollständig sortiert. Next Next Return $aRet EndFunc ;==>__Mars02 Func __Mars01($aArray, $iSubSetSize = 1) _ArraySort($aArray, 1) ; Rocket Science ReDim $aArray[$iSubSetSize] ; Obersten Teil abschneiden, fertig. Return $aArray EndFunc ;==>__Mars01 #EndRegion - Funktionen #Region - Unfug Func RandomNumbers($iCnt = 1) Local $aArray[$iCnt] For $i = 0 To $iCnt - 1 Step 1 $aArray[$i] = Random() Next Return $aArray EndFunc ;==>RandomNumbers Func Test($iStart = 10, $iEnd = 15, $iSubSetSize = 3, $iVersuche = 25) ; $iStart - Startwert für die Arraygröße ; $iEnd - Endwert für die Arraygröße ; $iSubSetSize - Schau bei ner anderen Beschreibung, sei fleißig ; $iVersuche - Anzahl Durchgänge um den Mittelwert zu bilden. Local $aRunde = Runde(1, 1, 1) ; Testrunde um das Ergebnisarray bestimmen zu können. Local $aRet[$iEnd - $iStart + 2][UBound($aRunde) + 2] = [['ArraySize', 'SubSetSize']] For $i = 0 To UBound($aRunde) - 1 Step 1 $aRet[0][$i + 2] = $aRunde[$i][0] Next For $v = 1 To $iVersuche Step 1 ; Doch besser die Runden einzeln durchzugeben. For $i = $iStart To $iEnd Step 1 $aRunde = Runde($i, $iSubSetSize, 1) $aRet[$i - $iStart + 1][0] = $i $aRet[$i - $iStart + 1][1] = $iSubSetSize For $e = 0 To UBound($aRunde) - 1 Step 1 $aRet[$i - $iStart + 1][$e + 2] += $aRunde[$e][1] / $iVersuche Next Next Next If $iSmooth Then Local $aSmooth[$iEnd - $iStart + 1] For $n = 2 To UBound($aRet, 2) - 1 Step 1 For $i = 0 To UBound($aSmooth) - 1 Step 1 $aSmooth[$i] = $aRet[$i + 1][$n] Next _ArraySmooth($aSmooth, $iSmooth, False) For $i = 0 To UBound($aSmooth) - 1 Step 1 $aRet[$i + 1][$n] = $aSmooth[$i] Next Next EndIf Return $aRet EndFunc ;==>Test Func _ArraySmooth(ByRef $aArray, $iSmooth = 1, $bFix = False) If Not IsArray($aArray) Then Return SetError(1, 0, 0) If UBound($aArray, 0) <> 1 Then Return SetError(2, 0, 0) If Not IsInt($iSmooth) Or $iSmooth < 1 Or $iSmooth > 1e9 Then Return SetError(3, 0, 0) For $i = 1 To $iSmooth Step 1 $aArray = __ArraySmooth($aArray, $bFix) Next EndFunc ;==>_ArraySmooth Func __ArraySmooth($aArray, $bFix) Local $iUBound = UBound($aArray), $aCopy[$iUBound], $nSum = $bFix ? __ArraySum($aArray, 1, $iUBound - 1) : 0, $nSum2 $aCopy[0] = $bFix ? $aArray[0] : 0.75 * $aArray[0] + 0.25 * $aArray[1] For $i = 1 To $iUBound - 2 Step 1 $aCopy[$i] = 0.25 * $aArray[$i - 1] + 0.5 * $aArray[$i] + 0.25 * $aArray[$i + 1] Next $aCopy[$iUBound - 1] = $bFix ? $aArray[$iUBound - 1] : 0.75 * $aArray[$iUBound - 1] + 0.25 * $aArray[$iUBound - 2] $nSum2 = $bFix ? __ArraySum($aCopy, 1, $iUBound - 1) : 0 If $bFix Then For $i = 1 To $iUBound - 2 Step 1 $aCopy[$i] *= $nSum / $nSum2 Next EndIf Return $aCopy EndFunc ;==>__ArraySmooth Func __ArraySum(ByRef $aArray, $iStart = 0, $iEnd = -1) If $iEnd = -1 Then $iEnd = UBound($aArray) Local $n For $i = $iStart To $iEnd - 1 Step 1 $n += $aArray[$i] Next Return $n EndFunc ;==>__ArraySum #EndRegion - Unfug -
Nicht wirklich. Du schriebst von Heaps. Und da geht es schon los. Dafür wären dynamische Datenstrukturen nötig oder alternativ entsprechend große Arrays welche am Ende erst verkleinert werden können. Quick-Select hingegen macht nur Tauschoperationen auf einem Array und damit in AutoIt die deutlich bessere Variante.
Deswegen ja meine Frage ob ihr nur auf der Laufzeitverhaltenanalyse stehen bleiben wollt. Dieses sagt erstmal nix darüber aus welche Methode die schnellere sein wird sondern nur wie diese mit der Anzahl der Elemente skalieren.
Auch Radix-Sort hat z.B. ein besseres Laufzeitverhalten als z.B. Quick-Sort. Aber in AutoIt wird Quicksort trotzdem immer schneller sein.Also stattdessen einfach mal umsetzen und dann schauen was passiert.