Hai, komunitas pengembang , saya harus menyelesaikan pekerjaan.

Dalam karya saya sebelumnya , ada panggilan untuk menunjukkan bagaimana bahasa Prolog dapat digunakan, dan untuk menunjukkan bahwa itu akan lucu. Ubah itu menjadi latihan.

Saya akan mencoba untuk melanjutkan pamer untuk menunjukkan.

Saya mengingat tugas itu sebentar :

Itu tidak mungkin untuk membuktikan kelengkapan solusi. Di situs yang menyediakan tugas ada 1808 tes yang tidak dapat dilihat langsung, Anda perlu menulis sebuah program dan mendapatkan tes lain sebagai kesalahan.

Hardcore, saya mendapat 66 darinya dan memeriksa keputusan saya - sementara semuanya bekerja. Tapi itu tidak sesederhana itu.

Mengapa begitu banyak tes, saya ingin memeriksa lebih lanjut ...

Saya akan mencoba menulis ulang solusi ini dalam bahasa bisa dimengerti tersedia dalam sistem ini (mereka mencerminkan popularitas bahasa pemrograman modern).

Jadi, pilih Python.

Kekuatan Prolog ada dalam prosedur pencarian, yang akarnya adalah dalam metode pembuktian teorema . Sederhananya, ia memiliki mekanisme unifikasi dan pencarian built-in dengan pengembalian. Bahkan lebih mudah untuk mengatakan pencarian yang cocok dan mendalam melalui pohon keputusan.

Dan Python adalah Pascal modern (sudah ada tiga bahasa dengan huruf "P"), dan siswa dapat menulis program di atasnya.

Sekarang saya akan menulis ulang solusi yang telah ditetapkan dalam implementasi sebelumnya dan segera mengimplementasikan pencarian prolog yang sama dengan pengembalian.

Selanjutnya, saya akan meluncurkannya di sistem pengujian, dan saya akan melihat apakah langkah (kode) itu benar.

Bergabunglah sekarang.

Pada input, string dan pola yang diuji:

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 

Tampaknya sangat mirip dengan implementasi 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). 

Lima solusi, sebaliknya bohong.

Tapi bagaimana melakukan pencarian dengan return ?, untuk ini saya menggunakan hasil, seperti yang disebut di sana, perhitungan (malas) yang belum selesai, penutupan, elemen dari pendekatan fungsional, katakan padaku ... Ini akan mengembalikan sesuatu yang memungkinkan untuk mengambil solusi berikut, tetapi jika itu Jika tidak mengarah ke jawaban yang benar, maka kami akan pergi ke cabang program dengan hasil berikutnya, ini adalah perbedaan dari pengembalian.

Fungsi ini akan menerima hasil dari tes pertama () jika benar maka semuanya baik-baik saja, jika tidak maka akan mencoba untuk beralih lagi, dan akan ada pencarian mendalam yang mirip dengan perilaku output prolog.

Di sini, pengembalian diperlukan secara khusus di sini:

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

Periksa 1

Wow, inilah hasilnya, "939/1808 uji kasus lulus." dan "Status: Batas Waktu Melebihi".
Inilah yang saya harapkan, solusi deklaratif tidak selalu mengarah pada implementasi yang efisien waktu. Kata-kata transparan bukanlah kata yang cepat.

Tapi, ini adalah hasil dari python, kami akan menguji tes yang dibuka dalam implementasi dari artikel pertama, dan mengukur waktu:

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

Waktu eksekusi Python adalah 11.10963249206543 detik., Tapi agak terlalu banyak.

Mesin uji lanjutan untuk 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). 

Dan ini adalah hasil dari Prolog (dimulai bukan di editor online, secara lokal, pada perangkat keras yang sama dengan yang sebelumnya):

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

Sepertinya saya tidak menggunakan python dengan baik ((, saya perlu memperbaikinya, itu tidak begitu jelas lagi:

 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) 

Inilah hasilnya: 3.921879768371582 dtk. (ini lebih dekat ke aslinya). Kami kembali ke arbiter:

Dan sekali lagi.

Saya menyimpulkan bahwa keseluruhan tes melampaui kerangka waktu, karena dua opsi terakhir diselesaikan dengan sangat cepat.

Kami membutuhkan urutan optimasi besar.

Pemeriksaan 2. Kami membutuhkan pengoptimalan.

Yang pasti meminta adalah pencarian pertama kali.

Jangan melanjutkan keputusan masing-masing cabang sampai kita mendapatkan kebohongan dan kembali ke cabang lain, tetapi perhatikan keputusan berdasarkan level, turun pada waktu yang sama untuk setiap opsi dan secara bertahap melangkah lebih jauh.

Saya akan mencoba membuatnya menjadi python, dan kemudian saya akan menunjukkan prolognya.

 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 

Sudah ada hasil untuk tes 939, hanya 0,01585698127746582 detik.
dan ... URA keputusan ini dibuat

Prolog

Saya akan mencoba menunjukkan bagaimana menerapkan pencarian pertama, dalam implementasi deklaratif. Untuk melakukan ini, ada predikat orde kedua khusus yang dapat mengumpulkan solusi ke dalam daftar, misalnya bagof, setof, findall.

bagof (+ Templat ,: Sasaran, -Tas)
Padukan Tas dengan alternatif Templat. Jika Sasaran memiliki variabel bebas selain yang dibagikan dengan Templat, bagof / 3 akan menelusuri kembali alternatif dari variabel-variabel gratis ini, menyatukan Tas dengan alternatif Templat yang sesuai. Konstruk + Var ^ Goal memberi tahu bagof / 3 untuk tidak mengikat Var di Goal. bagof / 3 gagal jika Goal tidak memiliki solusi.
setof (+ Template, + Goal, -Set)
Setara dengan bagof / 3, tetapi mengurutkan hasilnya menggunakan sort / 2 untuk mendapatkan daftar alternatif yang diurutkan tanpa duplikat.

Setof predikat bekerja dengan baik sejak itu dia sudah tahu cara menghapus duplikat (dengan python, saya harus belajar tentang set).

Jadi, saya akan membuat predikat yang mendapat solusi dari satu level, lalu mengumpulkannya dengan predikat lain dan masuk lebih dalam, inilah solusi lengkapnya:

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

Di sini Anda dapat melihat bahwa aturan yang sebelumnya melakukan pencarian dengan templat, seolah-olah membuat transisi sepanjang wajah dalam grafik, kini telah berubah menjadi seperangkat fakta yang berisi kemungkinan transisi (hubungan antar negara) - ini adalah deskripsi grafik, dan bukan kode yang mengimplementasikannya.

Dan hasil eksekusi dengan waktu dalam detik:

 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 

Dan ini sudah merupakan solusi yang berhasil, tidak hanya secara logis tetapi juga dalam waktu.

Kesimpulan

Dalam artikel sebelumnya, saya ingin melihat minat pada topik pendekatan deklaratif. Topik "niasilil pendekatan semacam itu" segera dibuka, tetapi minat masih bisa ditunjukkan. Di sini saya menunjukkan bahwa ada masalah kinerja, apa yang ditulis jelas tidak bekerja dengan cepat. Upaya untuk membuat prolog paralel tidak berhasil. Mungkin di sini adalah pertanyaan masa depan, dapatkah sebuah komputer kuantum ??
Total kami menggunakan teka-teki di situs di atas untuk hiburan yang menyenangkan dengan bijak.

Nah, lain kali, akan ada upaya untuk segera menyelesaikan satu tugas berat lagi secara efektif.