Spezielle PCHAR Vergleichsfunktion gesucht

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

Spezielle PCHAR Vergleichsfunktion gesucht

Beitrag von alfware17 »

Ich habe mir vor Jahren ein Sortierprogramm geschrieben, deren Algorithmus u.a. die folgende Vergleichsfunktion benutzt:

Code: Alles auswählen

FUNCTION Vergl_S(VAR a,b: STRING):BOOLEAN;
VAR s,i,l,la,lb: LONGINT;
BEGIN
   i:=abspalte; s:=0;
   la:=LENGTH(a); lb:=LENGTH(b);
   l:=la; IF l > lb THEN l:=lb;
   IF l > bisspalte THEN l:=bisspalte;
   WHILE (s = 0) AND (i <= l) DO BEGIN
      IF grossklein
         THEN s:= ORD(a[i]) - ORD(b[i])
         ELSE s:= ORD(UPCASE(a[i])) - ORD(UPCASE(b[i]));
      INC(i);
   END;
   IF s = 0
      THEN
         IF (la <= lb) THEN s:=-1 ELSE s:=1
      ELSE
         IF (s < 0) THEN s:=-1 ELSE s:=1;
   (* TRUE if a > b *)
   Vergl_S:=(s = -1); IF reverse THEN Vergl_S:=(s = 1);
END;
Ich habe als zusätzliche Funktionen: revers, groß/klein beachten, (nur) ab/bis Zeichen.

Meine Daten sind Zeilen bis 255 Zeichen lang, ich speichere sie in einer einfach verketteten Liste und der Quicksort kommt recht schnell damit klar.

Nun hatte ich immer mal wieder die Idee, PCHAR zu benutzen, sei es aus Geschwindigkeitsgründen oder wegen Speicherplatz - jedes Listenelement nimmt momentan 272 Bytes vom Heap bei String, bei PCHAR waren/sind es abhängig von der wirklichen Länge eben weniger (48, 64, 128 usw.).

Wenn ich mich recht erinnere, hatte ich immer mal wieder Argumente pro und contra PCHAR bzw STRING, zuletzt hatte ich eben PCHAR bei 16bit (weil mir der Heap wichtiger war) und STRING bei 32/64bit (bis 10 Mio Zeilen sind eh drin, also ist Geschwindigkeit wichtiger). Nun wollte ich (mal wieder) diese Aufteilung aufheben und einheitlich eins nehmen (PCHAR oder STRING) und habe alle 4 Varianten getestet als Sonntagsbeschäftigung. STRING bei 16bit fiel durch, also Entscheidung für PCHAR auch bei 32/64bit.

Nun stelle ich einen Geschwindigkeitsverlust fest, zwischen 30 und 100% mehr Laufzeit, das kann ich nicht so lassen. Als Ursache sehe ich natürlich das Konvertieren in/aus der gespeicherten Form (Liste mit PCHAR-Elementen) und eben von/nach der Ein-/Ausgabe-Form STRING. u.a. durch STRPAS und STRPCOPY. Bei der Ein-/Ausgabe kann ich es noch hinnehmen, was ich aber nicht bedacht hatte (damals so 2005): ich benutze meine o.a. Vergleichsfunktion und muß daher, wenn ich PCHAR speichere, eine "Krücke" wie diese hier benutzen

Code: Alles auswählen

FUNCTION Vergl_P(a,b: PCHAR):BOOLEAN;
VAR stra,strb: STRING;
BEGIN
   stra:=STRPAS(a); strb:=STRPAS(b);
   Vergl_P:=Vergl_S(stra,strb);
END;
Und die scheint mein Flaschenhals zu sein. Daher meine Überlegung, mir mit den PCHAR-Funktionen StrLComp usw eine neue Vergleichsfunktion zu basteln, da ich keine finde, die alle zusätzlichen Funktionen revers, groß/klein beachten, (nur) ab/bis Zeichen kann. Hat jemand eine Idee?

Die Geschwindigkeit, wenn ich zB nur StrLComp benutze, steigt zwar wieder, es fehlen nur noch 30% aber ich würde es versuchen auch noch an der Eingabe-/Ausgabe-Konvertierung zu basteln wobei ich ehrlich außer STRAPAS und STRPCOPY nichts kenne. Oder ich muß die Idee begraben. Ohne Vergl-Funktion für PCHAR muß ich es sowieso...

Warf
Beiträge: 1904
Registriert: Di 23. Sep 2014, 17:46
OS, Lazarus, FPC: Win10 | Linux
CPU-Target: x86_64

Re: Spezielle PCHAR Vergleichsfunktion gesucht

Beitrag von Warf »

Als erstes mal, warum das so lahm ist ist klar. Wenn du einen neuen String erzeugst, muss der Memory Manager Speicher allokieren, und am ende wieder freigeben, und das ist ziemlich Lahm.

Um deine Frage zu beantworten, du kannst einfach die LibC verwenden:

Code: Alles auswählen

uses
  ctypes;

const
// Geklaut von CMem
{$if defined(win32)}
  LibCName = 'msvcrt';
{$elseif defined(win64)}
  LibCName = 'msvcrt';
{$elseif defined(wince)}
  LibCName = 'coredll';
{$elseif defined(netware)}
  LibCName = 'clib';
{$elseif defined(netwlibc)}
  LibCName = 'libc';
{$elseif defined(macos)}
  LibCName = 'StdCLib';
{$elseif defined(beos)}
  LibCName = 'root';
{$else}
  LibCName = 'c';
{$endif}

function strcmp(str1: PChar; str2: PChar): cint; external LibCName;

var
  A: PChar = 'A';
  B: PChar = 'B';
begin
  WriteLn(strcmp(A, B)); 
Die LibC hat extrem auf die Hardware optimierte varianten von solchen basisfunktionen und ist vermutlich somit schon deutlich schneller als eine entsprechende Pascal alternative.

Benutzeravatar
af0815
Lazarusforum e. V.
Beiträge: 6175
Registriert: So 7. Jan 2007, 10:20
OS, Lazarus, FPC: FPC fixes Lazarus fixes per fpcupdeluxe (win,linux,raspi)
CPU-Target: 32Bit (64Bit)
Wohnort: Burgenland
Kontaktdaten:

Re: Spezielle PCHAR Vergleichsfunktion gesucht

Beitrag von af0815 »

Ein String ist manchmal nicht einfach eine Folge von PChars. Mittlerweile ist ein String eine Folge von UTF8 Codepoint die 1 bis 4 Bytes umfassen können. Das nur falls deine Routinen die auf reinen PChar (und das als Byte oder Word betrachten) basieren mal Blödsinn machen.
Blöd kann man ruhig sein, nur zu Helfen muss man sich wissen (oder nachsehen in LazInfos/LazSnippets).

Benutzeravatar
theo
Beiträge: 10446
Registriert: Mo 11. Sep 2006, 19:01

Re: Spezielle PCHAR Vergleichsfunktion gesucht

Beitrag von theo »

af0815 hat geschrieben:
Mo 26. Jun 2023, 13:29
Ein String ist manchmal nicht einfach eine Folge von PChars. Mittlerweile ist ein String eine Folge von UTF8 Codepoint die 1 bis 4 Bytes umfassen können. Das nur falls deine Routinen die auf reinen PChar (und das als Byte oder Word betrachten) basieren mal Blödsinn machen.
Der reine (Byte-) Vergleich ginge ja noch, aber Sachen wie ORD(UPCASE(Char)) kannst du in der Pfeife rauchen mit UTF-8.

Benutzeravatar
Jorg3000
Lazarusforum e. V.
Beiträge: 164
Registriert: So 10. Okt 2021, 10:24
OS, Lazarus, FPC: Win64
Wohnort: NRW

Re: Spezielle PCHAR Vergleichsfunktion gesucht

Beitrag von Jorg3000 »

theo hat geschrieben:
Mo 26. Jun 2023, 14:27
Sachen wie ORD(UPCASE(Char)) kannst du in der Pfeife rauchen mit UTF-8.
Gibt es für FreePascal/Delphi eigentlich einen Sortieralgorithmus für Unicode? (UCA)
https://de.wikipedia.org/wiki/Unicode_C ... _Algorithm

@alfware17
Ist deine Zeichenkodierung UTF-8 und um wie viele Textzeilen handelt es sich?
Ich hätte Lust mich am schnellsten Sortieralgorithmus für Unicode zu probieren, aber nur nach UCA (siehe oben) und wenn jemand Bedarf für Zehntausende Textzeilen hätte.

Mathias
Beiträge: 6120
Registriert: Do 2. Jan 2014, 17:21
OS, Lazarus, FPC: Linux (die neusten Trunk)
CPU-Target: 64Bit
Wohnort: Schweiz

Re: Spezielle PCHAR Vergleichsfunktion gesucht

Beitrag von Mathias »

Der reine (Byte-) Vergleich ginge ja noch, aber Sachen wie ORD(UPCASE(Char)) kannst du in der Pfeife rauchen mit UTF-8.
Genau so ist es, die Berücksichtigung von UTF8-Zeichen bremst das Vergleichen recht aus.
Wen man nur Zeichen unter #127 verwendet, würde ich auch auf die clibs zugreifen.
Mit Lazarus sehe ich grün
Mit Java und C/C++ sehe ich rot

Warf
Beiträge: 1904
Registriert: Di 23. Sep 2014, 17:46
OS, Lazarus, FPC: Win10 | Linux
CPU-Target: x86_64

Re: Spezielle PCHAR Vergleichsfunktion gesucht

Beitrag von Warf »

Das ist ja das geniale an UTF-8, solang es nicht case insensetive sein muss funktioniert strcmp genau richtig. Denn bei einem compare sucht man sich ja das erste Zeichen was unterschiedlich ist, und dann prüft man ob der charcode größer oder kleiner ist.

UTF-8 ist so designed das in dem ersten byte die längeninformation in den obersten bits hat. Das erste byte von einem Codepunkt der 1 char braucht ist damit immer kleiner als das erste byte eines Codepunkt der 2 bytes braucht, der ist kleiner als einer der 3 bytes braucht , etc. Da höhere Codepunkte mehr bytes brauchen, ist damit die Entscheidung von strcmp bereits korrekt.
Wenn die Chars gleichlang sind, dann muss einfach die bytes in order von Most nach Leastsigificant durchgegangen werden, sobald eins kleiner oder größer ist kann damit die entscheidung getroffen werden. Auch hier funktioniert UTF-8, denn die bytes sind mit Most Significant zu erst geordnet, d.h. ein algorithmus der einfach von links nach rechts durchgeht kann eine comparison durchführen.

Das gesagt, Gleichheit heist nicht Gleichheit in Unicode, so gibt es z.B. mehrere wege ein "Ä" darzustellen, z.B. als den charakter "Ä" der seinen eigenen codepunkt hat, oder als zwei decorator punkte und ein A, oder als ein decorator doppelpunkt und ein A, und bestimmt noch deutlich mehr.
Hierfür wird es aber generell komplizierter, was man hier machen muss ist beide Strings zu erst normalisieren, entweder auf die kleinstmögliche darstellung (einfach charcode "Ä") oder auf dei gröstmögliche (punkt punkt A). Siehe: https://de.wikipedia.org/wiki/Normalisierung_(Unicode)

Aber das ist eigentlich nur notwendig wenn man mit daten aus verschiedenen Quellen arbeitet. Wenn alle Daten aus der selben Quelle kommen, sollte es eigentlich keine Unterschiede bei der Darstellung geben, und ein einfaches strcmp sollte voll und ganz ausreichen

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

Re: Spezielle PCHAR Vergleichsfunktion gesucht

Beitrag von alfware17 »

Jorg3000 hat geschrieben:
Mo 26. Jun 2023, 17:17
theo hat geschrieben:
Mo 26. Jun 2023, 14:27
Sachen wie ORD(UPCASE(Char)) kannst du in der Pfeife rauchen mit UTF-8.
Gibt es für FreePascal/Delphi eigentlich einen Sortieralgorithmus für Unicode? (UCA)
https://de.wikipedia.org/wiki/Unicode_C ... _Algorithm

@alfware17
Ist deine Zeichenkodierung UTF-8 und um wie viele Textzeilen handelt es sich?
Ich hätte Lust mich am schnellsten Sortieralgorithmus für Unicode zu probieren, aber nur nach UCA (siehe oben) und wenn jemand Bedarf für Zehntausende Textzeilen hätte.
Es sind Windows-Dateien, das sind alles 1-Byte Codes, normale deutsche Umlaute. Im Linux funktioniert es mit meiner eigenen Vergleichsfunktion auch, außer die Zeilenenden, die ich nach dem Sortieren aus Fairnessgründen wieder anhänge (ich vergleiche die Laufzeit und checke die md5.Summe). Für Win32/64 habe ich mich jetzt für Ansistring entschieden, bei MS-DOS PChar und im Linux bleibt es bei String. Die Zeilenanzahl ist variabel, zB 1 Mio Zeilen durchschnittlich mit 64 Zeichen, max 133 aber nur für mich, ist auch beliebig lang möglich, 255 erschien mir mal sinnvoll.

Ich mache bei ca 1 Mio Zeilen einen Cut für in-memory Sort und dann kann man sich eines von 4 Mischverfahren aussuchen, der Bestand wird per Teile-und-Herrsche zerlegt.
Sicher geht bei mehr RAM auch noch mehr, aber ich habe zB bei 64bit und einem alten PC gemerkt, daß Windows dann nur mit Swappen beschäftigt war und das ist ja nicht Sinn der Sache, da ist mein Mischen viel schneller.

Ich habe mal mit einem C-Programm verglichen, Pascal also meins war schneller. Vor allem bricht es nicht bei größeren Datenmengen ab. In-Memory kann Python im Prinzip auch ganz gut oder neulich zB der Sort von den Stringlists in Pascal. Nur habe ich gemerkt, das Save der Stringlist ist wieder so eine Bremse. Will sagen, am reinen In-Memory Sort weiß ich nicht mehr, was ich noch schrauben soll - vielleicht hast du ja was - und die 4 Mischverfahren haben einen gemeinsamen Flaschenhals nämlich das Readln/Writeln, aber sonst schafft das Verfahren im Prinzip jeden riesigen Bestand, Zeit spielt eine Rolle und die Plattengröße. Vielleicht mißbrauche ich später mal einen neuen Rechner mal für mehr als 1 TB, bisher war bei 680 GB Schluß und langweilig, ich habe mir nur das orakelte Teilen theoretisch angesehen und dann abgebrochen.

Antworten