Hallo, Community von Entwicklern , ich muss den Job beenden.

In meinem vorherigen Werk gab es einen Aufruf, um zu zeigen, wie die Prolog-Sprache verwendet werden kann, und um zu zeigen, dass es lustig wäre. Machen Sie daraus eine Übung.

Ich werde versuchen weiterzumachen vorführen zu demonstrieren.

Ich erinnere mich kurz an die Aufgabe:

Die Vollständigkeit der Lösung konnte nicht nachgewiesen werden. Auf der Site, die die Aufgabe bereitstellt, gibt es 1808 Tests, die nicht sofort angezeigt werden. Sie müssen ein Programm schreiben und einen weiteren Test als Fehler erhalten.

Hardcore, ich habe 66 von ihm bekommen und meine Entscheidung überprüft - während alles funktioniert hat. Aber so einfach kann es nicht sein.

Warum so viele Tests gemacht habe, möchte ich weiter prüfen ...

Ich werde versuchen, diese Lösung in der Sprache umzuschreiben verständlich in diesem System verfügbar (sie spiegeln die Popularität moderner Programmiersprachen wider).

Wählen Sie also Python.

Die Kraft von Prolog liegt im Suchverfahren, dessen Wurzeln in den Methoden zum Beweis von Theoremen liegen . Einfach ausgedrückt, verfügt es über einen integrierten Vereinigungs- und Suchmechanismus mit Rückgabe. Es ist noch einfacher zu sagen, Matching plus Tiefensuche im Entscheidungsbaum.

Und Python ist modernes Pascal (es gibt bereits drei Sprachen mit dem Buchstaben "P"), und die Schüler können Programme darauf schreiben.

Jetzt werde ich die in der vorherigen Implementierung festgelegte Lösung neu schreiben und schnell eine ähnliche Prologsuche mit einer Rückgabe implementieren.

Als nächstes werde ich es im Testsystem starten und sehen, ob die Verschiebung (Code) korrekt war.

Jetzt mitmachen.

Am Eingang die getestete Zeichenfolge und das getestete Muster:

def test(st,pat): if st=="" and pat=="": yield True if pat>"" and pat[0]=='*':yield test(st,pat[1:]) if st>"" and pat>"": if st[0]==pat[0] or pat[0]=='?': yield test(st[1:],pat[1:]) if pat[0]=='*':yield test(st[1:],pat) yield False 

Es scheint der Prolog-Implementierung sehr ähnlich zu sein:

 test_pattrn([],[]). test_pattrn([Ch|UnpTail],[Ch|PatTail]):-test_pattrn(UnpTail,PatTail). test_pattrn([Ch|UnpTail],['?'|PatTail]):-test_pattrn(UnpTail,PatTail). test_pattrn([Ch|UnpTail],['*'|PatTail]):-test_pattrn(UnpTail,['*'|PatTail]). test_pattrn(Str,['*'|PatTail]):-test_pattrn(Str,PatTail). 

Fünf Lösungen, sonst eine Lüge.

Aber wie mache ich eine Rückgabesuche? Dafür verwende ich Yield, wie es dort genannt wird, unvollständige (faule) Berechnungen, Abschluss, ein Element des funktionalen Ansatzes, sag mir ... Es wird etwas zurückgeben, von dem es möglich sein wird, die folgende Lösung zu holen, aber wenn es Wenn dies nicht zur richtigen Antwort führt, gehen wir mit der nächsten Ausbeute zum Programmzweig. Dies ist der Unterschied zur Rendite.

Diese Funktion akzeptiert das Ergebnis des ersten Tests (), wenn es wahr ist, dann ist alles in Ordnung, andernfalls versucht sie erneut zu iterieren, und es wird eine Tiefensuche durchgeführt, die dem Verhalten der Prologausgabe ähnelt.

Hier ist hier ausdrücklich eine Rückgabe erforderlich:

 def run(r): if type(r)==bool: if r==True: return True else: for nr in r: if run(nr):return True return False 

Überprüfen Sie 1

Wow, das ist das Ergebnis: "939/1808 Testfälle bestanden." und "Status: Zeitlimit überschritten".
Genau das habe ich erwartet, eine deklarative Lösung führt nicht immer zu einer zeiteffizienten Implementierung. Transparente Formulierungen sind keine schnellen Formulierungen.

Aber hier ist das Ergebnis der Python, wir werden den geöffneten Test in der Implementierung ab dem ersten Artikel testen und die Zeit messen:

 import time pt=time.time() print(run(test("babaaababaabababbbbbbaabaabbabababbaababbaaabbbaaab","***bba**a*bbba**aab**b"))) print(time.time()-pt) 

Die Ausführungszeit für Python beträgt 11.10963249206543 Sek., Aber etwas zu viel.

Erweiterte Test-Engine für Prolog:

 %unit-tests framework assert_are_equal(Goal, false):-get_time(St),not(Goal),!,get_time(Fin),Per is Fin-St,writeln(Goal->ok:Per/sec). assert_are_equal(Goal, true):- get_time(St),Goal, !,get_time(Fin),Per is Fin-St,writeln(Goal->ok:Per/sec). assert_are_equal(Goal, Exp):-writeln(Goal->failed:expected-Exp). :-assert_are_equal(isMatch(aaabababaaabaababbbaaaabbbbbbabbbbabbbabbaabbababab,'*ab***ba**b*b*aaab*b'),true). 

Und hier ist das Ergebnis des Prologs (beginnend nicht im Online-Editor, lokal, auf derselben Hardware wie die vorherige):

 isMatch(aaabababaaabaababbbaaaabbbbbbabbbbabbbabbaabbababab,*ab***ba**b*b*aaab*b)->ok:2.208951950073242/sec 

Es sieht so aus, als würde ich Python nicht gut verwenden ((ich muss es verbessern, es ist nicht mehr so ​​offensichtlich:

 def test(st,pat): if st==pat: return True if pat>"" and pat[0]=='*': if test(st,pat[1:]):return True if st>"" and pat>"": if st[0]==pat[0] or pat[0]=='?': if test(st[1:],pat[1:]):return True if pat[0]=='*': if test(st[1:],pat):return True return False import time pt=time.time() print(test("babaaababaabababbbbbbaabaabbabababbaababbaaabbbaaab","***bba**a*bbba**aab**b")) print(time.time()-pt) 

Hier ist das Ergebnis: 3.921879768371582 Sek. (Dies ist näher am Original). Wir kehren zum Schiedsrichter zurück:

Und noch einmal.

Ich komme zu dem Schluss, dass der gesamte Testdurchgang über den Zeitrahmen hinausgeht, da die letzten beiden Optionen sehr schnell gelöst werden.

Wir brauchen eine Größenordnungsoptimierung.

Check 2. Wir brauchen Optimierung.

Was sicher bittet, ist die Breitensuche.

Setzen Sie die Entscheidung jedes Zweigs nicht fort, bis wir eine Lüge erhalten und zu einem anderen Zweig zurückkehren, sondern betrachten Sie die Entscheidungen nach Ebenen, gehen Sie für jede Option gleichzeitig nach unten und gehen Sie schrittweise weiter.

Ich werde versuchen, daraus eine Python zu machen, und dann werde ich den Prolog demonstrieren.

 def test(st,pat): if st==pat: return True res=[] #     ,    if pat>"" and pat[0]=='*':res+=[(st,pat[1:])] if st>"" and pat>"": stt=st[1:] if st[0]==pat[0] or pat[0]=='?':res+=[(stt,pat[1:])] if pat[0]=='*':res+=[(stt,pat)] return res def run(st,pat): lev=[(st,pat)] while len(lev)!=0: nxt=set() ##        for s,p in lev: one=test(s,p) if one==True:return True else:nxt.update(set(one)) lev=nxt return False 

Es gibt bereits das Ergebnis für den Test 939, nur 0,01585698127746582 Sek.
und ... URA diese Entscheidung wird getroffen

Prolog

Ich werde versuchen zu zeigen, wie eine Breitensuche in einer deklarativen Implementierung implementiert wird. Zu diesem Zweck gibt es spezielle Prädikate zweiter Ordnung, die Lösungen in einer Liste sammeln können, z. B. bagof, setof, findall.

bagof (+ Vorlage,: Ziel, -Tasche)
Vereinheitlichen Sie die Tasche mit den Alternativen der Vorlage. Wenn Goal neben der mit Template freigegebenen Variablen auch freie Variablen hat, wird bagof / 3 die Alternativen dieser freien Variablen zurückverfolgen und Bag mit den entsprechenden Alternativen von Template vereinheitlichen. Das Konstrukt + Var ^ Goal weist bagof / 3 an, Var in Goal nicht zu binden. bagof / 3 schlägt fehl, wenn Goal keine Lösungen hat.
setof (+ Vorlage, + Ziel, -Set)
Entspricht bagof / 3, sortiert das Ergebnis jedoch mit sort / 2, um eine sortierte Liste von Alternativen ohne Duplikate zu erhalten.

Setof Prädikat funktioniert seitdem gut Er weiß bereits, wie man Duplikate entfernt (in Python musste ich etwas über Sets lernen).

Also erstelle ich ein Prädikat, das eine Lösung auf einer Ebene erhält, sammle es dann mit einem anderen Prädikat und gehe tiefer. Hier ist die vollständige Lösung:

 atom_to_list(Str,[Ch|T]) :- atom_concat(Ch,Rest,Str),atom_length(Ch,1), atom_to_list(Rest,T). %  pattrn(X:X,true). %-      pattrn([Ch|UnpTail]:[Ch|PatTail],UnpTail:PatTail). pattrn([_|UnpTail]:['?'|PatTail],UnpTail:PatTail). pattrn([_|UnpTail]:['*'|PatTail],UnpTail:['*'|PatTail]). pattrn(Str:['*'|PatTail],Str:PatTail). %  true,     ,     next_level(Lev):-member(true,Lev),!. next_level(Lev):-setof(One,SP^(member(SP,Lev),pattrn(SP,One)),Next),!, next_level(Next). test_pattrn(Str,Pat):-next_level([Str:Pat]). isMatch(S,P) :- atom_to_list(S,SL), atom_to_list(P,PL),!, test_pattrn(SL,PL),!. %unit-tests framework assert_are_equal(Goal, false):-get_time(St),not(Goal),!,get_time(Fin),Per is Fin-St, writeln(Goal->ok:Per/sec). assert_are_equal(Goal, true):- get_time(St),Goal, !,get_time(Fin),Per is Fin-St, writeln(Goal->ok:Per/sec). assert_are_equal(Goal, Exp):-writeln(Goal->failed:expected-Exp). %all test :-assert_are_equal(isMatch(aa,a),false). :-assert_are_equal(isMatch(aa,'*'),true). :-assert_are_equal(isMatch(cb,'?a'),false). :-assert_are_equal(isMatch(adceb,'*a*b'),true). :-assert_are_equal(isMatch(acdcb,'a*c?b'),false). :-assert_are_equal(isMatch(aab,'c*a*b'),false). :-assert_are_equal(isMatch(mississippi,'m??*ss*?i*pi'),false). :-assert_are_equal(isMatch(abefcdgiescdfimde,'ab*cd?i*de'),true). :-assert_are_equal(isMatch(zacabz,'*a?b*'),false). :-assert_are_equal(isMatch(leetcode,'*e*t?d*'),false). :-assert_are_equal(isMatch(aaaa,'***a'),true). :-assert_are_equal(isMatch(b,'*?*?*'),false). :-assert_are_equal(isMatch(aaabababaaabaababbbaaaabbbbbbabbbbabbbabbaabbababab,'*ab***ba**b*b*aaab*b'),true). :-assert_are_equal(isMatch(abbbbbbbaabbabaabaa,'*****a*ab'),false). :-assert_are_equal(isMatch(aaabababaaabaababbbaaaabbbbbbabbbbabbbabbaabbababab,'*ab***ba**b*b*aaab*b'),true). :-assert_are_equal(isMatch(babaaababaabababbbbbbaabaabbabababbaababbaaabbbaaab,'***bba**a*bbba**aab**b'),false). 

Hier können Sie sehen, dass die Regel, die zuvor die Suche nach der Vorlage durchgeführt hat, als ob sie einen Übergang entlang der Fläche im Diagramm vorgenommen hätte, jetzt zu einer Reihe von Faktenmustern geworden ist, die mögliche Übergänge (Beziehungen zwischen Zuständen) enthalten. Dies ist eine Beschreibung des Diagramms und kein Code, der sie implementiert.

Und die Ausführung ergibt sich mit der Zeit in Sekunden:

 isMatch(aa, a)->ok:0.00010013580322265625/sec isMatch(aa, *)->ok:4.00543212890625e-5/sec isMatch(cb, ?a)->ok:3.981590270996094e-5/sec isMatch(adceb, *a*b)->ok:0.0001399517059326172/sec isMatch(acdcb, a*c?b)->ok:9.989738464355469e-5/sec isMatch(aab, c*a*b)->ok:4.00543212890625e-5/sec isMatch(mississippi, m??*ss*?i*pi)->ok:0.0003399848937988281/sec isMatch(abefcdgiescdfimde, ab*cd?i*de)->ok:0.0003600120544433594/sec isMatch(zacabz, *a?b*)->ok:9.989738464355469e-5/sec isMatch(leetcode, *e*t?d*)->ok:0.00020003318786621094/sec isMatch(aaaa, ***a)->ok:9.989738464355469e-5/sec isMatch(b, *?*?*)->ok:6.008148193359375e-5/sec isMatch(aaabababaaabaababbbaaaabbbbbbabbbbabbbabbaabbababab, *ab***ba**b*b*aaab*b)->ok:0.0040400028228759766/sec isMatch(abbbbbbbaabbabaabaa, *****a*ab)->ok:0.0006201267242431641/sec isMatch(aaabababaaabaababbbaaaabbbbbbabbbbabbbabbaabbababab, *ab***ba**b*b*aaab*b)->ok:0.003679990768432617/sec isMatch(babaaababaabababbbbbbaabaabbabababbaababbaaabbbaaab, ***bba**a*bbba**aab**b)->ok:0.002460002899169922/sec 

Und dies ist bereits eine erfolgreiche Lösung, nicht nur logisch, sondern auch rechtzeitig.

Schlussfolgerungen

In einem früheren Artikel wollte ich Interesse am Thema eines deklarativen Ansatzes sehen. Das Thema "niasilil solch ein Ansatz" wurde sofort eröffnet, aber das Interesse kann immer noch gezeigt werden. Hier habe ich gezeigt, dass es ein Leistungsproblem gibt, was klar geschrieben steht, funktioniert nicht schnell. Versuche, einen parallelen Prolog zu erstellen, waren erfolglos. Vielleicht ist hier die Frage der Zukunft, kann ein Quantencomputer?
Insgesamt verwenden wir Rätsel auf der oben genannten Seite für einen angenehmen Zeitvertreib mit Bedacht.

Nun, beim nächsten Mal wird versucht, eine weitere schwierige Aufgabe sofort effektiv zu lösen.