Regex vs. Eigenbau (Effizienz vs. Lesbarkeit?)

[Warf]

Das erspart in den meisten Fällen den REGEX-"Dampfhammer".

Regex sieht zwar immer recht kompliziert aus, es ist aber tatsächlich oftmals die beste Lösung um strings zu matchen, denn Regex ist Theoretisch Optimal. Ein Regulärer Ausdruck (wenn er echt regulär ist und nicht diese Perl style zusatzfeatures hat die die sprache nicht regulär machen) wird zu einem Automaten Kompiliert der jedes Zeichen des Input Strings genau einmal betrachten muss.

Deine Lösung zum Beispiel ruft 2 mal Pos auf, was bedeutet das im schlimmsten Fall (wenn die input strings nicht vorhanden sind aber prefixe davon oft vorkommen), 2 mal sich jeden Charakter mal die länge des match strings (also bei 'PRO-T' sind wir bei 5x jeden char) anschauen muss.
Natürlich ist es auch immer ein bisschen die Frage wie Effizient was implementiert ist, Pos ist ziemlich effizient, und ich weis nicht wie Optimiert TRegExpr ist.

Aber grundsätzlich macht man mit regex nichts falsch. In sehr einfachen Fällen ist man vielleicht ein bisschen langsamer wegen dem statischen overhead von Regex, bei komplexeren fällen (komplexerer input string oder komplexeres Pattern) wird Regex deutlich besser werden als der Naive ansatz da Regex immer Alogrithmisch optimal ist.

Man sollte nur dran denken das Regex immer vor zu kompilieren und nicht jedes mal neu erstellen (also das TRegExpr objekt zu behalten und so oft wie möglich wieder zu verwenden)

[theo]

Regex ist immer kryptisch und alleine deshalb fehleranfällig und nachträglich bzw. durch andere schwer zu entschlüsseln. Das Gegenteil der Pascal Philosophie.
Wenn man es selten benötigt, muss man sich immer wieder zuerst schlau machen oder mindestens ein Cheat Sheet hervorkramen.
Das braucht Zeit, die man oft lieber in eine kleine Funktion investiert, welche man auch ohne Bletchley Park versteht.
Für mich ist das etwas für Skriptsprachen, wo man vielleicht nicht Effizient an einzelne Chars herankommt.

Code: Alles auswählen

 (\b25[0-5]|\b2[0-4][0-9]|\b[01]?[0-9][0-9]?)(\.(25[0-5]|2[0-4][0-9]|[01]?[0-9][0-9]?)){3} 

[Warf]

Für mich ist das etwas für Skriptsprachen, wo man vielleicht nicht Effizient an einzelne Chars herankommt.

Code: Alles auswählen

 (\b25[0-5]|\b2[0-4][0-9]|\b[01]?[0-9][0-9]?)(\.(25[0-5]|2[0-4][0-9]|[01]?[0-9][0-9]?)){3} 

Der Regex den du da gepostet hast sieht vielleicht kompliziert aus auf den ersten blick, aber ich würde mal behaupten das wenn man einen effizienten algorithmus schreibt der die selbe funktionaltität hat deutlich komplexer ist.

Ein beispiel aus einem meiner Projekte, funktion ist einen stream char für char zu lesen bis zu einem konstanten string pattern. Es ist also 1-1 die funktionalität die ein DFA der sprache '.*(PATTERN)' hat. Beispiel um newline zu matchen wäre also das pattern #13#10 (CRLF) also regex '.*\r\n'

Der entsprechende code dazu ist:

Code: Alles auswählen

procedure TStreamHelper.ReadTo(const pattern: string; out Result: string;
  MaxLen: integer);
var
  c: char;
  len: integer;
  pLen: integer;
  backtrack: integer;
begin  
  if MaxLen <= 0 then Exit;
  SetLength(Result, 128);
  len := 0;
  plen := 0;
  backtrack := 0;
  try
    while len < MaxLen do
    begin
      c := char(Self.ReadByte);
      Result[len + 1] := c;
      Inc(len);
      if len = Result.Length then
        SetLength(Result, Result.Length * 2);
      if pattern[pLen + 1] = c then
      begin
        if plen = 0 then
        begin
          backtrack := len;
        end;
        Inc(pLen);
        if pLen = pattern.Length then
          Exit;
      end
      else if plen > 0 then
      begin
        pLen := 0;
        while backtrack + pLen < len do
        begin
          if pattern[pLen + 1] = Result[backtrack + pLen + 1] then
            Inc(pLen)
          else
          begin
            pLen := 0;
            Inc(backtrack);
          end;
        end;
      end;
    end;
  finally
    SetLength(Result, len);
  end;
end;

Das ist ziemlich genau die implementierung eines backtracking automaten der einen konstanten string finden soll. Und das stichwort hier ist backtracking, also ist das nicht mal das matching eines regulären ausdrucks sondern das suchen eines patterns (und damit statt in O(n) in O(n*m)). D.h. implementierung die so effizient ist wie ein Regex Matching wäre sogar noch komplexer.

Was ist einfacher zu verstehen der regex '.*(PATTERN)' oder die 50 zeilen pascal code da oben? Und da ich den Code oben geschrieben habe kann ich auch aus erfahrung sagen das es ein paar fehler beim entwickeln gab die ich ausbügeln musste, ich glaub ich muss nicht sagen das ich bei '.*pattern' eher selten bugs habe.

Und das ist so ziemlich der einfachst mögliche regex, um das komplizierte pattern was du da gepostet hast effizient zu matchen braucht man bestimmt mehrere hundert zeilen Code.

[theo]

@Warf: Zwei ganz einfache Fragen:

Verstehst du, was das tut?

Code: Alles auswählen

 (\b25[0-5]|\b2[0-4][0-9]|\b[01]?[0-9][0-9]?)(\.(25[0-5]|2[0-4][0-9]|[01]?[0-9][0-9]?)){3} 

(Habe ich aus dem Web kopiert. Ich kann es nicht entschlüsseln, bekomme Kopfschmerzen und Augenflattern)

Verstehst du, was das tut?

Code: Alles auswählen

function isIpAddr(Inp: string): boolean;
var
  sa: TStringArray;
  len, i, vala, code: integer;
begin
  Result := False;
  sa := Inp.split(['.']);
  Len := Length(sa);
  if Len = 4 then
  begin
    for i := 0 to len - 1 do
    begin
      Val(Sa[i], vala, code);
      if (code <> 0) or (vala < 0) or (vala > 255) then exit;
    end;
    Result := True;
  end;
end;  

Habe ich jetzt kurz in ein paar Minuten hingehackt. Nicht getestet.

[Warf]

Du machst aber was anderes als die Regex, die Regex prüft die IP syntaktisch, du prüfst sie semantisch.
Wenn du eine semantische prüfung machst dann kannst du auch eine viel einfachere regex benutzen

Code: Alles auswählen

function isIPv4(const addr: string): boolean;
const
  re: TRegExpr = nil;
begin
  if not Assigned(re) then
    re := TRegExpr.Create('(\d+)\.(\d+)\.(\d+)\.(\d+)');
  Result := (re.Exec(addr))
        And (StrToInt(re.Match[1]) < 256)
        And (StrToInt(re.Match[2]) < 256)
        And (StrToInt(re.Match[3]) < 256)
        And (StrToInt(re.Match[4]) < 256);
end;

Diese regex erkennt man ziemlich einfach als 4 zahlen die von "." getrennt sind. Der semantische check danach ist dann ob die Zahlen auch in die Byte Range von.

Tatsächlich sind semantische checks (sog. context conditions) mit Regex allein nicht immer möglich, da Reguläre Sprachen sehr limitiert sind (Stichwort Pumping Lemma), und wenn es möglich ist dann meistens über sehr viele edge cases die explizit eingebaut werden müssen, wie in deinem beispiel oben (wo z.B. der die erste zahl jeweils nur 0 1 oder 2 sein darf und wenn sie 2 ist darf die nächste zahl nur 0-4 oder 5 sein und wenns 5 ist dann darf die letzte zahl nur 0-5 sein. All das muss explizit encoded werden)

Alles eine Frage wie viel man in Regex machen will und wie viel außerhalb.

[theo]

Alles eine Frage wie viel man in Regex machen will und wie viel außerhalb

Ja klar.
Die Diskussion um Regex ist ja nicht gerade neu.
Für mich passt es einfach nicht so gut zu Pascal. Man trifft es auch selten an in Pascal Code.
Bei PHP, JS o.ä. benutze ich es auch manchmal, wenn es sich anbietet und versehe es mit einem Kommentar.
Eine Regex basteln ist oft noch einfacher als eine Regex entziffern..

[Warf]

Für mich passt es einfach nicht so gut zu Pascal. Man trifft es auch selten an in Pascal Code.
Bei PHP, JS o.ä. benutze ich es auch manchmal, wenn es sich anbietet.

Ich meine (kann sein das ich mich da falsch erinnere) das die Regex Implementierung "relativ" neu ist (wurde glaube ich erst in den 2010ern eingeführt). Tatsächlich finde ich hat man in den letzten 5-6 Jahren deutlich öfter TRegExpr (zumindest bei Fragen hier oder im Englischen Forum) gesehen als vorher.
Bei einer Sprache wo die meisten Programmierer sie schon seit 30 Jahren + verwenden, brauchts manchmal ein bisschen bis neuerungen viel eingesetzt werden, was natürlich auch verständlich ist, da man einfach extrem viel alten Code der super funktioniert rumliegen hat den man einfach wieder verwenden kann. Schau dir Generics an, die gibts jetzt auch schon ewig und werden noch recht wenig verwendet, obwohl generische Listen viel angenehmer sind als das Pointer jonglieren mit der klassischen TList.

[theo]

Schau dir Generics an, die gibts jetzt auch schon ewig und werden noch recht wenig verwendet, obwohl generische Listen viel angenehmer sind als das Pointer jonglieren mit der klassischen TList.

Das mag sein, aber ich verwende die "neuen" Features wie Advanced Records oder Generics durchaus, da sie eindeutige Vorteile bringen, wenn man einmal verstanden hat, worum es geht.
Regex stehe ich skeptischer gegenüber, das sie der Leserlichkeit des Codes aus meiner Sicht nicht dienlich sind.

Mich erinnert dein Vergleich ein bisschen an das Beispiel, welches immer wieder gerne gebracht wurde, dass Verbrenner-Autos wie klassische Kameras mit Filmmaterial (Kodak) seien.
Nur musste man Digitalkameras nicht staatlich "fördern". Das wirklich Bessere setzt sich von selbst durch.

[Warf]

Das Ding ist, viele die evtl nicht aus der Theoretischen Ecke kommen, verstehen Regex potentiell nicht so ganz. Ich weis das weil ich dazu gehörte. Ich hab schon lang bevor ich Informatik Studiert habe bereits schon Programmiert, halt ohne das Theoretische Grundwissen. Da stolpert man ab und an über Regex, doch meist aus rein praktischer Sicht, das man damit XYZ machen kann.
Dann sieht man es sich an und denkt sich "das sieht ja kompliziert aus, da bau ich mir meine Funktion lieber selbst". Aber was der große unterschied zwischen Regex und den meisten (naiv) gebauten eigenkreationen ist, Regex ist algorithmisch Optimal, also alles was man selbst baut kann im besten fall nur so effizient sein wie Regex. Und das ist ein wichtiger punkt.

Wenn ich mir schnell was selbst zusammen baue, dann hat das normalerweise eine Kombination aus mehrfachen aufrufen von "pos", string iterationen und co, was zwar schnell gebaut ist aber oftmals unnötig oft über den String laufen muss. Regex ist immer optimal.

Klar kann man sich entscheiden trozdem was selbst zu bauen, mach ich auch oft. Doch man sollte immer im hinterkopf haben das alles was man selbst baut im endeffekt entweder nicht so effizient wie Regex sein wird, oder extrem komplizierter code wird (Automaten nachbauen in imperativen sprachen ist aufwendig), Und das ist auch etwas was man bei so Forenthemen herforheben sollte, denn viele die das lesen sind evtl (so wie ich bevor ich die Theoretische Ausbildung an der Uni bekommen hab) nicht so vertraut mit der Theorie das sie das wissen

Und das sollte man in Form von Wissensweitergabe schon fördern. Ich finde man sollte immer wenn möglich auch die Theorie versuchen mitzuerklären und warum etwas was eventuell auf den ersten Blick alles zu verkomplizieren scheint, potentiell doch besser ist

[theo]

Du sprichst von Effizienz, ich von Leserlichkeit / Nachvollziehbarkeit / Wartbarkeit.
Das sind zwei paar Schuhe.

Wenn ich das richtig mitbekommen habe, hast du auch als Experte nicht auf Anhieb verstanden, was dieser Ausdruck tut.

Code: Alles auswählen

 (\b25[0-5]|\b2[0-4][0-9]|\b[01]?[0-9][0-9]?)(\.(25[0-5]|2[0-4][0-9]|[01]?[0-9][0-9]?)){3} 

Nur darum geht es mir.

[kupferstecher]

Das ist ziemlich genau die implementierung eines backtracking automaten der einen konstanten string finden soll. Und das stichwort hier ist backtracking, also ist das nicht mal das matching eines regulären ausdrucks sondern das suchen eines patterns (und damit statt in O(n) in O(n*m)). D.h. implementierung die so effizient ist wie ein Regex Matching wäre sogar noch komplexer.

Der Regexautomat muss doch auch das Pattern auf Byteebene durchprobieren. Der Faktor m (steht wohl für die Länge des Pattern) ist dann halt in O versteckt.

[m.fuchs]

Anmerkung: Ich gehe im folgenden davon aus, dass ein REGEX-Ausdruck einer (lesbaren) Eigenentwicklung in Pascal in Punkto Effizienz überlegen ist.
Ich reduziere also die Fragestellung auf Effizienz vs. Lesbarkeit.

Von allen in- und externen Projekten bei denen ich in den letzten zehn Jahren um Rat gebeten wurde, gab es exakt einen Fall bei dem es um die langsame Ausführungsgeschwindigkeit des Programms ging. Aber echt viele bei denen die Entwickler nicht mehr durch eigenen (oder schlimmer durch fremden) Quellcode durchgeblickt haben.
Und noch besser: bei dem genannten einen Fall habe ich über 800 Zeilen PHP-Quellcode durchforstet, einen unnötigen Aufruf aus einer Schleife herausgenommen und vor dem Schleifenaufruf eingesetzt und damit die Ausführungsgeschwindigkeit von über fünf Sekunden auf unter 300 Millisekunden gesenkt. Hatte der entsprechende Entwickler verbasselt, weil er in seinem eigenen Code nicht mehr durchsah.

Ich sage daher: Vergesst erst einmal die Effizienz des Quellcodes, was richtig Arbeitszeit (und damit Geld) kostet ist nicht-lesbarer Quellcode. In den meisten Fällen wird sich auch die Frage nach 50 Millisekunden mehr gar nicht stellen, einfach weil der Benutzer dies niemals bemerkt. Bei der Originalfragestellung im Ursprungs-Thread wird das wohl auch so sein - Einlesen und Bearbeiten von Config-Dateien ist selten etwas zeitkritisches.

Was aber, wenn es doch einmal um die Geschwindigkeit geht? Dann hilft ein sauber strukturiertes Projekt ebenfalls.

Man startet mit seiner selbstgebastelten Funktion die den String durchsucht und das Ergebnis zurückgibt. Dann ein paar Unittests die alle wichtigen Fälle durchspielen.
Und anschließend kann optimiert werden. Funktion anpassen, eigene Stringverarbeitung durch REGEX ersetzen, oder auch einen externen REGEX-Experten einschalten der das baut - all das ist dann problemlos möglich. Denn solange die Tests immer noch funktionieren, hat man nichts kaputtgemacht. Und wenn dann doch mal ein Test fehlschlägt? Dann geht man wieder einen Schritt im Versionskontrollsystem zurück und probiert es von neuem. Diese Tests sind übrigens auch ein ganz guter Ort um mal vergleichende Geschwindigkeitstests durchzuführen.

Von daher sieht mein Ablauf so aus:

• Test implemtieren
• Funktion implementieren (in Pascal)
• Ist das ausreichend schnell? => Nix mehr tun.
• Ist es zu langsam? => Optimieren mit allen Mitteln. Und dem guten Gefühl das nix kaputt gehen kann.

[Warf]

Wenn ich das richtig mitbekommen habe, hast du auch als Experte nicht auf Anhieb verstanden, was dieser Ausdruck tut.

Code: Alles auswählen

 (\b25[0-5]|\b2[0-4][0-9]|\b[01]?[0-9][0-9]?)(\.(25[0-5]|2[0-4][0-9]|[01]?[0-9][0-9]?)){3} 

Nur darum geht es mir.

Wenn man regex im vakuum betrachtet dann ist es natürlich etwas aufwendiger rauszubekommen, aber nehmen wir mal ne realistische situation an, man findet diese Zeile:

Code: Alles auswählen

IPv4Regexpr := TRegExpr.Create( '(\b25[0-5]|\b2[0-4][0-9]|\b[01]?[0-9][0-9]?)(\.(25[0-5]|2[0-4][0-9]|[01]?[0-9][0-9]?)){3}'); 

Und ich kann dir auf anhieb sagen das das ne IPv4 addresse matchen soll. Wenn man mit dem wissen sich das anschaut macht es auch direkt Sinn.

Ich sage daher: Vergesst erst einmal die Effizienz des Quellcodes, was richtig Arbeitszeit (und damit Geld) kostet ist nicht-lesbarer Quellcode. In den meisten Fällen wird sich auch die Frage nach 50 Millisekunden mehr gar nicht stellen, einfach weil der Benutzer dies niemals bemerkt. Bei der Originalfragestellung im Ursprungs-Thread wird das wohl auch so sein - Einlesen und Bearbeiten von Config-Dateien ist selten etwas zeitkritisches.

Da stimme ich komplett zu, wenn es um simple optimierungen geht, aber algorithmische Effizienz ist ein ganz anderes Biest.
Der unterschied zwischen O(n) und O(n^2) macht vielleicht bei den tests mit ein paar kb nur wenige millisekunden, und dann schiebt der nutzer eine datei von einem MB rein und plötzlich dauerts beim Nutzer jahre. Bei diesem unterschied bedeutet wenn man den Input um einen Faktor 10 größer macht, dauert es 100x länger. Bzw bei dem Beispiel von KB auf MB dauerts halt dann einen Faktor 1000000 länger.
Das sind nicht mal eben 50 millisekunden, das ist der unterschied von 30ms auf über 1 jahr.
Vor allem bedeutet es auch das selbst wenn ich mir einen 10 mal schnelleren rechner hole ich trozdem nur 3x mehr input in der gleichen zeit geparsed bekomme.

Das beste beispiel hier ist Sortieren, Bubble sort sind 5 zeilen oder so extrem einfach zu bauen und zu lesen. Im vergleich dazu sind Quicksort oder heapsort relativ kompliziert. Aber trozdem baut absolut niemand in produktionssoftware Bubblesort ein, genau deshalb, man hat hier nicht das problem von ein paar MS, sondern der Geschwindigkeitsverlust geht relativ schnell in den minuten bis stunden bereich für sachen die sonst in wenigen Sekunden fertig sind.

Der Regexautomat muss doch auch das Pattern auf Byteebene durchprobieren. Der Faktor m (steht wohl für die Länge des Pattern) ist dann halt in O versteckt.

Tatsächlich ist die antwort hier ein klares Jein. Es gibt den unterschied zwischen dem Matchen und dem Finden, beim Matchen (die Frage ob ein string in gänze eine bestimmte form hat) braucht man kein backtracking, da ist die Laufzeit O(n). Beim suchen wo das pattern irgendwo auftauchen kann muss man backtracken und braucht O(n*m) wobei m der maximale substring vom input ist der auf das pattern matchen kann (bei fixen patterns konstant, bei dynamischen ist m potentiell = n und damit ist es O(n^2)).

Allerdings kann man einen Seaching ausdruck in einen Matching ausdruck verwandeln indem man .* davor hängt.
Also der string "Hallo Welt" matcht nicht "Welt" weil noch ein Hallo davor ist aber er matcht ein ".*Welt". Allerdings erlaubt das nicht das mehrfache finden des selben ausdrucks in einem string also "Hallo Welt Welt" würde immer nur das erste "Hallo Welt" matchen, aber das zweite Welt würde man nicht finden können. Dafür wird dann Searching mit Backtracking benötigt.

Im endeffekt kommt das aber auch auf die Implementation an. Ich glaube TRegExpr kann gar nicht Matchen sondern immer Searchen, und durch die Teuren String Operationen ist ein Prefixen mit .* deutlich ineffizienter statt zu searchen. In C++ aber gibt es genau dafür den unterschied zwischen std::regex_match und std::regex_search, genau wegen dieser performance unterschiede.

[m.fuchs]

Da stimme ich komplett zu, wenn es um simple optimierungen geht, aber algorithmische Effizienz ist ein ganz anderes Biest.
Der unterschied zwischen O(n) und O(n^2) macht vielleicht bei den tests mit ein paar kb nur wenige millisekunden, und dann schiebt der nutzer eine datei von einem MB rein und plötzlich dauerts beim Nutzer jahre. Bei diesem unterschied bedeutet wenn man den Input um einen Faktor 10 größer macht, dauert es 100x länger. Bzw bei dem Beispiel von KB auf MB dauerts halt dann einen Faktor 1000000 länger.
Das sind nicht mal eben 50 millisekunden, das ist der unterschied von 30ms auf über 1 jahr.

Ist ja dann auch kein Problem. Im besten Fall wird das auch vorher getestet (Grenzwerte sollten immer getestet werden, auch und gerade maximale Datenmengen). Im schlechten Fall meldet der Benutzer das und dann kann ja tatsächlich optimiert werden.
Ich persönlich würde diese Optimierung dann auch einem REGEX-Guru überlassen, da traue ich mir nicht unbedingt zu das beste Pattern zu erstellen.

[Warf]

Ich persönlich würde diese Optimierung dann auch einem REGEX-Guru überlassen, da traue ich mir nicht unbedingt zu das beste Pattern zu erstellen.

Das ist ja das coole an Regex, automaten minimierung ist ein gelöstes problem wofür wir die optimalen algorithmen kennen, jedes Regex pattern das korrekt ist, selbst wenn es nicht sehr schön ist, wird beim kompilieren auch gleichzeitig optimal. Bis auf sowas wie praktische Limitierungen (stellt sich raus das man nicht in einer perfekt theoretischen Welt lebt).

Aber ja ich kann das voll und ganz verstehen, ich finde zu große Regex auch nicht schön. Meine faustregel ist, bevor man sich am Regex tot arbeitet lieber ein einfaches Regex benutzen und zusätzliche strukturen drum herum bauen als was zu basteln wozu man am ende ne eigene Dokumentation braucht warum das funktioniert.
Ich würd z.B. sowas was theo da gepostet hat auch nie selbst verwenden. Aber alles eine frage des Contexts und wie strikt man sein will/muss (generell in ser strikten dateiformaten braucht man keine so elaborierten regex da man ein gewisses grundformat annehmen kann und das nicht im regex verifizieren muss).