smart software solutions


Stringzerlegung mit TPosition

Vorbemerkung

Über die Vollständigkeit der "angeborerenen" String-Funktionen von Delphi kann man geteilter Meinung sein (String-Funktionen von Delphi finden sich in den Delphi-Units Sysutils und Strutils), bei fast jedem Programmierer findet sich im Laufe der Zeit aber eine Sammlung mit eigenen String-Funktionen, die die offensichtlichen Lücken schließen. Bei der Verarbeitung großer Stringmengen (z.B. 10 Mb Ascii-Daten parsen) wird man aber unweigerlich mit erheblichen Performance-Bremsen konfrontiert, die sich unter der Oberfläche verbergen. Hierzu etwas Grundlagen:

Es gibt drei Stringtypen in Delphi: 
ShortString     255 Zeichen    2 bis 256 Byte     Abwärtskompatibilität
AnsiString    ~2^31 Zeichen    4 Byte bis 2 GB    8-Bit-Zeichen (ANSI)
WideString    ~2^30 Zeichen    4 Byte bis 2 GB    Unicode-Zeichen
Der Standardtyp in Delphi ist Ansi-String, eventuell notwendige Typwandlungen führt Delphi automatisch durch. Hier verbirgt sich schon der erste Stolperstein, denn manche unnötige String-Operation fügt Delphi automatisch in den Code ein. Solche unbeabsichtigten Bremsen kann man vermeiden, nur sagt einem Delphi leider nicht, wie. Hier hilft nur probieren. Als allgemeine Strategie erweist sich: Funktionsparameter immer mit (const ...: string) markieren. Hierdurch entfällt ein ungewolltes Kopieren des Strings. Ansi-Strings als var-Parameter zu übergeben ist (laut Delphi-Hilfe) noch ungünstiger als ohne Qualifizierung.

In Sonderfällen kann theoretisch die Arbeit mit Shortstrings Geschwindigkeit bringen, nur sollte man dann seine ganze Applikation mit {$H-} compilieren (oder Optionen/Compiler/Huge-Strings off), denn sonst kommt es laufend zu Umwandlungen zwischen den Stringtypen.

Eine grundsätzliche Performance-Bremse liegt aber in der Tatsache, daß die Standardfunktionen stets Teilstrings herauskopieren. Hierzu einmal als Beispiel die Funktion LeftStr aus StrUtils: 
function LeftStr(const AText: WideString; const ACount: Integer): WideString; overload;
begin
  Result := Copy(AText, 1, ACount);
end;
Bei der Verarbeitung bedeutet dies, das ein Text bei der Zerlegung zum Teil mehrfach im Text herumgeschoben werden muß, was Zeit kostet und die Speicherverwaltung fordert.

Als günstigere Konzept hat sich die Verwendung von Tposition-Records erwiesen.


Stringverarbeitung mit TPosition und TPositionArray

Ein TPosition-Record speichert zwei Integerwerte, mit denen Startposition und Länge eines Teilstrings in einem String angegeben werden (TPosition ist eine Kreation von mir und kein Delphi-Standard). Die Arbeit mit Position-Records hat den Vorteil daß der String nur in wenigen Fällen umkopiert werden muß, was einen erheblichen Performance-Gewinn bringt. 
Type
TPosition = record // Position eines Substrings in einem String
   start,len: integer;
end;

TPositionArray = Array of TPosition;
TStringArray = Array of String;
Start und len sind so berechnet, daß sie direkt mit dem Copy-Befehl verwendet werden können: 
var p: TPosition;
begin
     s = copy(text, p.start, p.len)  //Achtung, start beginnt mit 1!
end;
Soll mehr als eine Position in einem Text markiert werden, dann bieten sich TPositionArray´s an. Es handelt sich hierbei um dynamische Arrays, die mit Setlength() angelegt werden müssen. Befehle, die Strings zerlegen, können TPositionArray´s verwenden, um ihre Ergebnisse zu markieren. Hierdurch erübrigt es sich,den String zeitaufwendig z.B. in Stringlisten zu übertragen, die vielleicht bei der weiteren Verarbeitung gar nicht gebraucht werden.

Grundlegend sollten Befehle, die mit TPositionArray´s arbeiten, folgende Struktur bekommen: 
function befehl(... , var pa: TPositionArray): integer;
var count: integer;
begin
    Setlength(pa, maximalmöglicheZahl);

    ... // Hier die eigentliche Verarbeitung. Die Zahl der benötigten
                                Elemente in count festhalten;

    Setlength(pa,count);
    result := count;
end;
Setlength wird zunächst auf die maximal notwendige Größe angelegt. Der zweite Aufruf von Setlength verkleinert das Array auf die tatsächlich benötigte Größe, ohne den Inhalt zu löschen. Diese Technik entlastet den Memorymanager erheblich. Für die weitere Arbeit stehen length(pa) und high(pa) zur Verfügung (Length = High+1). For-Schleifen können damit einfach mit for i := 0 to high(pa) geschrieben werden.

Müssen Ergebnisse tatsächlich zerlegt werden, dann können die Teilstrings in einem einzelnen String oder einem Stringarray abgelegt werden: 
{ -------------------------------------------------
  Ein Wort holen
  -------------------------------------------------}
Function ExtractWord(const S: string; p: TPosition): string;
begin
    with p do
        result := copy(s,start,len);
end;
{ -------------------------------------------------
  Alle Worte holen
  -------------------------------------------------}
Function ExtractWords(const S: String; const Arr: TPositionArray;
                                       var sa: TStringArray): integer; overload;
var i: integer;
begin
    result := length(Arr);
    setlength(sa,result);
    for i := 0 to result-1 do
        with arr[i] do
            sa[i] := copy(s,start,len);
end;
Natürlich bietet es sich auf dieser Basis nun an, diverse Zerlegungsfunktionen zu implementieren, die alle nur ein TPosition-Array liefern. Bei der Extraktionen muß neben der oben gezeigten Variante noch eine Funktion existieren, die die Worte zwischen den gefundenen Strings extrahieren kann: 
{ -------------------------------------------------
  ExtractWordsBetween holt die Wörter zwischen den Fundstellen
  von Count. GetEmptyStrings steuert, ob leere Strings (auch am
  Anfang und Ende) mit ausgegeben werden.
  -------------------------------------------------}
Function ExtractWordsBetween(const S: String; tp: TPositionArray;
                            GetEmptyStrings: boolean; var sa: TStringArray): integer;
var i,n,k,p0: integer;
    t: string;
begin
    n := length(tp);
    SetLength(sa, n+1);
    k := 0;
    p0 := 1;
    for i := 0 to n do
    begin
        if i0) or GetEmptyStrings then
        begin
            sa[k] := t;
            inc(k);
        end;
    end;
    if k<>n+1 then
        SetLength(sa, k);
    result := K;
end;