fastwild - Wildcard matching mit Kompilierung zur Laufzeit

[I.MacLeod]

Aloah,

so, nachdem ich diese Unit schon im DF veröffentlicht habe (und sie brav in meinem aktuellen Projekt ihren Dienst verrichtet), werde ich dies dann jetzt endlich auch hier nachholen. Vielleicht kann der/die ein oder andere sie ja gebrauchen. (Hoffe ich zumindest mal)


nochmal 1. September: da hat sich ein kleiner Bug eingeschlichen. (Das kommt davon, wenn das Testprogramm so viele Fälle bearbeitet, dass man die oberen nicht mehr sieht, und einfach davon ausgeht, dass sie immernoch stimmen). "??" hatte sich verhalten wie "???*" (zumindest soweit ichs gesehn hab)
Jetzt sollte wieder alles funktionieren.

1. September: Ich hab mich kurzerhand dazu entschlossen auf eine 0.5 final zu verzichten, ein paar neue Optimierungen einzubauen und das Ergebnis 0.6 zu nennen. String-Vergleiche sollten nochmal was schneller durchlaufen.

28. August: Hier ist eine neue Betaversion. String-Blöcke mit einer Länge von 3 oder mehr als 4 werden jetzt wesentlich schneller verarbeitet. Ein Test von "simpletest" auf "simpletest" läuft beispielsweise ~ 7x so schnell durch. Download unten. Die äußerst zahlreichen Bugs bitte an mich weiterleiten - bei meinen Tests hat allerdings alles funktioniert.


Folgende Methoden werden zur Verfügung gestellt:

• function CompileWildcardFunction(Pattern: AnsiString): TWildcardFunction; Erzeugt eine Funktion, die einen string mit "Pattern" vergleicht.
• procedure FreeWildCardFunction(WildcardFunction: TWildcardFunction); Gibt eine mit CompileWildcardFunction erzeugte Funktion wieder frei.

Unterstützte Platzhalter:

• Code:

    *

  ein beliebiger Text
• Code:

    ?

  ein beliebiges Zeichen
• Code:

  [...]

  sets mit ein paar Zusatzfunktionen

Beispiele:

• Code:

  [a-z]

  a, b, c, ..., oder z
• Code:

  [z-a]

  z, - oder a
• Code:

  [a-]

  a oder -
• Code:

  *oo

  foo oder zoo oder shampoo oder ...
• Code:

  [*a-z]

  beliebig viele Buchstaben zwischen a und z.
  Zum Beispiel "hallo", aber nicht "Hallo"
• Code:

  [+a-z]

  mindestens ein Buchstabe zwischen a und z
  Zum Beispiel "hallo", aber nicht "" (leerer String)
• Code:

  [!a-z]

  ein Buchstabe nicht zwischen a und z
  zum Beispiel "H"
• Code:

  [!*a-z]

  beliebig viele Buchstaben nicht zwischen a und z
  zum Beispiel "HALLO"
• Code:

  [[-\]]

  ein Buchstabe zwischen [ und ]
• Code:

  A\*

  der Text "A*"
• Code:

  [+a-zA-Z]

  Hallo, hallo, HALLO, ...

Code-Beispiel:

Delphi-Quellcode:

var
  fkt: TWildcardFunction;
begin
  fkt := CompileWildcardFunction(eWildcard.Text);
  try
    if fkt(PChar(eText.Text)) then
      lAusgabe.Caption := 'Ja'
    else
      lAusgabe.Caption := 'Nein';
  finally
    FreeWildCardFunction(fkt);
  end;
end;

Natürlich ist die ganze kompiliererei in diesem Beispiel überflüssig - wenn ein paar tausend Dateinamen überprüft werden lohnt sich das natürlich schon eher ^^.

Bekannte Bugs:

• derzeit keine, aber Patterns, die nicht funktionieren wie sie sollen, sind immer willkommen.

Wer will, kann (sofern er D2005 nutzt) irgendwo oben noch {$DEFINE D2005} einfügen, dann wird die Freigabe zur Inlinefunktion.

Cheers

[shmia]

Hut ab, das ist ja fast schon kriminell, wie du da die X86 Assemblercodes zusammenbaust!!
Hallo du eine Liste von Patterns und zugehörigen Strings sammt Ergebnis ?

Code:

pattern    string                   Result
==========================================
[*a-z]     hallo                    True
[*a-z]     Hallo                    False
[+0-7]     12                       True
[+0-7]     87                       False

Falls ja, dann sollte man diese Liste immer weiter pflegen und daraus einen UnitTest bauen.
Das gibt Dir (und uns) die Sicherheit, dass durch eine Änderung am Code keine neuen Bugs erzeugt werden.

[I.MacLeod]

Erstmal: Danke für das Lob!

Die Idee ist gut, bisher hab ich einfach immer bei jedem neuen Feature daran rumgetestet, aber so gehts wirklich einfacher. Ich hab mal schnell was zusammengehackt:

Ich glaube aber, die wirklichen Problemfälle fehlen noch.

Delphi-Quellcode:

program test;

{$APPTYPE CONSOLE}

uses
  fastwild;

const
  TrueTests: array[0..18, 0..1] of string = (
    ('', ''),
    ('a', 'a'),
    ('?', 'a'),
    ('??', 'ab'),
    ('*', ''),
    ('*', 'a'),
    ('*', 'aa'),
    ('*???', 'abc'),
    ('*???', 'abcd'),
    ('*test?*', 'tester'),
    ('*.*', 'fastwild.pas'),
    ('[a-z]', 'a'),
    ('[+a-z]', 'hallo'),
    ('[*a-z]', ''),
    ('[!abc]', 'd'),
    ('[a-]', '-'),
    ('[z-a]', '-'),
    ('[!-c]', 'b'),
    ('*a*b*', 'kebab')
  );

  FalseTests: array[0..4, 0..1] of string = (
    ('a', 'b'),
    ('', 'a'),
    ('*???', 'ab'),
    ('?', ''),
    ('*a*b*', 'erbanlage')
  );

var
  i: integer;
  f: TWildcardFunction;
begin
  WriteLn('         pattern               string     exp.res.    result');
  WriteLn('==============================================================');

  for i := low(TrueTests) to high(TrueTests) do
  begin
    f := CompileWildcardFunction(TrueTests[i, 0]);
    try
      WriteLn(TrueTests[i, 0]:16, TrueTests[i, 1]:21, 'TRUE':13, f(PChar(TrueTests[i, 1])):10);
    finally
      FreeWildcardFunction(f);
    end;
  end;

  for i := low(FalseTests) to high(FalseTests) do
  begin
    f := CompileWildcardFunction(FalseTests[i, 0]);
    try
      WriteLn(FalseTests[i, 0]:16, FalseTests[i, 1]:21, 'FALSE':13, f(PChar(FalseTests[i, 1])):10);
    finally
      FreeWildcardFunction(f);
    end;
  end;

  ReadLn;
end.

Cheers!

[Vjay]

Ich habe deine Unit zwar noch nicht benutzt - lade sie mir aber trotzdem mal, soetwas kann man schließlich immer gebrauchen.

PS. Deine Methode mit dem selbsterstellten Code ist wirklich der Hammer

Wer sich die Unit nicht läd weiß nicht was er daran hat.

Jetzt nur noch erweiterte Befehlssätze abtesten und evtl. einbauen

Merci

[I.MacLeod]

...Danke.

Ich hab eben mal zwei Optimierungen eingebaut, die das Ganze nochmal kräftig beschleunigen (Zumindest bei Stringblöcken der Länge 3 oder 5 und länger). Wäre nett wenn das mal jemand ein bisschen durchtesten könnte (ich habs zwar auch schon getestet, aber wahrscheinlich überseh ich wieder alles).

Cheers!

[I.MacLeod]

So, hier ist Version 0.6. Wie immer, einiges ist schneller geworden.

Als nächstes wird der set-Code ein bissl optimiert (ich hoffe dass das, was ich im Kopf hab auch funktioniert).

PS: besteht interesse an einer Funktion, um Patterns zu kompilieren, auf Festplatte zwischenzulagern und dann (beispielsweise zwecks schnellerem Programmstart) später wieder zu laden?

Cheers!