Salut, communauté de développeurs , je dois terminer le travail.

Dans mon précédent opus, il y avait un appel pour montrer comment le langage Prolog peut être utilisé et pour montrer que ce serait drôle. Transformez-le en exercice.

Je vais essayer de continuer montrer pour démontrer.

Je rappelle brièvement la tâche:

Il n'a pas été possible de prouver l'exhaustivité de la solution. Sur le site qui fournit la tâche, il y a 1808 tests qui ne peuvent pas être vus immédiatement, vous devez écrire un programme et obtenir un autre test en tant qu'erreur.

Hardcore, j'ai obtenu 66 de lui et vérifié ma décision - pendant que tout fonctionnait. Mais ça ne peut pas être aussi simple.

Pourquoi avoir fait autant de tests, je veux vérifier plus loin ...

Je vais essayer de réécrire cette solution dans la langue compréhensible disponibles dans ce système (ils reflètent la popularité des langages de programmation modernes).

Alors, choisissez Python.

Le pouvoir de Prolog réside dans la procédure de recherche, dont les racines se trouvent dans les méthodes de démonstration des théorèmes . Autrement dit, il dispose d'un mécanisme intégré d'unification et de recherche avec retour. Il est encore plus simple de dire une correspondance plus une recherche en profondeur dans l'arbre de décision.

Et Python est un Pascal moderne (il y a déjà trois langues avec la lettre "P"), et les étudiants peuvent écrire des programmes dessus.

Maintenant, je vais réécrire la solution qui était prévue dans l'implémentation précédente et implémenter rapidement une recherche de prologue similaire avec un retour.

Ensuite, je vais le lancer dans le système de test, et je vais voir si le mouvement (code) était correct.

Rejoignez-nous maintenant.

En entrée, la chaîne et le motif testés:

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 

Il semble être très similaire à l'implémentation de Prolog:

 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). 

Cinq solutions, sinon un mensonge.

Mais comment faire une recherche avec retour?, Pour cela j'utilise le rendement, comme on l'appelle là, des calculs inachevés (paresseux), la fermeture, un élément de l'approche fonctionnelle, dites-moi ... Il renverra quelque chose dont il sera possible de chercher la solution suivante, mais si elle Si cela ne mène pas à la bonne réponse, alors nous irons à la branche du programme avec le rendement suivant, c'est la différence par rapport au retour.

Cette fonction acceptera le résultat du premier test () si elle est vraie alors tout va bien, sinon elle essaiera de réitérer, et il y aura une recherche en profondeur similaire au comportement de la sortie prologue.

Ici, le retour est spécifiquement nécessaire ici:

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

Contrôle 1

Wow, voici le résultat, "les cas de test 939/1808 ont été passés." et "Statut: Délai dépassé".
C'est exactement ce à quoi je m'attendais, une solution déclarative ne conduit pas toujours à une implémentation efficace en temps. Une formulation transparente n'est pas une formulation rapide.

Mais, voici le résultat du python, nous allons tester le test ouvert dans l'implémentation du premier article, et mesurer le temps:

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

Le temps d'exécution de Python est de 11.10963249206543 sec., Mais un peu trop.

Moteur de test avancé pour 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). 

Et voici le résultat du Prolog (démarrant pas dans l'éditeur en ligne, localement, sur le même matériel que le précédent):

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

On dirait que je n'utilise pas bien python ((, j'ai besoin de l'améliorer, ce n'est plus si évident:

 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) 

Voici le résultat: 3,921879768371582 sec. (c'est plus proche de l'original). Revenons à l'arbitre:

Et encore une fois.

Je conclus que le passage total des tests dépasse le délai, car les deux dernières options sont résolues très rapidement.

Nous avons besoin d'un ordre d'optimisation de l'ordre de grandeur.

Contrôle 2. Nous avons besoin d'optimisation.

Ce qui est sûr, c'est la recherche en premier.

Ne continuez pas la décision de chaque branche jusqu'à ce que nous obtenions un mensonge et revenons à une autre branche, mais regardez les décisions par niveaux, en descendant en même temps pour chaque option et en allant progressivement plus loin.

Je vais essayer d'en faire un python, puis je ferai la démonstration du prologue.

 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 

Il y a déjà le résultat du test 939, seulement 0,01585698127746582 sec.
et ... URA cette décision est prise

Prologue

Je vais essayer de montrer comment implémenter une recherche en largeur, dans une implémentation déclarative. Pour ce faire, il existe des prédicats spéciaux de second ordre qui peuvent collecter des solutions dans une liste, par exemple bagof, setof, findall.

bagof (+ Template ,: Goal, -Bag)
Unify Bag avec les alternatives de Template. Si Goal a des variables libres en plus de celle qui partage avec Template, bagof / 3 reviendra sur les alternatives de ces variables libres, unifiant Bag avec les alternatives correspondantes de Template. La construction + Var ^ Goal indique à bagof / 3 de ne pas lier Var dans Goal. bagof / 3 échoue si Goal n'a pas de solution.
setof (+ Template, + Goal, -Set)
Équivalent à bagof / 3, mais trie le résultat à l'aide de sort / 2 pour obtenir une liste triée d'alternatives sans doublons.

Setof prédicat fonctionne bien depuis il sait déjà comment supprimer les doublons (en python, j'ai dû me renseigner sur les ensembles).

Donc, je vais créer un prédicat qui obtient une solution d'un niveau, puis le collecter avec un autre prédicat et aller plus loin, voici la solution complète:

 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). 

Ici, vous pouvez voir que la règle qui effectuait auparavant la recherche par le modèle, comme si elle effectuait une transition le long du visage dans le graphique, s'est maintenant transformée en un ensemble de faits pattrn qui contiennent des transitions possibles (relations entre états) - il s'agit d'une description du graphique, et non d'un code qui le met en œuvre.

Et l'exécution résulte en temps en secondes:

 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 

Et c'est déjà une solution réussie, non seulement logiquement mais aussi dans le temps.

Conclusions

Dans un article précédent, je voulais voir l'intérêt pour le sujet d'une approche déclarative. Le sujet "niasilil une telle approche" s'est immédiatement ouvert, mais l'intérêt peut encore se manifester. Ici, j'ai montré qu'il y a un problème de performances, ce qui est écrit clairement ne fonctionne pas rapidement. Les tentatives de création d'un prologue parallèle ont échoué. Voici peut-être la question de l'avenir, un ordinateur quantique peut-il être ??
Au total, nous utilisons des puzzles sur le site ci-dessus pour un passe-temps agréable à bon escient.

Eh bien, la prochaine fois, il y aura une tentative de résoudre immédiatement et efficacement une autre tâche difficile .