[gelöst] StringList Sort sortiert komisch?

Für Fragen von Einsteigern und Programmieranfängern...
Antworten
alfware17
Beiträge: 134
Registriert: Di 14. Dez 2010, 23:27

[gelöst] StringList Sort sortiert komisch?

Beitrag von alfware17 »

Hallo ich wollte mal die Sort-Routine von TStringList testen.

Habe mich auch vorher im Forum umgesehen und auch mit Google - das Problem, was die meisten sehen ist z.B. "lexikalisch sortieren" vs "natürlich sortieren".
Naja aber das ist nicht das, was mich stört bzw. was mir aufgefallen ist.
Mein Beispiel-Programm siehe Anlage.

Drückt man die "eigener Sort" ToggleBox, wird mein eigner CustomSort benutzt, ist der Schalter aus, dann das TStringList.Sort.
Bei dieser Standard-Variante ist das Ergebnis leider anders, und in meinen Augen falsch. Z.B. geht das so

AaBbCc statt ABC... und irgendwann später abc... und die Zahlen/Sonderzeichen sind ganz woanders.

Auch wenn die Listbox nicht alles anzeigt, in der Ausgabedatei sind dann wieder alle Ascii-Zeichen drin, nur eben bei meiner Routine richtig und beim Standard tja weiß nicht...

Bin ich der Einzige, den das stört oder dem es auffällt? Habe ich Tomaten auf den Augen :shock: ,habe ich etwas übersehen, was man einstellen kann?
Ist es ein Zeichensatzproblem (erzeugt hat die Eingabe-Datei ein Free-Pascal Programm mit CHR(i) i=32..255.

Also für die Listboxen würde ich das OEM/Ansi/UTF8-Thema ja noch einsehen, aber in der Ausgabedatei sind eindeutig die Asciis "falsch" sortiert.

An den Load/Save-Routinen des TStringList liegt es nicht, denn ich habe das Problem für mich ja mit dem CustomSort eindeutig gelöst und der Sort
liefert das gleiche Ergebnis wie die Eingabe bzw später dann wie mein Batch-Programm (auch im ZIP) und mein eigenes älteres Programm.

Dieses Batch-Programm ist der eigentlche Zweck meiner Übung, ich wollte mal sehen bzw. probieren, wie schnell bzw langsam der TStringList-Sort
gegenüber meiner eigenen Lösung (ca 20 Jahre alt, mit Freepascal aktualisiert, arbeitet bei MEMOUT dann mit Zwischendateien und mischt die wieder zusammen) ist.
Richtige Unterschiede sehe ich ab ca 1 Mio Zeilen, kann aber auch betriebssystem/maschinenabhänig sein. Ich wollte eigentlich auch Gigabytes testen,
mal sehen, wann die TStringList "platzt".

Aber die Frage mit dem Lazarus/TStringList Sort bleibt? Habe nur ich damit ein Problem?

Gruß Bernd

Technik: Lazarus 1.6.4, Windows 7
Dateianhänge
sortieren_d20171115.zip
(763.12 KiB) 111-mal heruntergeladen
Zuletzt geändert von alfware17 am Do 30. Nov 2017, 17:43, insgesamt 1-mal geändert.

wp_xyz
Beiträge: 4869
Registriert: Fr 8. Apr 2011, 09:01

Re: StringList Sort sortiert komisch?

Beitrag von wp_xyz »

Hast du da die richtigen Dateien gepostet? Die test.txt enthält nur Zeilen mit 1 Zeichen, also nix von wegen mit ABCabc.

Dass von vielen Zeilen im Memo nichts zu sehen ist, liegt daran, dass die test.txt (lt. Notepad++) eine ANSI-codierte Datei ist, du aber nirgendwo etwas unternimmst, um dies in die von Lazarus verwendete UTF8-Kodierung umzwandeln. Z.B. könntest du das so tun (eine von mehreren Möglichkeiten):

Code: Alles auswählen

uses
  LConvEncoding;
 
procedure TForm1.Button1Click(Sender: TObject);
var
  i: Integer;
begin
  datei.LoadFromFile (eingabe);
  for i:=0 to datei.Count-1 do
    datei[i] :=  CP1252toUTF8(datei[i]);
  listbox1.Items.AddStrings (datei);
  Button2.enabled:= true;
  ToggleBox1.Enabled:= true;
  Button1.enabled:= false;
end;   

Ich weiß, mein Post befasst sich gar nicht mit der eigentlichen Frage der Sortierung, aber solange nicht klar ist, dass die richtige Text-Datei beigefügt ist, mag ich darüber nicht nachdenken.

alfware17
Beiträge: 134
Registriert: Di 14. Dez 2010, 23:27

Re: StringList Sort sortiert komisch?

Beitrag von alfware17 »

hallo wp_xyz,

oops, das hört sich ja doch nach Zeichensatzproblem an. Schon wieder grrrr... Wie schnell ist diese Konvertierung denn? Und wie hieße das Gegenstück (beim Save?). Wahrscheinlich brauche ich dann wieder
CP850 und 1252.

Also die Eingabe-Datei ist extra so einfach gehalten (nur ein Zeichen pro Zeile), damit nicht noch zusätzlich Komplexität rein kommt. Zumindest mein Batch-Progi macht sonst auch längere Zeilen :mrgreen:

Also was ich meine, siehe meine beiden Screeshots. Jeweils nach dem Sortieren.
Beim Standard-Sort steht da doch (untereinander, sorry für das Mißverständnis) aAbBcCdD usw. Oje, sogar noch gemischt wechselseitig die Groß/Klein-Reihenfolge sehe ich grade.
Nicht sowie es sein soll ABC beim Bild eigen.

Gruß Bernd
Dateianhänge
im rechten Fenster nach "Sortieren" die falsche(?) Reihenfolge
im rechten Fenster nach "Sortieren" die falsche(?) Reihenfolge
im rechten Fenster nach "Sortieren" die "richtige" Reihenfolge
im rechten Fenster nach "Sortieren" die "richtige" Reihenfolge

wp_xyz
Beiträge: 4869
Registriert: Fr 8. Apr 2011, 09:01

Re: StringList Sort sortiert komisch?

Beitrag von wp_xyz »

alfware17 hat geschrieben:oops, das hört sich ja doch nach Zeichensatzproblem an. Schon wieder grrrr... Wie schnell ist diese Konvertierung denn? Und wie hieße das Gegenstück (beim Save?). Wahrscheinlich brauche ich dann wieder CP850 und 1252.

Naja, wenn du Millionen von Strings hast, wird es schon etwas dauern, in der täglichen Arbeit mit einem Programm merkt man davon nichts.

Warum Gegenstück beim Save? Ich würde die Strings gleich als UTF8 speichern, vielleicht mit BOM (Byte-Order-Marker), so dass das lesende Programm weiß, dass es UTF8 ist (Achtung: bei der Stringlist hat Lazarus Probleme, wenn ein BOM vorhanden ist. Man muss den BOM überspringen, oder das wird dann die nächste Frage...).

Ansonsten, wenn du beim Lesen CP1252ToUTF8 verwendet hast, dann brauchst du beim Speichern UTF8ToCP1252 - logisch oder?

Wenn die Strings UTF8-kodiert sind, wird deine Vergleichsroutine versagen. Denn du vergleichst Byte mit Byte, aber nicht UTF8-Zeichen (wobei es diesen Begriff gar nicht gibt). Das 'ä' z.B. hat die Bytefolge $C3 $A4. Wenn du byte-weise vergleichst, siehst du bei dem Zwei-Zeichen-String 'aä' drei Bytes und es wird nach dem letzten Zweizeichen-String 'zz' einsortiert!

Um einen UTF8-String Zeichen für Zeichen zu durchlaufen, verwendest du am besten Juha Manninen's neue Unit LazUnicode (Laz 1.8 ); damit ist der folgende Aufruf möglich:

Code: Alles auswählen

uses
  LazUnicode;
var
  s, ch: String;
 ...
 for ch in s do
   writeln('ch=',ch);

Achtung: ch ist mit Absicht ein String (kein Char), damit die mehreren Bytes eines Utf8-Zeichens zusammengefasst werden. Dokumentation dazu: http://wiki.freepascal.org/Unicode_Support_in_Lazarus

Wenn du einen älteren Lazarus verwendest musst du dir mit den Routinen der Unit lazutf8 die einzelnen UTF8-Zeichen extrahieren: http://wiki.freepascal.org/Old_LCL_Unicode_Support

Wenn dir die ganze Utf8-Chose zu komplizert ist, bleibt noch der Ausweg bei AnsiStrings mit Code-Pages zu bleiben, so wie deine Eingangsdatei ist. Diese Strings kannst du byte für byte durchlaufen. Dann musst du nach dem Einlesen der Datei zuerst die Sortierung vornehmen und dann erst die Konvertierung nach UTF8 für die Anzeige. falls die Dateien verschiedene Code-Pages haben, musst du schlimmstenfalls für jede Codepage eine eigene Vergleichsroutine schreiben. Ist auch nicht ohne. Und ehrlich gesagt, was ist das Problem in dem oben gezeigten Code "for c in s"? Mit Ansi-Strings ist das auch nicht anders, nur dass ch ein Char ist.

alfware17
Beiträge: 134
Registriert: Di 14. Dez 2010, 23:27

Re: StringList Sort sortiert komisch?

Beitrag von alfware17 »

Hallo und erstmal vielen Dank, die Anzeige (der 1-Zeichen-Zeilen) Datei geht jetzt.

Aber: den Sort stört das gar nicht, der läuft m.E. nach wie vor seltsam.

Ich habe das aktualisierte Projekt angehängt. Was habe ich gemacht? CP1252toUTF8 und
ich bin noch einen Vereinfachungsschritt gegangen und habe als test.txt meinen Quelltext genommen.

standard.jpg
eigen.jpg


Siehe meine Bilder und was mich stört :roll: Das ist doch eine Sortierung, die Richtung "menschlich" geht,
aber nicht streng lexikalisch also nach den Ascii-/Ansi/UTF8-Zeichen (nach dieser Tabelle stehen da alle Großbuchstaben
zusammen und nicht gemischt wie im rechten Fenster meines Programms)

utf8.jpg


Und danke für die Hinweise für den Umgang mit den UTF8-Ketten, Durchlaufen usw. Aber wenn ich im UTF8-Bereich bin,
wollte ich je eigentlich gerade keine Customsort mehr brauchen, sondern die TStringList.Sort?

Hier für den Quelltext geht mein Customsort erstaunlicherweise immer noch, wahrscheinlich weil keine Asciis > 128 dabei sind,
falls ich es für ein Batch-Programm mit TStringList doch noch brauche, werde ich Deine Hinweise berücksichtigen.
Aber ich glaube, ich bleibe lieber bei meinem Free-Pascal Batch-Programm, das hatte (mit einem eigenen Quicksort und wie gesagt
Mischen wenn es haarig groß wird) bei den normalen Windows-Dateien (also auch binäre nicht nur Text) keinerlei Probleme und
ist wahrscheinlich auch schneller als das mit TStringList. Aber ich wollte es mal probieren/verifizieren.

Ich denke schon, die TSTringList ist sicher viel ausgefeilter und effizienter als meine per Hand doppelt verkettete Liste,
aber UTF8 - dann benutzt er doch 2 Byte pro Zeichen und kommt viel schneller an MEMOUT und muß dann swappen und mischen
oder platzt einfach, oder?

Übrigens zeigt der Lazarus-Sort immer noch das gleiche "renitente" Verhalten, wenn ich den "Standard"-Fall durch einen CustomSort
mit dem StringListCompareStringsByOrdinalCharacterValue
aus diesem Tip
https://stackoverflow.com/questions/217 ... -in-delphi

ersetze. Quelle wäre im Sortieren2-Verzeichnis des Zips.
Dateianhänge
sortieren_d20171116a.zip
(1.98 MiB) 81-mal heruntergeladen

wp_xyz
Beiträge: 4869
Registriert: Fr 8. Apr 2011, 09:01

Re: StringList Sort sortiert komisch?

Beitrag von wp_xyz »

Welchen FPC verwendest du übrigens? Du hast die Funktionen CompareStr und CompareText in deinem Code. Bei FPC 3+ bin ich mir ziemlich sicher, dass die UTF8-Routinen genommen werden, wenn die zu vergleichenden Strings UTF8-kodiert sind; bei FPC 2.6 oder älter meine ich aber, dass die Strings als Ansistrings vergleichen werden. Obwohl: Ich sehe gerade die Zeile "l1 := s1.Length" - das ist FPC-trunk-Syntax, also FPC 3+. Da habe ich jetzt wiederum keine Erfahrung, da ich FPC-Trunk kaum verwende: Bist du sicher, dass die String.Length die Zeichenlänge ermittelt oder nur die Bytes zählt? Also, wenn der String s = 'ä' ist, ergibt s.Length den Wert 1 oder 2? Ich denke letzteres - das wäre ein weiteres Problem in deinem CustomSort.

Wie schon im letzten Beitrag geschrieben, würde ich nicht erwarten, dass StringList.Sort lexikalisch sortiert. Was ist das eigentlich genau? Wikipedia führt mich dazu zu einem mathematisch gehaltenen Artikel. "Alphabetische Sortierung" ergibt auch keine klare Aussage:
[...]
Ignorieren der Tremata. Müll wird wie Mull sortiert.
Gleichordnung von Grundbuchstaben, Doppelbuchstaben und Umlaut, wenn Doppelbuchstabe wie Umlaut gesprochen wird. Mull wird wie Muell oder Müll sortiert. Duell dagegen zwischen Duden und Dugast.
Auflösung des Umlauts. Müll wird wie Muell vor Muffe einsortiert.
Separierung als selbstständiger Buchstabe.
Einordnung hinter dem Grundbuchstaben. Müll steht zwischen Muzin und Münze (und Myalgie).
Einordnung am Ende des Alphabets. Müll steht hinter Mythos.

Für alle sonstigen (fremdsprachigen) diakritischen Zeichen gilt im deutschsprachigen Raum, dass sie einheitlich weggelassen werden; so auch alle Akzente, Tilde, Makron: é und e, ç und c, ñ und n, č und c, ō und o sind gleich.

DIN 5007 Variante 1 (für Wörter verwendet, etwa in Lexika; Abschnitt 6.1.1.4.1)

ä und a sind gleich
ö und o sind gleich
ü und u sind gleich
ß und ss sind gleich

DIN 5007 Variante 2 (spezielle Sortierung für Namenslisten, etwa in Telefonbüchern; Abschnitt 6.1.1.4.2)

ä und ae sind gleich
ö und oe sind gleich
ü und ue sind gleich
ß und ss sind gleich

alfware17
Beiträge: 134
Registriert: Di 14. Dez 2010, 23:27

Re: StringList Sort sortiert komisch?

Beitrag von alfware17 »

Hallo also Lazarus 1.6.4 mit FPC 3.0.2 unter Windows 7 (bzw XP in einer Oracle VM). Auch noch unter Linux Mint 17, Lazarus Version müßte ich nachschauen.
Das mit dem Length habe ich korrigiert und so wie in der Anlage-ZIP bleiben die Lazarus-Programme jetzt. Beim Sortieren bleibe ich beim Ansi, für die Listbox
dann konvertiert aber VOR und NACH dem Sortieren, da hatte ich mich selbst ausgetrickst.
Die beiden Batch-Programme (sortieren_batch bzw sortieren_batch2) habe ich mal mit meinem Free-Pascal Programm verglichen - bzgl. Laufzeit sind sie gar nicht mal
so schlecht, allerdings steigt die StringList bei 10 Mio (Load/Save) bzw. 20 Mio (Readln+Add) Zeilen dann aus.
Nochmal danke für deine Hilfe.
Die Sort-Standards muß ich dann eben hinnehmen (habe auch ansicomparestr und sowas probiert). Und das UTF8-Problem schiebe ich noch vor mir her, wo ich kann.
Bis es eine Anwendung wirklich erfordert. Aber hier freiwillig von 1 Byte auf mehr gehen, nee :mrgreen:
Dateianhänge
sortieren_d20171116b.zip
(498.25 KiB) 81-mal heruntergeladen

Antworten