Regex vs. Eigenbau (Effizienz vs. Lesbarkeit?)

[Warf]

Abgesehen von der Regex-Theorie gibt es auch noch die Praxis

RegExpr scheint gar nichts mit DFA/NFA zu machen, sondern nur Zeichen für Zeichen den String abzusuchen und bei Alternativen Backtracking zu machen.

Interessant, ich meine das ich mir die mal angesehen hatte und ich was mit NFAs gesehen hatte, scheint aber nicht der Fall zu sein. Kann sein das ichs mit der Unit Regex vertauscht habe die benutzt auf jeden fall NFAs (auch wenn ich mir jetzt nicht genau angesehen habe was die alles macht.

Und natürlich dauert das Kompilieren von Regex zu Automaten verhältnismäßig lang, Regex lohnt sich nur wenn man den regex vorkompilieren kann und den selben ausdruck mehrfach oder auf großen datenmengen verwendet.

[theo]

Habe mal kurz einen Test gemacht.
Ich bin bei dem hier besprochenen isIpAddr Beispiel geblieben und kann keinen eindeutigen Speed-Vorteil bei Regex erkennen.
Es hängt etwas vom Input ab.
Man kann natürlich argumentieren, dass das Problem nicht auf die gleiche Weise gelöst wird und dass ich diesen und jenen Fehler gemacht habe, aber das ist mMn nicht so erheblich.
Wahrscheinlich kriegt man das mit Regex auch schneller hin, aber dazu muss man schon wieder ziemlich viel wissen.
"Einfach so" ist es nicht schneller.

P.S. Habe keine Ahnung von Regex mit FPC. Vielleicht ist meine Anwendung falsch. Bitte dann um Korrektur.
Und ja, meine eigene Funktion prüft nur den Eingabestring und durchsucht natürlich nicht einen ganzen Text.
Deshalb ist dieser Test vielleicht nicht so relevant.

Code: Alles auswählen

uses uregexpr;
...
function isIpAddrRegex(Inp: string): boolean;
var
  r: TRegExpr;
begin
  Result := False;
  r := TRegExpr.Create;
  try
    r.Expression :=
      '(\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}';
    if r.Exec(UTF8Decode(inp)) then
      if r.SubExprMatchCount > 0 then Result := True;
  finally
    r.Free;
  end;
end;

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

procedure TForm1.Button1Click(Sender: TObject);
var
  tick: Int64;
  i, Count: integer;
  res: boolean;
  Srch: string;
  r: TRegExpr;
begin
  Count := 20000;
  Srch := Edit1.Text;

  Tick := GetTickCount64;
  for i := 0 to Count do res := isIpAddr(Srch);
  Memo1.Lines.add('Func: '+(GetTickCount64 - Tick).ToString+'ms '+res.ToString(TUseBoolStrs.True));

  Tick := GetTickCount64;
  for i := 0 to Count do res := isIpAddrRegex(Srch);
  Memo1.Lines.add('Regex Func: '+(GetTickCount64 - Tick).ToString+'ms '+res.ToString(TUseBoolStrs.True));

  Res := False;
  r := TRegExpr.Create;
  try
    Tick := GetTickCount64;
    r.Expression :=
      '(\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}';
    for i := 0 to Count do
      if r.Exec(UTF8Decode(Srch)) then
        if r.SubExprMatchCount > 0 then res := True;
    Memo1.Lines.add('Regex Reuse: '+(GetTickCount64 - Tick).ToString+'ms '+res.ToString(TUseBoolStrs.True));
  finally
    r.Free;
  end;
end;    

[Warf]

Der speed vergleich hinkt allerdings auch ein bisschen, du erstellst in jeder iteration ein TRegExpr und freest es wieder. Create und Free sind, da sie den Memory Manager involvieren grundsätzlich schonmal ziemlich langsam. Gleichzeitig benutzt du immer den gleichen Regex, weshalb es keinen sinn macht immer neu zu erzeugen. Da anscheinend TRegExpr keinen Automaten baut, ist das nicht so tragisch, aber z.B. Python hatte das problem das wenn man einen regex immer wieder gebaut hat das bauen des NFAs ziemlich lange im vergleich zum matchen gedauert hat. Seit Python 2.5 oder so werden daher regex auch gecached damit der overhead nicht immer wieder erzeugt wird.

In C++ gibt es z.B. sogar bestrebungen das bauen der Automaten in die Compiletime zu verlagern, sodass zur laufzeit nur das DFA matching stattfinden muss. Das ist dann richtig schnell.

Um mal kurz den vergleich zu geben zwischen einem DFA und nicht DFA matching, habe ich mal das folgende programm genommen:

Code: Alles auswählen

program Project1;

{$mode objfpc}{$H+}

uses
  SysUtils, classes, uregexpr;

var
  expr: TRegExpr;
  sl: TStringList;
  s: String;
begin
  expr := 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}');
  sl := TStringList.Create;
  try
    sl.LoadFromFile(ParamStr(0));
    if expr.Exec(sl.Text) then
    repeat
      s := expr.Match[0];
      WriteLn(s);
    until not expr.ExecNext;
  finally
    sl.Free;
    expr.Free;
  end;
  ReadLn;
end.  

Und gegen grep (das den regex zu nem DFA kompiliert) auf einem etwas größeren Server log (500mb) antreten lassen um alle ip addressen zu matchen:

Code: Alles auswählen

$> time grep -Eo '(\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}' nextcloud_access_log > /dev/null
grep --color=auto --exclude-dir={.bzr,CVS,.git,.hg,.svn,.idea,.tox} -Eo   >   0.00s user 0.00s system 17% cpu 0.009 total
$> time ./match nextcloud_access_log > /dev/null
./match nextcloud_access_log > /dev/null  49.10s user 0.84s system 98% cpu 50.552 total

Der echte DFA ohne backtracking ist etwa einen faktor 10000 schneller.

Lustigerweise bedeutet das auch das der wohl schnellste weg große strings zu durchsuchen mit dem FPC vermutlich ist grep über TProcess aufzurufen und dessen output zu parsen.

[theo]

Der speed vergleich hinkt allerdings auch ein bisschen, du erstellst in jeder iteration ein TRegExpr und freest es wieder.

Das hatte ich im dritten Test drin. Siehe "Regex Reuse".
Das ist viel besser als der Funktionsaufruf ("'Regex Func"), aber erreicht bei mir teilweise immer noch nicht die Geschwindigkeit von "Func".
Oder meintest du etwas anderes?

Fazit: Regex mit FPC ist nicht so "der Burner"?

[BeniBela]

Wenn man da FLRE nimmt, ist es schneller als Func und auch ungefähr so schnell wie grep

Code: Alles auswählen

Res := False;
  try
    f := TFLRE.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}',[]);
    Tick := GetTickCount64;
    for i := 0 to Count do
      if f.test(Srch) then
        res := True;
    Memo1.Lines.add('FLRE Reuse: '+(GetTickCount64 - Tick).ToString+'ms '+res.ToString(TUseBoolStrs.True));
  finally
    f.Free;
  end;        

[theo]

Wenn man da FLRE nimmt, ist es schneller als Func und auch ungefähr so schnell wie grep

Kannte ich nicht. Hier der Überblick: https://wiki.freepascal.org/RegEx_packages