Codingcrew.de - Board

[Rainer]

Hallo,

ich muss ein Stringarray sortieren, wobei die Strings eine feste Länge haben. Im Prinzip ist das kein Problem, da ich jedoch von sehr großen Arrays ausgehen muss, sollte die Procedure sehr schnell sein.
Kann da jemand weiterhelfen? Ein Lösungsansatz wäre bereits sehr hilfreich.
Ich nutze MASM32.

Rainer

[CDW]

ich würde als Verfahren Mergesort oder Heapsort nutzen. Denn zuerst sollte man den richtigen Algo nehmen (für größere Datenmengen: lieber Mergesort in Java als hochoptimiertes Selectionsort in MASM )

Ansonsten wäre auch eine weitere Idee : eine "Zwischentabelle" mit Zeigern auf die Strings zu sortieren - dann müssten nicht ständig Strings kopiert werden und logisch gesehen macht es ja keinen Unterschied und man kann dann, wenn es sein muss, erst zum Schluss die Tabelle auslesen und die Strings dann "richtig herum" vertauschen.

Eine weitere Idee wäre eine Hashtabelle anzulegen und die Hashs selber zu sortieren - dürfte noch schneller gehen, da wiederum weniger Kopiererei und Vergleiche pro String.
Wobei man dann als Hashfunktion irgendeine Funktion suchen sollte, die ASCII Werte und Stellen berücksichtigt - ob es die gibt, habe ich erhlich gesagt keine Ahnung .

[Rainer]

Hallo EBFE,

vielen Dank für die Antwort. Die Sortierfunktion ist eine von vielen in Assember geschriebenen; ich möchte sie deshalb auch in Assembler schreiben.
Leider sagt mir Selectionsort nichts, ich werde anschließend mal danach googeln.
Die Tabelle mit Zeigern dürfte realisierbar sein, ich habe früher schon mal Zeitversuche unter Nutzung einer Index-Tabelle gemacht.
Zu dem Vielen, was ich nicht weiß, gehören auch Hashtabellen. Gibt es dazu Veröffentlichungen?

Nochmals vielen Dank.

Rainer

[CDW]

Die Sortierfunktion ist eine von vielen in Assember geschriebenen; ich möchte sie deshalb auch in Assembler schreiben.

Ich meinte nur, dass man zuallererst einen geeigneten Algorithmus wählen sollte .
Selectionsort war als Beispiel für einen "schlechten" Algorithmus. Hierbei wird durch "Suche das größte/kleinste Element (im Vergleich zum ersten), vertausche die beiden. Wiederhole das ganze mit dem zweiten Element usw - bis alles abgearbeitet wurde)".

Solch ein Algorithmus hat während seiner Laufzeit ca. n² Vergleiche (n ist die Eingabelänge). Also bei 100 000 Strings wären das 10 000 000 000.

Wogegen Merge/Heapsort mit n*log(n) auskommt, was sich insbesondere bei größeren Datenmengen auszahlt: bei 100 000 Strings wären das nur ca. 500 000.

Natürlich gibt es hier wiederum Vor und Nachteile - Heapsort braucht nur einen konstanten Speicher zum Sortieren, wogegen Mergesort "Zusatzspeicherverbaucht" von der Menge der zu Sortierenden Eingaben abhängt. Dafür lässt sich Mergesort besser parallelisieren usw:
http://en.wikipedia.org/wiki/Heapsort
Ist meiner Meinung nach sehr wichtiges Kriterium - z.B würde imho ein Javaprogramm bei solchen großen Datenmengen mit Heapsort/Mergesort verfahren "Jahrzente" vor einem hochoptimiertem MASM-Programm fertig.

Was bei Strings noch wichtig ist - der eigentliche Vergleich. Z.B wäre ja Zahlensortieren kein großes Problem (hier kommt wieder das pratkische Low-Level "Wissen" durch MASM-Programmierung zu Gute ), "mov eax,Zahl1; mov ebx,Zahl2; cmp eax,ebx". Bei Strings müsste man die einzelnen Zeichen und deren ASCII Werte berücksichtigen (eventuell groß/kleinschreibung, da z.b ein "a" einen ASCII Wert von 97 und "A" einen Wert von 65 darstellet). Und Strings können schon ziemlich lang sein - also wäre der eigentliche Vergleich schon eine recht aufwendige Operation (je nach Stringbeschaffenheit) und es würde sich lohnen, den zu optimieren.


Hashes:

Die Zeigertabelle spart ja schon eine Menge der Zeitintensiven Kopiervorgänge. Aber bei jedem Vergleich wird immer wieder der String Buchstabe für Buchstabe durchlaufen. Deshalb schwebte mir zuest eine Hashtable vor (formshalber: http://de.wikipedia.org/wiki/Hashtable)
denn die sind für größere "Objekte" sehr günstig - man "geht" jeden String nur einmal durch und arbeitet später nur noch mit Zahlen. Allerdings, wenn man die Hashs selber sortiern möchte, muss man sich einen Hashalgoritmus überlegen, der bei der Hashbildung die einzelnen ASCII-Werte so berücksichtigt, dass man später zuverlässig die Hashwerte selbt sortieren kann - so dass sich dann auch eine Sortierung von Strings ergibt. Man bräuchte in diesem Fall also keine komplette Hashtable zu implementieren (wäre recht aufwendig) sondern eben nur eine Hashfunktion - die Hashs+Stringzeiger selber speichert man in einem Array und sortiert diese Hashs. Der Zusatzvorteil wäre auch, dass man alleine mit dem Hashalgorithmus die Sortierung "steueren" könnte. Leider finde ich Moment nichts wesentliches dazu bei goolge - entweder habe ich einen Denkfehler und es ist schlichtweg nicht möglich oder ich suche nach falschen Begriffen
Ich dachte in folgender Richtung:

String:abcdefg
Hashfunktion

Code: Alles auswählen

for i=0 to Stringlänge do
  hash:=string[i]*(Stringlaenge-i);


So dass die ASCII Werte abhängig von ihrer Position "bewertet" werden und die Zahl damit sozusagen einen "Positionswert" darstellt:
abc wäre 97*(3-0)+98*(3-1)+99*(3-2)=582
bcd wäre 98*3+99*2+100*1=592
leider wäre dann aber "ef=304" und würde vor dem "abc" sortiert werden.


Eventuell wird aber auch schon ohne Hashnutzung schnell genug sortiert, so dass man sich da keinen Kopf machen muss.

[Rainer]

Hallo EBFE,

Vielen Dank für die Mühe, insbesondere für das Beispiel mit Hash-Bearbeitung. Das könnte klappen, meine jetzige Sortierung ist viel zu langsam. Ich werde gleich mal rangehen, in dieser Richtung was zu schreiben.

Nochmals vielen Dank.

Rainer

[kermit]

wenn du nur sortieren willst ( also keinen sortier alghorithmus selber schreiben willst ) kannst du auch die funktion "assort" ( ascending string sort) aus der masm lib nutzen, die scheint schon optimiert zu sein fuer das sortieren von string arrays...

[Rainer]

Hallo Kermit,

vielen Dank für die Antwort, ich sehe gleich mal nach.

Rainer

PS: Das ich heute erst antworten kann, verdanke ich der T-Com, die es seit dem 9.11. nicht schafft, eine angekündigte DSL-Freischaltung zu realisieren.

[Rainer]

Hallo,

mit assort hat sich das Problem lösen lassen. Die erreichten Zeiten sind einfach genial. Nochmals vielen Dank an alle, die geantwortet haben.

Gruß Rainer