こんにちは、 開発者のコ​​ミュニティ 、仕事を終える必要があります。

私の以前の作品では、Prolog言語がどのように使用されるかを示し、それが面白いことを示すための呼び出しがありました。 それを運動に変えてください。

私は続けようとします 見せびらかす 実証する。

タスクを簡単に思い出します。

ソリューションの完全性を証明することはできませんでした。 タスクを提供するサイトには、すぐには表示できない1808テストがあります。プログラムを作成し、エラーとして別のテストを取得する必要があります。

ハードコア、私は彼から66を得て、私の決定をチェックしました-すべてはうまくいきました しかし、それほど単純なことはできません。

なぜこれほど多くのテストを行ったのか、さらに確認したい...

このソリューションを言語で書き直そうとします 分かりやすい このシステムで利用可能です（最新のプログラミング言語の人気を反映しています）。

したがって、Pythonを選択してください。

Prologの力は検索手順にあり、そのルーツは定理を証明する方法にあります。 簡単に言うと、組み込みの統合および検索メカニズムとリターンがあります。 決定木を介したマッチングと深さの検索を言うのはさらに簡単です。

また、Pythonは最新のPascal（文字「P」が付いた3つの言語が既にあります）であり、 学生はそれにPythonでプログラムを書くことができます。

ここで、以前の実装で作成されたソリューションを書き直し、同様のプロローグ検索をすばやく実装します。

次に、テストシステムで起動し、移動（コード）が正しいかどうかを確認します。

今すぐ参加してください。

入力では、テストされた文字列とパターン：

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

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

5つのソリューション、それ以外は嘘。

しかし、どのようにリターン検索を行うのですか？これのためにそこに呼ばれるyieldを使用します、未完成の（怠yな）計算、クロージャ、機能的なアプローチ要素、教えてください...正しい答えが得られない場合、次の利回りでプログラムブランチに進みます。これはリターンとの違いです。

この関数は、最初のテスト（）の結果を受け入れます（trueの場合はすべて正常です。それ以外の場合は、さらに反復しようとします。プロローグ出力の動作と同様の深さ検索があります）。

ここでは、ここで特に返品が必要です。

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

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

そして、プロローグの結果は次のとおりです（オンラインエディターではなく、ローカルで、前のハードウェアと同じハードウェアで実行されます）。

 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つのオプションは非常に迅速に解決されるため、テストの合計通過は時間枠を超えると結論します。

桁違いの最適化が必要です。

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秒しかありません。

そして... URAこの決定が下されます

プロローグ

宣言的な実装で幅優先検索を実装する方法を示します。 これを行うには、bagof、setof、findallなど、ソリューションをリストに収集できる特別な2次述語があります。

bagof（+テンプレート、目標、-Bag）

テンプレートの代替案でバッグを統合します。 Goalがテンプレートと共有する変数以外に無料の変数を持っている場合、bagof / 3はこれらの無料の変数の代替をバックトラックし、Bagを対応するテンプレートの代替と統合します。 コンストラクト+ Var ^ Goalは、bagof / 3にGoで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).
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

グラフの面に沿ってトランジションを行うかのようにテンプレートによって以前に検索を実行したルールが、可能性のあるトランジション（状態間の関係）を含む事実pattrnのセットになっていることがわかります-これはグラフの説明であり、それを実装するコードではありません。

そして、実行結果は秒単位の時間で表示されます。

 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
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

そして、これは論理的にだけでなく時間的にもすでに成功したソリューションです。

結論

前回の記事で、宣言的アプローチのトピックに興味を持ちたいと思いました。 「ナイアシリルのようなアプローチ」というトピックがすぐに始まりましたが、関心はまだ示されています。 ここで、パフォーマンスの問題があることを示しました。明らかに書かれているものはすぐには動作しません。 並列プロローグを作成する試みは失敗しました。 多分ここに未来の問題があるのでしょうか、量子コンピューターはできますか？

上記のサイトでは、楽しい娯楽のためにパズルを賢く使用しています。

さて、次回は、もう1つの難しいタスクをすぐに効果的に解決する試みがあります 。