Moin,
Nachdem ich nicht in der Lage war mich in der SB richtig auszudrücken (Deutsche Sprache schwäre Sprache) hier nochmal. (Danke an Xori für seine Geduld mit Personen die so viel verstehen wie ein Ziegelstein :D)
Problemstellung:
Es gibt ein Array mit n Elementen welches Zufallszahlen enthält (oder irgendwelche anderen Zahlen, ist im Prinzip egal).
Aus diesem Array hätte man gerne in möglichst geringer Zeit eine Liste mit den k größten Einträgen in absteigender Reihenfolge. (Also wie z.B. ArrayMax eine "Liste" mit dem größten Eintrag liefert, möchte man eine Liste mit dem größten, dem 2t größten, ... dem k-t größten)
Dazu kommt man spontan auf die brilliante Idee: Nimm Quicksort und trenne anschließend den oberen Teil des Arrays ab.
Richtig, genauso kann man es machen. Und wenn man aus einem n = 100 Array die größten 90 Elemente in einer sortierten Rückgabeliste haben will ist das sicherlich der beste Weg. Falls man aus den 100 Elementen aber nur die 5 größten haben will ist es sinnlos das komplette Array zu sortieren.
Es gibt schon ein paar Lösungen, die aber bestimmt noch nicht perfekt sind. Gesucht ist die schnellste Methode
Was ist schnell ?
Das ist eine gute Frage. Da es 2 Parameter gibt (n = Arraygröße, k = Anzahl der gesuchten Elemente) ist es unwahrscheinlich, dass eine einzige Funktion auf dem kompletten Spektrum von n und k überall am schnellsten zum Ziel kommt. Wie oben angedeutet kann man QuickSort nicht einfach schlagen, wenn man z.B. von 100 Elementen 90 haben will. Gebraucht werden also funktionen die für Spezialfälle ein besonderst gutes Ergebnis liefern. (z.B. für kleines n, für großes n, für kleines k, für großes k, für k = Wurzel(n), usw usw). Aus diesen Fällen lässt sich im Endeffekt eine Funktion die an vielen Stellen halbwegs optimal läuft zusammenschustern.
Anbei 2 kleine Testskripte:
#include <Array.au3>
Global $a = RandomNumbers(15)
Global $m1 = __ArrayMax2($a, 9)
Global $m2 = __ArrayMax2($a, 9)
Global $m3 = __ArrayMax4($a, 9)
ConsoleWrite(@CRLF & 'Array: [' & UBound($a) & ']' & @CRLF)
For $i = 0 To UBound($a) - 1 Step 1
ConsoleWrite($a[$i] & ' ')
Next
ConsoleWrite(@CRLF & @CRLF & '__ArrayMax1: [' & UBound($m1) & ']' & @CRLF)
For $i = 0 To UBound($m1) - 1 Step 1
ConsoleWrite($m1[$i] & ' ')
Next
ConsoleWrite(@CRLF & @CRLF & '__ArrayMax2: [' & UBound($m2) & ']' & @CRLF)
For $i = 0 To UBound($m2) - 1 Step 1
ConsoleWrite($m2[$i] & ' ')
Next
ConsoleWrite(@CRLF & @CRLF & '__ArrayMax4: [' & UBound($m3) & ']' & @CRLF)
For $i = 0 To UBound($m3) - 1 Step 1
ConsoleWrite($m3[$i] & ' ')
Next
ConsoleWrite(@CRLF & @CRLF)
Func Find(ByRef $aArray, $nValue) ; Findet den Index für ein sortiertes Array
Local $l = 0, $r = UBound($aArray) - 1, $m = Int(($l + $r) / 2)
While 1
If $r - $l = 1 Then Return $r
If $aArray[$m] > $nValue Then
$l = $m
Else
$r = $m
EndIf
$m = Int(($l + $r) / 2)
WEnd
EndFunc ;==>Find
Func __ArrayMax4($aArray, $iSubSetSize = 1)
$iSubSetSize += 1 ; Ein 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
Func __ArrayMax2($aArray, $iSubSetSize = 1)
Local $aRet[$iSubSetSize] ; Resultatarray erstellen
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 ;==>__ArrayMax2
Func __ArrayMax1($aArray, $iSubSetSize = 1)
_ArraySort($aArray, 1) ; Rocket Science
ReDim $aArray[$iSubSetSize] ; Obersten Teil abschneiden, fertig.
Return $aArray
EndFunc ;==>__ArrayMax1
Func RandomNumbers($iCnt = 1)
Local $aArray[$iCnt]
For $i = 0 To $iCnt - 1 Step 1
$aArray[$i] = Random(100, 999, 1)
Next
Return $aArray
EndFunc ;==>RandomNumbers
Alles anzeigen
#include <Array.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(50, 100, 20, 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.
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)
ReDim $aArray[$iSubSetSize] ; Obersten Teil abschneiden. Klappt hier nicht weil nicht sortiert wurde.
Return $aArray ; 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
Alles anzeigen
Edit1: Mars02 ist rausgeflogen, weil die Funtkion in allen Fällen deutlich schlechter als Mars03 ist. Neu hinzugekommen ist Mars04, die in einigen Fällen (vorallem bei mittlerem k) etwas schneller ist.
Edit2: AspirinJunkie hat eine Funktion beigesteuert die in fast allen Fällen schneller ist, als reines Quicksort. Für die UDF und das Testskript bitte in Post 12 nachschauen.
Da ich ein Diagrammfan bin gibts hier auch ein paar Bildchen (Weniger Millisekunden sind wichtig. Also je niedriger die Kurve ist, desto besser.)
(Peaks in den Diagrammen kommen daher, dass mein Rechner im Hintergrund am Arbeiten ist)
unnamed.pngunnamed2.pngunnamed3.png
lg
M