嗨， 开发人员社区 ，我需要完成工作。

在我之前的作品中，有一个电话来说明如何使用Prolog语言，并表明它会很有趣。 把它变成练习。

我会继续 炫耀 演示。

我简要回顾一下任务：

无法证明解决方案的完整性。 在提供任务的站点上，有1808个测试无法立即看到，您需要编写一个程序并获得另一个测试作为错误。

顽固，我从他那里得到了66英镑，并检查了我的决定-一切正常。 但这不是那么简单。

为什么要进行这么多测试，我想进一步检查...

我将尝试用该语言重写此解决方案 可以理解的 在该系统中可用（它们反映了现代编程语言的流行）。

因此，选择Python。

Prolog的力量在于搜索过程，其根源于证明定理的方法。 简而言之，它具有内置的统一和搜索机制，并带有返回值。 通过决策树说匹配和深度搜索甚至更简单。

Python是现代的Pascal（已经有三种语言的字母“ P”）， 学生可以在上面编写程序。

现在，我将重写先前实现中提出的解决方案，并快速实现类似的序言搜索，但要返回一个结果。

接下来，我将在测试系统中启动它，然后查看移动（代码）是否正确。

现在加入。

在输入处，测试的字符串和模式：

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 

它似乎与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). 

五种解决方案，否则就是谎言。

但是如何用return进行搜索呢？为此，我使用yield，它被称为那里，未完成的（惰性）计算，闭包（函数方法的一个元素）告诉我...它将返回一些信息，可以从中获取以下解决方案，但如果有的话如果没有得到正确的答案，那么我们将转到下一个收益率的程序分支，这是与return的区别。

如果为true，则此函数将接受第一个test（）的结果，那么一切都很好，否则它将尝试进行更多迭代，并且将进行类似于prolog输出行为的深度搜索。

在这里，这里特别需要返回：

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

检查1

哇，这就是“ 939/1808测试用例通过”的结果。 和“状态：超出时间限制”。
这正是我所期望的，声明式解决方案并不总能带来省时的实现。 透明的措词不是一个快速的措词。

但是，这是python的结果，我们将在第一篇文章的实现中测试打开的测试，并测量时间：

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

Python执行时间是11.10963249206543秒，但是有点太多。

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

这是Prolog的结果（不在本地的在线编辑器中，与上一个相同的硬件开始）：

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

看来我对python的使用不太好（（，我需要改进它，现在不再那么明显了：

 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) 

结果如下：3.921879768371582秒。 （这更接近原始的）。 我们回到仲裁者：

还有一次。

我得出结论，测试的总通过时间超出了时间范围，因为后两个选项可以很快解决。

我们需要一个数量级的优化。

检查2.我们需要优化。

可以肯定的是，广度优先搜索。

在我们撒谎并返回另一个分支之前，不要继续每个分支的决策，而要逐级查看解决方案，同时选择每个选项并逐步走远。

我将尝试使其成为python，然后将演示其序言。

 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 

测试939的结果已经存在，仅0.01585698127746582秒。
和...市建局作出此决定

序言

我将尝试说明如何在声明式实现中实现广度优先搜索。 为此，有一些特殊的二阶谓词可以将解决方案收集到列表中，例如bagof，setof，findall。

bagof（+模板，：目标，-袋）
使用Template的替代方法来统一Bag。 如果Goal除了与模板共享的变量之外还有其他自由变量，bagof / 3将回溯这些自由变量的替代方案，从而将Bag与相应的Template替代方案统一起来。 构造+ Var ^ Goal告诉bagof / 3不要在目标中绑定Var。 如果目标没有解决方案，bagof / 3将失败。
setof（+模板，+目标，-设置）
等效于bagof / 3，但是使用sort / 2对结果进行排序，以获得没有重复项的替代项排序列表。

Setof谓词运作良好，因为 他已经知道如何删除重复项（在python中，我不得不学习集合）。

因此，我将创建一个谓词，该谓词获得一个级别的解决方案，然后与另一个谓词一起收集它并进行更深入的研究，这是完整的解决方案：

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

在这里，您可以看到以前通过模板执行搜索的规则，就像沿着图形中的面孔进行转换一样，现在变成了一组事实模式，其中包含可能的转换（状态之间的关系）-这是图形的描述，而不是实现它的代码。

执行结果以秒为单位：

 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 

这已经是一个成功的解决方案，不仅在逻辑上而且在时间上都是如此。

结论

在上一篇文章中，我希望看到对声明式方法主题的兴趣。 主题“ niasilil这样的方法”立即打开，但仍然可以表现出兴趣。 我在这里表明存在性能问题，清楚地编写并不能很快完成。 尝试创建并行的序言未成功。 也许这是未来的问题，量子计算机可以吗？
总计，我们明智地在上述网站上使用拼图来度过愉快的时光。

好吧，下一次，我们将尝试立即有效地解决另一项艰巨的任务 。