Ich brauchte eine Sortierfunktion, um Strings der Länge nach zu sortieren.
Mir war schon klar, dass es auf eine Quicksort-Funktion hinauslaufen würde, aber ich wollte auch mal sehen, wie sich andere Sortierverfahren schlagen.
BubbleSort ist zwar einfach zu programmieren, aber grottenlahm. InsertionSort war dann schon schneller, aber mit vielen String (mehreren Tausend) auch nicht wirklich brauchbar.
Meine Quicksort-Funktion schlägt sich schon ganz gut (über 13.000 Strings in ca. 1.8 s, InsertionSort braucht fast 5 Minuten).
Vielleicht kann ja noch jemand so eine Funktion gebrauchen oder es findet jemand noch Optimierungsmöglichkeiten.
Im ZIP-Archiv (Anhang) befindet sich neben dem Script auch die Testdatei mit den 13.071 Strings.
Edit1 17.03.2022:
Dank Lambdax und AspirinJunkie musste ich feststellen, dass Quicksort hier nicht die schnellste Variante ist, sondern BucketSort.
Und dank MAPS (ab AutoIt v3.3.16.0 oder Beta-Version) kann man eine recht kleine BucketSort-Funktion damit erstellen.
Edit2 17.03.2022:
Die BucketSort-Funktion konnte man noch optimieren (_ArrayConcatenate war überflüssig, das kann man gleich in das Quell-Array schreiben).
Und _ArraySort mit DualPivot ist auch noch etwas schneller.
Mit 0.178 s (auf meinem Rechner) ist das wohl jetzt das Optimum.
Edit3 06.04.2022:
Ich habe mal eine UDF daraus erstellt. Man kann die Buckets beim BucketSort auch mit einem Array abbilden, was nur geringfügig langsamer als die MAPS-Variante ist.
Hat aber den Vorteil, dass es auch mit älteren AutoIt-Versionen funktioniert.
Im Anhang befindet sich das ZIP-Archiv "_ArraySortStringLen.zip", mit der UDF, einem Example und zwei Teilwörterbüchern (107.632 und 538.160 Wörter) zum testen.
Auf meinem Rechner benötigt die Funktion für das große Wörterbuch nur ca. 7 Sekunden zum sortieren (inkl. Alphabetisch).
BucketSort mit Arrays:
#include-once
#include <Array.au3>
#include <AutoItConstants.au3>
; ============================================================================================================
; Name...........: _ArraySortStringLen
; Description ...: Sortiert ein 1D-StringArray nach den Stringlaengen
; Syntax.........: _ArraySortStringLen($aData[, $iDescending][, $iAlphabetical][, $sSepChar][, $iMax])
; Parameters ....: $aData = das Array mit den Strings
; $iDescending = auf- oder absteigend sortieren (Standard = 0 = aufsteigend)
; $iAlphabetical = zusaetzlich noch alphabetisch sortieren (Standard = 0 = nein)
; $sSepChar = das zu verwendende Trennzeichen (darf nicht in den Strings vorkommen)
; $iMax = die maximale Stringlaenge (Standard = 50, wird aber automatisch vergroessert)
; Return values .: bei Erfolg = True und das uebergebene Array ist entsprechend sortiert (ByRef-Uebergabe)
; im Fehlerfall = False und @error =
; 1: Das uebergenene Array ist kein 1D-Array
; Author ........: Oscar (www.autoit.de)
; ============================================================================================================
Func _ArraySortStringLen(ByRef $aData, $iDescending = 0, $iAlphabetical = 0, $sSepChar = Chr(0), $iMax = 50)
If UBound($aData, $UBOUND_DIMENSIONS) <> 1 Then Return SetError(1, 0, False)
If UBound($aData, $UBOUND_ROWS) <= 1 Then Return True
Local $aBucket[$iMax], $iLen, $aTmp, $iIndex = 0
For $sWord In $aData
$iLen = StringLen($sWord)
If $iLen = 0 Then ContinueLoop
If $iLen >= $iMax Then
$iMax = $iLen + 1
ReDim $aBucket[$iMax]
EndIf
$aBucket[$iLen] &= $sWord & $sSepChar
Next
If $iDescending Then _ArrayReverse($aBucket)
For $sTmp In $aBucket
If $sTmp = '' Then ContinueLoop
$aTmp = StringSplit(StringTrimRight($sTmp, 1), $sSepChar, 3)
If $iAlphabetical Then _ArraySort($aTmp, $iDescending, 0, 0, 0, 1)
For $sWord In $aTmp
$aData[$iIndex] = $sWord
$iIndex += 1
Next
Next
Return True
EndFunc ;==>_ArraySortStringLen
Alles anzeigen
BucketSort:
#include <Array.au3>
#include <GUIConstantsEx.au3>
#include <GuiListView.au3>
#include <WindowsConstants.au3>
Global $sFile = @ScriptDir & '\autocomplete.txt'
Global $sData = FileRead($sFile)
Global $aWords = StringSplit($sData, @CRLF, 3)
Global $iTimer, $iDiff
$iTimer = TimerInit()
_BucketSortLength($aWords)
$iDiff = TimerDiff($iTimer) / 1000
ConsoleWrite(StringFormat('Wörter: %i\r\nZeit: %.03f s\r\n', UBound($aWords), $iDiff))
_ArrayShow($aWords)
Func _BucketSortLength(ByRef $aData)
Local $mBucket[], $iLen, $aKeys, $sTmp, $aTmp, $iIndex = 0
For $sWord In $aData
$iLen = StringLen($sWord)
If $mBucket.exists($iLen) Then
$mBucket[$iLen] &= $sWord & ','
Else
$mBucket[$iLen] = $sWord & ','
EndIf
Next
$aKeys = MapKeys($mBucket)
_ArraySort($aKeys, 1)
For $sTmp In $aKeys
$aTmp = StringSplit(StringTrimRight($mBucket[$sTmp], 1), ',', 2)
_ArraySort($aTmp, 1, 0, 0, 0, 1)
For $sWord In $aTmp
$aData[$iIndex] = $sWord
$iIndex += 1
Next
Next
EndFunc
; Funktion zum Anzeigen des Arrays
Func _ArrayShow(ByRef $aData, $sTitle = 'ArrayShow')
Local $hGui = GUICreate($sTitle, 540, @DesktopHeight - 140, -1, 10, BitOR($GUI_SS_DEFAULT_GUI, $WS_SIZEBOX))
Local $idLV = GUICtrlCreateListView('Row|Data', 5, 5, 530, @DesktopHeight - 150)
GUICtrlSetFont(-1, 12, 400, 0, 'Courier New')
GUICtrlSetResizing(-1, $GUI_DOCKBORDERS)
_GUICtrlListView_JustifyColumn($idLV, 0, 1)
_GUICtrlListView_BeginUpdate($idLV)
For $i = 0 To UBound($aData) - 1
GUICtrlCreateListViewItem($i & '|"' & $aData[$i] & '"', $idLV)
Next
_GUICtrlListView_SetColumnWidth($idLV, 0, $LVSCW_AUTOSIZE)
_GUICtrlListView_SetColumnWidth($idLV, 1, $LVSCW_AUTOSIZE)
_GUICtrlListView_EndUpdate($idLV)
GUISetState()
Do
Until GUIGetMsg() = -3
GUIDelete($hGui)
EndFunc ;==>_ArrayShow
Alles anzeigen
Quicksort:
#include <GUIConstantsEx.au3>
#include <GuiListView.au3>
#include <WindowsConstants.au3>
Global $sFile = @ScriptDir & '\autocomplete.txt'
Global $sData = FileRead($sFile)
Global $aWords = StringSplit($sData, @CRLF, 3)
Global $iTimer, $iDiff
; Zur Auswahl der Sortiermethode (Achtung! InsertionSort dauert sehr lange!)
; $bQuicksort = True gleich Quicksort (bei mir: 1.865 s)
; $bQuicksort = False gleich InsertionSort (bei mir: 287.283 s also fast 5 Minuten)
Global $bQuicksort = True
Switch $bQuicksort
Case True
$iTimer = TimerInit()
_QSSortLength($aWords)
$iDiff = TimerDiff($iTimer) / 1000
Case False
$iTimer = TimerInit()
_QSInsertionSort($aWords)
$iDiff = TimerDiff($iTimer) / 1000
EndSwitch
;~ _ArrayReverse($aWords)
ConsoleWrite(StringFormat('Wörter: %i\r\nZeit: %.03f s\r\n', UBound($aWords), $iDiff))
_ArrayShow($aWords)
; Funktion fuer den Stringvergleich
Func _QSStringCmp(Const $sD1, Const $sD2)
Local $1 = StringLen($sD1), $2 = StringLen($sD2)
If $1 = $2 Then Return StringCompare($sD1, $sD2, 1) >= 0
Return $1 > $2
EndFunc ;==>_QSStringCmp
; Rekursive Quicksort-Funktion
Func _QSSortLength(ByRef $aData, $left = 0, $right = UBound($aWords) - 1)
If $right - $left >= 20 Then ; bei 20 und mehr Elementen, Quicksort benutzen
If $left < $right Then
Local $pivot = _QSSplitSwap($aData, $left, $right)
_QSSortLength($aData, $left, $pivot - 1)
_QSSortLength($aData, $pivot + 1, $right)
EndIf
Else ; bei weniger als 20 (noch verbleibenden) Elementen, ist InsertionSort schneller
_QSInsertionSort($aData, $left, $right)
EndIf
EndFunc ;==>_QSSortLength
Func _QSSplitSwap(ByRef $aData, $left, $right)
Local $i = $left, $j = $right - 1, $pivot = $aData[$right], $h
Do
While _QSStringCmp($aData[$i], $pivot) And $i < $right
$i += 1
WEnd
While _QSStringCmp($pivot, $aData[$j]) And $j > $left
$j -= 1
WEnd
If $i < $j Then
$h = $aData[$i]
$aData[$i] = $aData[$j]
$aData[$j] = $h
EndIf
Until $i >= $j
$aData[$right] = $aData[$i]
$aData[$i] = $pivot
Return $i
EndFunc ;==>_QSSplitSwap
; InsertionSort-Funktion
Func _QSInsertionSort(ByRef $aData, $iStart = 0, $iEnd = UBound($aData) - 1)
Local $sVal, $j
For $i = $iStart To $iEnd
$sVal = $aData[$i]
$j = $i
While ($j > $iStart) And _QSStringCmp($sVal, $aData[$j - 1])
$aData[$j] = $aData[$j - 1]
$j -= 1
WEnd
$aData[$j] = $sVal
Next
EndFunc ;==>_QSInsertionSort
; Funktion zum Anzeigen des Arrays
Func _ArrayShow(ByRef $aData, $sTitle = 'ArrayShow')
Local $hGui = GUICreate($sTitle, 540, @DesktopHeight - 140, -1, 10, BitOR($GUI_SS_DEFAULT_GUI, $WS_SIZEBOX))
Local $idLV = GUICtrlCreateListView('Row|Data', 5, 5, 530, @DesktopHeight - 150)
GUICtrlSetFont(-1, 12, 400, 0, 'Courier New')
GUICtrlSetResizing(-1, $GUI_DOCKBORDERS)
_GUICtrlListView_JustifyColumn($idLV, 0, 1)
_GUICtrlListView_BeginUpdate($idLV)
For $i = 0 To UBound($aData) - 1
GUICtrlCreateListViewItem($i & '|"' & $aData[$i] & '"', $idLV)
Next
_GUICtrlListView_SetColumnWidth($idLV, 0, $LVSCW_AUTOSIZE)
_GUICtrlListView_SetColumnWidth($idLV, 1, $LVSCW_AUTOSIZE)
_GUICtrlListView_EndUpdate($idLV)
GUISetState()
Do
Until GUIGetMsg() = -3
GUIDelete($hGui)
EndFunc ;==>_ArrayShow
Alles anzeigen