Strings nach Länge sortieren (_ArraySortStringLen)

  • 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:

    BucketSort:

    Quicksort:

  • Genau für solche Fälle wo ich mir nicht immer extra spezielle Sortierfunktion schreiben will, habe ich mir eine flexible Sortierfunktion geschrieben, bei der man einfach die Vergleichsfunktion durch eine selbstdefinierte austauschen kann.
    Die eigentliche Sortierung ist dann noch entsprechend optimiert, so dass man am Ende zu einer schnellen Lösung kommt ohne jedesmal das Rad neu erfinden zu müssen.

    Die Funktion findest du in der >>DynArray-UDF<<.

    Mit dieser würde dein Beispiel dann z.B. so gelöst werden:

    Und die Performance dabei ist bei mir um ca. Faktor 4 schneller.

  • Und die Performance dabei ist bei mir um ca. Faktor 4 schneller.

    Nunja, kommt darauf an. Meine Funktion sortiert bei gleich langen Strings noch nach dem Alphabet.

    Wenn ich bei Deinem Script die Sortierfunktion umstelle:

    AutoIt
    Func cbByLength(ByRef $A, ByRef $B)
        Local $nA = StringLen($A), $nB = StringLen($B)
        If $nA = $nB Then Return -StringCompare($nA, $nB, 1)
        Return $nA > $nB ? -1 : 1
    EndFunc

    Dann passt es fasst. Allerdings treten ein paar Merkwürdigkeiten auf:

    Manche Einträge werden aufsteigend sortiert und manche absteigend.

  • Ich habs so gemacht: Quasi, keine ahnung ob sowas einen namen hat, ich nenne es mal ein kassen system. Jede wort länge hat eine eigene spalte (map in dem fall hier), wie in der kasse wo nach den münzen sortiert wird. Am ende werden die spalten (maps) einfach zusammen geworfen. Das braucht dann auch nur 0.231 s

    Edit: Hab nen bug gefunden, jetzt läuft es bei 0.203 s

  • Quasi, keine ahnung ob sowas einen namen hat, ich nenne es mal ein kassen system.

    Ist ein "Bucket-Sort".

    Es fehlt nur noch der Schritt, dass die einzelnen Buckets noch in sich selbst sortiert werden müssen.

    In Oscars Falle wäre dies lexikographisch unter Beachtung der Groß/Kleinschreibung.

    I.d.R. wird für diesen Schritt dann ein anderes Sortierverfahren verwendet (_ArraySort könnte man hierfür verwenden).

    Für den Fall hier wäre Bucket Sort wirklich ein ziemlich vernünftiger Ansatz :thumbup:

  • Ist ein "Bucket-Sort".

    Es fehlt nur noch der Schritt, dass die einzelnen Buckets noch in sich selbst sortiert werden müssen.

    In Oscars Falle wäre dies lexikographisch unter Beachtung der Groß/Kleinschreibung.

    I.d.R. wird für diesen Schritt dann ein anderes Sortierverfahren verwendet (_ArraySort könnte man hierfür verwenden).

    Für den Fall hier wäre Bucket Sort wirklich ein ziemlich vernünftiger Ansatz :thumbup:

    Bucket-Sort also. Noch nicht gehört von, danke fürs mitteilen :thumbup: Und die buckets müssen auch noch sortiert werden. Dann vielleicht so hier

    Zeit: 0.247 s

  • Je nachdem wie man das Verfahren nennen möchte. Manchmal heißt es auch Radix-Sort.
    Das ist übrigens in fast allen Fällen die mit großem Abstand schnellste Sortiermethode, sofern man eine gute Repräsentation der "Buckets" findet. (bei Dezimalzahlen z.B. die Ziffern -> 10 Buckets -> Iterativ), bei Buchstaben -> 256 Buckets Iterativ, etc etc. Das Größte Problem der Methode ist es eine gute Methode für die Bucketdefinition zu finden (bei hochdimensionalen Daten wie z.B. einem WString kann nicht einfach 2^16 Buckets nutzen, das ist dann wieder zu Speicherintensiv und zu langsam, bei floats kann man z.B. auch nicht einfach die Ziffern verwenden, da muss man kreativ werden).

  • Je nachdem wie man das Verfahren nennen möchte. Manchmal heißt es auch Radix-Sort.

    Ne - beim Radix werden die Elemente stellenweise betrachtet.
    Hier hingegen wird nur die Voreinteilung in Buckets durchgeführt.

    Wäre es ein Radix würde man mit dem ersten Zeichen anfangen und in einen von 26 Containern (Anzahl Buchstaben) speichern.

    In dem Container dann die Elemente nach dem 2. Zeichen in 26 weitere Subcontainer speichern usw.
    Stellenweise wird hier aber nicht gearbeitet - hier ist es ein ganz klarer Bucket Sort.

  • Dachte immer das ist im Prinzip dasselbe. Quicksort heißt ja normalerweise auch immernoch Quicksort, selbst wenn ich ab einer gewissen Teife z.B. InsertionSort (wie in der Array.au3) verwende... Muss ich wohl nochmal nachlesen ist schon ein paar Tage her :P

  • Oscar 18. März 2022 um 05:04

    Hat den Titel des Themas von „QuicksortLength“ zu „Strings nach Länge sortieren (BucketSort)“ geändert.
  • Ich wollte mal testen, wie die MAPS gegenüber dem ScriptingDictionary-Objekt abschneiden.

    Also habe ich die BucketSort-Funktion (oben aus Post#1) 1:1 auf das ScriptingDictionary-Objekt umgestellt.

    Ergebnis: Die neuen MAPS sind mehr als doppelt so schnell (0.175 s <-> 0.362 s, auf meinem Rechner und mit AutoIt v3.3.16.0).

  • Mir ist bei der entwicklung der _storageS udf aufgefallen das maps langsamer werden je mehr elemente darin gespeichert werden. Das passiert beim dictionary auch, aber nicht so schnell.

    Hier mal veranschaulicht. Die map und das dictionary bekommen jeweils eine millionen elemente. Die zeit die beide je element brauchen wird in ein array gespeichert und am ende wird verglichen.

    Man sieht das die map ab ca. 120000 langsamer wird neue elemente hinzuzufügen als das dictionary. Mir ist das auch bei .Exists aufgefallen, hab ich in dem test aber nicht beachtet. Zwischendurch wird die map auch wieder schneller. Aber generell braucht es deutlich mehr zeit die eine millionen elemente der map zuzufügen als dem dictionary.

    Das script braucht einige minuten. Leider ist das ergebnis zu groß für den anhang.

  • Lambdax: >>Hier<< hatten wir das Verhalten mal visualisiert und mit anderen Methoden verglichen.


    Der Grund für das Verhalten von Map bei großen Elementanzahlen liegt darin begründet, dass die Hashtabelle in den AutoIt eine fixe Größe von 256 Elementen besitzt und kein Resize stattfindet. Daher kommt es bei vielen Elementen zu enorm vielen Hashkollisionen mit der entsprechenden Folge, dass man beim Elemtzugriff über zig Elemente linear durchgehen muss.

  • Oscar 6. April 2022 um 15:51

    Hat den Titel des Themas von „Strings nach Länge sortieren (BucketSort)“ zu „Strings nach Länge sortieren (_ArraySortStringLen)“ geändert.
  • Ich habe mal eine UDF daraus gemacht und damit die auch mit älteren AutoIt-Versionen funktioniert, habe ich statt MAPS ein Array benutzt. Das ist nur geringfügig langsamer.

    Alles Weitere in Post#1.

    Cool danke, ich finde bestimmt mal eine anwendung dafür