• Die üblichen Sortieralgorithmen beruhen auf direkten Größenvergleichen zwischen zwei Elementen.
    Mathematisch kann man beweisen, dass man hiermit jedoch auf ein Laufzeitverhalten von n*log(n) beschränkt ist.
    Auch _ArraySort unterliegt dieser Beschränkung. Dennoch ist sie durch die (optionale) Verwendung des Dual-Pivot-Quicksorts und der Verwendung von Insertionsort für kleine Teilarrays sehr nahe an einem möglichen Optimum.

    Dennoch stellt sich die Frage: Gibt es denn trotzdem Alternativen?: Jein
    Ein Algorithmus welcher nicht auf Größenvergleichen beruht ist Radix-Sort.
    Sein Grundansatz ist ein anderer: Alle Werte werden stellenweise betrachtet. Man beginnt mit der ersten Stelle und schmeißt alle Zahlen entsprechend ihrem Stellenwert in einen bestimmten Topf. Hat man das gemacht fügt man alle Töpfe in der Reihe ihres Stellenwertes wieder aneinander.
    Dann wiederholt man das Spielchen für die restlichen Stellen.
    Am Ende liegen die Werte sortiert vor. (Genauere Beschreibungen siehe google)

    Nun die Frage: Warum wurde dieses Verfahren bisher noch nicht in AutoIt implementiert?
    Das liegt einerseits an der Beschränkung der zu sortierenden Datentypen.
    Der Sortierschlüssel der Werte muss aus "Zeichen eines endlichen Alphabets" bestehen (Zitat Wikipedia ;-).
    Vorzeichenlose Integer sind ein Beispiel hierfür, oder auch Objekte mit einem UInt als Sortierungsschlüssel.

    Auf der anderen Seite benötigt man schnelle dynamische Datenstrukturen für die Zwischenspeicherung.
    AutoIt-Arrays waren dafür schlicht nicht geeignet.
    Mit dem Map-Datentyp der aktuellen Betas steht nun aber eine derartige Struktur zur Verfügung.
    Das brachte mich dazu den RadixSort nun auch einmal in Autoit zu implementieren:

    RadixSort in AutoIt (benötigt AutoIt-Version > 3.3.13.6)
    [autoit]

    #include <Array.au3>

    [/autoit] [autoit][/autoit] [autoit]

    ; ################### Random-Array erstellen ######################
    Global Const $nEl = 1e3 ; Anzahl Elemente
    Global Const $dMaxEl = 1e5 - 1 ; Wertebereich
    Global $ARnd[$nEl]
    For $i = 0 To $nEl - 1
    $ARnd[$i] = Random(0, $dMaxEl, 1)
    Next
    _ArrayDisplay($ARnd, "unsortiert")
    ; -----------------------------------------------------------------

    [/autoit] [autoit][/autoit] [autoit]

    $t = $ARnd
    $iT = TimerInit()
    _ArraySort($t)
    ConsoleWrite(StringFormat("% 30s: %8.3f ms\n", "_ArraySort", TimerDiff($iT)))

    [/autoit] [autoit][/autoit] [autoit]

    $t = $ARnd
    $iT = TimerInit()
    _ArrayRadixSortLSD($t, __dRadixUInt)
    ConsoleWrite(StringFormat("% 30s: %8.3f ms\n", "_ArrayRadixSortLSD", TimerDiff($iT)))

    [/autoit] [autoit][/autoit] [autoit]

    $t = $ARnd
    $iT = TimerInit()
    _ArrayRadixSortMSD_Stable($t, __dRadixUInt)
    ConsoleWrite(StringFormat("% 30s: %8.3f ms\n", "_ArrayRadixSortMSD_Stable", TimerDiff($iT)))

    [/autoit] [autoit][/autoit] [autoit]

    $t = $ARnd
    $iT = TimerInit()
    _ArrayRadixSortMSD($t, __dRadixUInt)
    ConsoleWrite(StringFormat("% 30s: %8.3f ms\n", "_ArrayRadixSortMSD", TimerDiff($iT)))

    [/autoit] [autoit][/autoit] [autoit]

    ; #FUNCTION# ======================================================================================
    ; Name ..........: _ArrayRadixSortLSD
    ; Description ...: sort an array with radix-sort (LSD=Least significant digit)
    ; Syntax ........: _ArrayRadixSort(ByRef $A, Const $F, [$N = Default])
    ; Parameters ....: $A - the array which should be sorted (by reference means: direct manipulating of the array - no copy)
    ; $F - a function which defines the datatype/digit-system of the array-values (see an example for deeper details)
    ; $N - the maximum number of value-digits (if Default then evaluate this value from array - slower)
    ; Return values .: Success: True - array is sorted now
    ; Failure: False
    ; @error = 1: $A is'nt an array
    ; 2: invalid value for $F
    ; Author ........: AspirinJunkie
    ; Related .......: AutoIt-version > 3.3.13.6
    ; Remarks .......: see Wikipedia for an explanation for which data you can use it
    ; =================================================================================================
    Func _ArrayRadixSortLSD(ByRef $A, Const $F, $N = Default)
    Local $i, $t, $nn, $u, $rn = 0
    Local Const $iMax = UBound($A) - 1

    [/autoit] [autoit][/autoit] [autoit]

    ; error-handling:
    If Not IsArray($A) Then Return SetError(1, 0, False)
    If Not IsFunc($F) Then Return SetError(2, 0, False)

    [/autoit] [autoit][/autoit] [autoit]

    ; evaluate the maximum number of digits:
    If $N = Default Then
    $N = 1
    For $i = 0 To $iMax
    If $N < $F($A[$i]) Then $N = $F($A[$i])
    Next
    EndIf

    [/autoit] [autoit][/autoit] [autoit]

    ; get the digit order definition:
    Local Const $O = $F()

    [/autoit] [autoit][/autoit] [autoit]

    ; create the bucket holders:
    Local $m[], $r[] ; $m = the temporary bucket-holder, $r = the already sorted bucket holder

    [/autoit] [autoit][/autoit] [autoit]

    ; sorting!:
    For $d = 1 To $N
    ; create (and empty) buckets:
    For $i In $O
    Dim $t[]
    $m[String($i)] = $t
    Dim $t[]
    $r[String($i)] = $t
    Next

    [/autoit] [autoit][/autoit] [autoit]

    ; sort into the buckets related to the current digit:
    For $i = $rn To $iMax
    $t = $A[$i]
    $u = $F($t, $d)
    If @extended Then
    MapAppend($r[$u], $t)
    Else
    MapAppend($m[$u], $t)
    EndIf
    Next

    [/autoit] [autoit][/autoit] [autoit]

    ; convert back to array (merge the buckets to the array):
    ; at first add the already sorted elements:
    For $k In $O
    $t = $r[String($k)]
    $nn = UBound($t) - 1
    For $e = 0 To $nn
    $A[$rn] = $t[$e]
    $rn += 1
    Next
    Next

    [/autoit] [autoit][/autoit] [autoit]

    ; now add the leftover elements:
    $i = $rn
    For $k In $O
    $t = $m[String($k)]
    $nn = UBound($t) - 1
    For $e = 0 To $nn
    $A[$i] = $t[$e]
    $i += 1
    Next
    Next
    Next

    [/autoit] [autoit][/autoit] [autoit]

    Return True
    EndFunc ;==>_ArrayRadixSortLSD

    [/autoit] [autoit][/autoit] [autoit]

    ; #FUNCTION# ======================================================================================
    ; Name ..........: _ArrayRadixSortMSD
    ; Description ...: sort an array with radix-sort (MSD=Most significant digit)
    ; this implementation is stable(maintain the relative order of records with equal keys) but not in-place
    ; Syntax ........: _ArrayRadixSortMSD(ByRef $A, Const $F, [$N = Default, [$iMin = 0, [$iMax = UBound($A) - 1, {$d = Default, {Const $b_First = True}}]]])
    ; Parameters ....: $A - the array which should be sorted (by reference means: direct manipulating of the array - no copy)
    ; $F - a function which defines the datatype/digit-system of the array-values (see an example for deeper details)
    ; $N - the maximum number of value-digits (if Default then evaluate this value from array - slower)
    ; $iMin - start index for the array-range which should be sorted
    ; $iMax - end index for the array-range which should be sorted
    ; $d - Don't touch! - internal parameter which defines the actual radix
    ; $b_First - Don't touch! - internal parameter for recognize if actual function call is the begin of the recursion
    ; Return values .: Success: True - array is sorted now
    ; Failure: False
    ; @error = 1: $A isn't an array
    ; 2: invalid value for $F
    ; 3: $A isn't a 1D-Array
    ; 4: wrong value for $iMin
    ; 5: wrong value for $iMax
    ; 6: wrong combination of $iMin and $iMax
    ; Author ........: AspirinJunkie
    ; Related .......: AutoIt-version > 3.3.13.6
    ; Remarks .......: see Wikipedia for an explanation for which data you can use it
    ; =================================================================================================
    Func _ArrayRadixSortMSD(ByRef $A, ByRef Const $F, $N = Default, $iMin = 0, $iMax = UBound($A) - 1, $d = Default, Const $b_First = True)
    Local $count[], $pos, $j, $c, $u, $t
    Local Const $dLen = $iMax - $iMin ; Array-Size

    [/autoit] [autoit][/autoit] [autoit]

    If $b_First Then
    ; error-handling:
    If Not IsArray($A) Then Return SetError(1, 0, False) ; no array
    If Not IsFunc($F) Then Return SetError(2, 0, False) ; no function
    If UBound($A, 0) <> 1 Then Return SetError(3, 0, 0) ; no 1D-array
    If Not IsInt($iMin) Or $iMin < 0 Then Return SetError(4, $iMin, False) ; wrong value in $iMin
    If Not IsInt($iMax) Or $iMax > UBound($A) - 1 Then Return SetError(5, $iMin, False) ; wrong value in $iMax
    If $iMin > $iMax Then Return SetError(6, $iMax - $iMin, False) ; wrong combination of $iMin and $iMax

    [/autoit] [autoit][/autoit] [autoit]

    ; evaluate the maximum number of digits:
    If $N = Default Then
    $N = 1
    For $i = 0 To $iMax
    If $N < $F($A[$i]) Then $N = $F($A[$i])
    Next
    EndIf
    $d = $N
    EndIf

    [/autoit] [autoit][/autoit] [autoit]

    ; get the digit order definition:
    Local Const $O = $F()

    [/autoit] [autoit][/autoit] [autoit]

    ; reset the maps for the digit counter
    For $i In $O
    $count[String($i)] = 0
    Next

    [/autoit] [autoit][/autoit] [autoit]

    ; count for every digit how much elements are in it:
    For $i = $iMin To $iMax
    $count[$F($A[$i], $d)] += 1
    Next

    [/autoit] [autoit][/autoit] [autoit]

    ; calculate the positions of digit-area start in the result-array (=partial sum):
    $pos = $count
    For $i = 1 To UBound($O) - 1
    $pos[String($O[$i])] = $count[String($O[$i])] + $pos[String($O[$i - 1])]
    Next

    [/autoit] [autoit][/autoit] [autoit]

    ; reorder items:
    $i = 0
    Do
    While 1
    $u = $F($A[$iMin + $i], $d)
    $pos[$u] -= 1
    $j = $pos[$u]
    If $j <= $i Then ExitLoop
    ; swap A[iMin + i] <-> A[iMin + j]
    $c = $A[$iMin + $i]
    $A[$iMin + $i] = $A[$iMin + $j]
    $A[$iMin + $j] = $c
    WEnd
    $i += $count[$F($A[$iMin + $i], $d)]
    Until $i >= $dLen

    [/autoit] [autoit][/autoit] [autoit]

    If $d < 2 Then Return True

    [/autoit] [autoit][/autoit] [autoit]

    ; recursivly sort digit-related subarrays:
    $u = $iMin
    For $i In $O
    $c = $count[String($i)]
    If $c > 1 Then _ArrayRadixSortMSD($A, $F, $N, $u, $u + $c - 1, $d - 1, False)
    $u += $c
    Next
    Return True
    EndFunc ;==>_ArrayRadixSortMSD2

    [/autoit] [autoit][/autoit] [autoit]

    ; #FUNCTION# ======================================================================================
    ; Name ..........: _ArrayRadixSortMSD_Stable
    ; Description ...: sort an array with radix-sort (MSD=Most significant digit)
    ; this implementation is stable(maintain the relative order of records with equal keys) but not in-place
    ; Syntax ........: _ArrayRadixSortMSD_Stable(ByRef $A, Const $F, [$N = Default, [$iMin = 0, [$iMax = UBound($A) - 1, {$d = Default, {Const $b_First = True}}]]])
    ; Parameters ....: $A - the array which should be sorted (by reference means: direct manipulating of the array - no copy)
    ; $F - a function which defines the datatype/digit-system of the array-values (see an example for deeper details)
    ; $N - the maximum number of value-digits (if Default then evaluate this value from array - slower)
    ; $iMin - start index for the array-range which should be sorted
    ; $iMax - end index for the array-range which should be sorted
    ; $d - Don't touch! - internal parameter which defines the actual radix
    ; $b_First - Don't touch! - internal parameter for recognize if actual function call is the begin of the recursion
    ; Return values .: Success: True - array is sorted now
    ; Failure: False
    ; @error = 1: $A isn't an array
    ; 2: invalid value for $F
    ; 3: $A isn't a 1D-Array
    ; 4: wrong value for $iMin
    ; 5: wrong value for $iMax
    ; 6: wrong combination of $iMin and $iMax
    ; Author ........: AspirinJunkie
    ; Related .......: AutoIt-version > 3.3.13.6
    ; Remarks .......: see Wikipedia for an explanation for which data you can use it
    ; =================================================================================================
    Func _ArrayRadixSortMSD_Stable(ByRef $A, ByRef Const $F, $N = Default, $iMin = 0, $iMax = UBound($A) - 1, $d = Default, Const $b_First = True)
    Local Static $aAux[0]
    Local $count[], $j, $iOld, $c, $p, $u, $t
    Local Const $dLen = $iMax - $iMin ; Array-Size

    [/autoit] [autoit][/autoit] [autoit]

    ; error-handling:
    If Not IsArray($A) Then Return SetError(1, 0, False)
    If Not IsFunc($F) Then Return SetError(2, 0, False)

    [/autoit] [autoit][/autoit] [autoit]

    If $b_First Then
    ; error-handling:
    If Not IsArray($A) Then Return SetError(1, 0, False) ; no array
    If Not IsFunc($F) Then Return SetError(2, 0, False) ; no function
    If UBound($A, 0) <> 1 Then Return SetError(3, 0, 0) ; no 1D-array
    If Not IsInt($iMin) Or $iMin < 0 Then Return SetError(4, $iMin, False) ; wrong value in $iMin
    If Not IsInt($iMax) Or $iMax > UBound($A) - 1 Then Return SetError(5, $iMin, False) ; wrong value in $iMax
    If $iMin > $iMax Then Return SetError(6, $iMax - $iMin, False) ; wrong combination of $iMin and $iMax

    [/autoit] [autoit][/autoit] [autoit]

    ReDim $aAux[UBound($A)]
    ; evaluate the maximum number of digits:
    If $N = Default Then
    $N = 1
    For $i = 0 To $iMax
    If $N < $F($A[$i]) Then $N = $F($A[$i])
    Next
    EndIf
    $d = $N
    EndIf
    ; get the digit order definition:
    Local Const $O = $F()

    [/autoit] [autoit][/autoit] [autoit]

    ; reset the maps for the digit counter and start-positions
    For $i In $O
    $count[String($i)] = 0
    Next
    $pos = $count

    [/autoit] [autoit][/autoit] [autoit]

    ; count for every digit how much elements are in it:
    For $i = $iMin To $iMax
    $count[$F($A[$i], $d)] += 1
    Next

    [/autoit] [autoit][/autoit] [autoit]

    ; calculate the positions of digit-area start in the result-array (=partial sum):
    For $i = 1 To UBound($O) - 1
    $pos[String($O[$i])] = $count[String($O[$i - 1])] + $pos[String($O[$i - 1])]
    Next

    [/autoit] [autoit][/autoit] [autoit]

    ; iterate through the array and put the elements in their digit-related part of the result-array:
    For $i = $iMin To $iMax
    $t = $A[$i]
    $u = $F($t, $d)
    $aAux[$pos[$u]] = $t
    $pos[$u] += 1
    Next

    [/autoit] [autoit][/autoit] [autoit]

    ; transfer changes to input array
    For $i = $iMin To $iMax
    $A[$i] = $aAux[$i - $iMin]
    Next

    [/autoit] [autoit][/autoit] [autoit]

    ; sort the digit-related-subarrays recursively
    If $d > 0 Then
    For $i In $O
    $c = $count[String($O[$i])]
    $p = $pos[String($O[$i])] + $iMin - $c
    If $c > 1 Then _ArrayRadixSortMSD_Stable($A, $F, $N, $p, $p + $c - 1, $d - 1, False)
    Next
    EndIf

    [/autoit] [autoit][/autoit] [autoit]

    If $b_First Then ReDim $aAux[0]
    Return True
    EndFunc ;==>_ArrayRadixSortMSD_Stable

    [/autoit] [autoit][/autoit] [autoit]

    ; #FUNCTION# ======================================================================================
    ; Name ..........: __dRadixUInt
    ; Description ...: return the nth digit of an value / return the number of digits of a value / return the digit order definition array
    ; Syntax ........: __dRadixUInt([Const $v = Default, [Const $N = Default]])
    ; Parameters ....: $v - the value which should be analysed
    ; $N - the digit position which should be extracted from the value
    ; Return values .: this is an multi-functional function. It's return value depends on the parameter-combination:
    ; $v and $N is setted - return the nth digit of $v
    ; only $v is setted - return the number of digits of $v
    ; nothing is setted - return the digit order definition array
    ; @extended = 1 - if $N = the last digit (help speed up RadixSort)
    ; Author ........: AspirinJunkie
    ; Related .......: _ArrayRadixSort()
    ; =================================================================================================
    Func __dRadixUInt(Const $v = Default, Const $N = Default)
    Local Static $aRet[10] = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
    Local Const $d = StringLen($v)
    If $v = Default Then Return $aRet ; return digit order definition
    If $N = Default Then Return $v = 0 ? 0 : $d ; return the number of digits of $value
    If $N = $d Then Return SetExtended(1, StringLeft($v, 1))
    Return $N > $d ? "0" : StringLeft(StringRight($v, $N), 1) ; return the nth digit of $value
    EndFunc ;==>__dRadixUInt

    [/autoit] [autoit][/autoit] [autoit]

    ; #FUNCTION# ======================================================================================
    ; Name ..........: __dRadixString
    ; Description ...: return the nth digit of an String / return the number of digits of a value / return the digit order definition array
    ; Syntax ........: __dRadixString([Const $v = Default, [Const $N = Default]])
    ; Parameters ....: $v - the value which should be analysed
    ; $N - the digit position which should be extracted from the value
    ; Return values .: this is an multi-functional function. It's return value depends on the parameter-combination:
    ; $v and $N is setted - return the nth digit of $v
    ; only $v is setted - return the number of digits of $v
    ; nothing is setted - return the digit order definition array
    ; @extended = 1 - if $N = the last digit (help speed up RadixSort)
    ; Author ........: AspirinJunkie
    ; Related .......: _ArrayRadixSort()
    ; =================================================================================================
    Func __dRadixString(Const $v = Default, Const $N = Default)
    Local Static $aRet[26] = ["A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z"]
    Local Const $d = StringLen($v)
    If $v = Default Then Return $aRet ; return digit order definition
    If $N = Default Then Return $v = "" ? 0 : $d ; return the number of digits of $value
    If $N = $d Then Return SetExtended(1, StringLeft($v, 1))
    Return $N > $d ? "0" : StringLeft(StringRight($v, $N), 1) ; return the nth digit of $value
    EndFunc ;==>__dRadixString

    [/autoit]

    2 Mal editiert, zuletzt von AspirinJunkie (6. November 2014 um 13:21)

  • Sehr fein umgesetzt!
    Ich hatte RadixSort vor Jahren selbst schon getestet, aber war aufgrund der geringeren Geschwindigkeit im Vergleich zu Quicksort davon abgekommen.
    Wahrscheinlich hatte ich den Algorithmus auch etwas zu kompliziert umgesetzt.
    Für UINT hatte ich das sogar in Assembler, die Buckets waren 0 und 1, sortiert wurde nach den Bits 0 bis 31.
    Insgesamt ein wüstes Speichergeschiebe.

    Wenn man Zahlen in Hex-Darstellung schreibt, kann man sie auch mit einem abgewandelten __dRadixString (0123456789ABCDEF) sortieren. Auch BigINT.
    Mir ist zwar keine Anwendung für sortierte BigINT bekannt, aber das hat ja nichts zu sagen.

  • aber war aufgrund der geringeren Geschwindigkeit im Vergleich zu Quicksort davon abgekommen.

    In der Theorie gibt es, vor allem bei großen Datenmengen, genügend Fälle in denen Radixsort dem Quicksort überlegen ist.

    Diese Implementierung hier kommt jedoch nur in sehr wenigen Fällen am Quicksort der _ArraySort vorbei. Bei aktiviertem Dual-Pivot-Quicksort sogar fast gar nicht.
    Das liegt aber weniger am Algorithmus als an der konkreten Implementierung.
    Für den Quicksort sind z.b. viele Größenvergleiche notwendig. Diese liegen in AutoIt für die Standardtypen nativ vor und sind daher verdammt fix.
    Für den Radixsort ist hingegen die Extraktion der n-ten Stelle der Werte essentiell. Dies liegt jedoch nicht nativ vor, sondern muss über AutoIt-Code realisiert werden.

    Jetzt könnte man sagen: Ok schön für die Theorie: Radixsort nun auch in Autoit und dann auch noch fast so schnell wie Dual-Pivot-Quicksort. lassen wir es dabei.
    Aber deine Geschichte von deiner Radixsort-Umsetzung in Assembler brachte mich zu der Überlegung: Wenn man die __dRadixUInt() in Assembler umsetzen könnte und in das Skript integrieren kann, dann könnte man vielleicht wirklich eine Sortierungsfunktion erhalten welche in vielen Fällen die _ArraySort schlägt.

    Vielleicht versuche ich mich aber auch nochmal an einer MSD-Radix-Umsetzung um zu schauen wie diese sich verhält.


    Wenn man Zahlen in Hex-Darstellung schreibt, kann man sie auch mit einem abgewandelten __dRadixString (0123456789ABCDEF) sortieren. Auch BigINT.Mir ist zwar keine Anwendung für sortierte BigINT bekannt, aber das hat ja nichts zu sagen.

    Die __dRadixUInt und die __dRadixString (die nicht lexikographisch sortiert!) waren ja nur Beispiele.
    Hab die Funktion bewusst ausgelagert um eben nicht nur auf die Standardtypen beschränkt zu sein. Durch kleine Anpassungen kann man mit der Funktion auch komplexere Datentypen wie Arrays in Arrays, DllStructs oder COM-Objekte sortieren. Die _ArraySort ist hingegen auf die Grundtypen beschränkt (weswegen ich in meine Dynarray-UDF auch eine Sort-Funktion mit austauschbarer Vergleichsfunktion reingenommen habe).

    Einmal editiert, zuletzt von AspirinJunkie (4. November 2014 um 21:51)

  • Wenn man die __dRadixUInt() in Assembler umsetzen könnte und in das Skript integrieren kann, dann könnte man vielleicht wirklich eine Sortierungsfunktion erhalten welche in vielen Fällen die _ArraySort schlägt.

    Wird leider so nicht funktionieren, da der Overhead des DllCall() bzw. DllCallAddress() einfach zu groß ist! Einfach gesagt, liegen diese Berechnungen

    in AutoIt für die Standardtypen nativ vor und sind daher verdammt fix.

    8)
    Aber Versuch macht kluch...

    In der Theorie gibt es, vor allem bei großen Datenmengen, genügend Fälle in denen Radixsort dem Quicksort überlegen ist.

    Nicht nur in der Theorie! Da die Zeit für Radixsort linear mit der Menge der zu sortierenden Daten skaliert, ist es schneller. Vorausgesetzt (und das ist der Knackpunkt) die Daten haben eine konstante Schlüssellänge.

    Auch bei Radixsort schlägt die Autoit-Engine wieder erbarmungslos zu, mehr Code = langsamer Code.
    Sobald ein schnellerer Algorithmus mehr Codezeilen benötigt, fällt er hoffnungslos zurück, vgl. div. Verfahren zur Primzahlberechnung hier im Forum