مرحبًا ، منتدى المطورين ، أحتاج إلى إنهاء المهمة.

في مقالتي السابقة ، كانت هناك دعوة لإظهار كيفية استخدام لغة 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). 

خمسة حلول ، وإلا كذبة.

ولكن كيف أقوم بالبحث بالعودة؟ ، لهذا أستخدم العائد ، كما يطلق عليه هناك ، الحسابات (البطيئة) غير المكتملة ، الإغلاق ، عنصر من النهج الوظيفي ، أخبرني ... أنه سيعيد شيئًا يمكن من خلاله جلب الحل التالي ، ولكن إذا كان إذا لم يؤد ذلك إلى الإجابة الصحيحة ، فسننتقل إلى فرع البرنامج مع العائد التالي ، وهذا هو الفرق من العائد.

ستقبل هذه الوظيفة نتيجة الاختبار الأول () إذا كان صحيحًا ، فكل شيء على ما يرام ، وإلا فستحاول التكرار أكثر ، وسيكون هناك بحث معمق مشابه لسلوك إخراج المقدمة.

هنا ، العودة مطلوبة بشكل خاص هنا:

 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 حالة اختبار". و "الحالة: تجاوز الحد الزمني".
هذا بالضبط ما توقعته ، الحل الإعلاني لا يؤدي دائمًا إلى تنفيذ فعال من حيث الوقت. الصياغة الشفافة ليست صياغة سريعة.

ولكن ، هنا نتيجة الثعبان ، سنختبر الاختبار المفتوح في التنفيذ من المقالة الأولى ، ونقيس الوقت:

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

وقت تنفيذ Python هو 11.10963249206543 ثانية ، لكن قليلاً أكثر من اللازم.

محرك اختبار متقدم لبرولوج:

 %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 

يبدو أنني لا أستخدم الثعبان جيدًا ((، أحتاج إلى تحسينه ، لم يعد الأمر واضحًا:

 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. نحن بحاجة إلى التحسين.

ما يستدعي بالتأكيد هو البحث الأول.

لا تواصل قرار كل فرع حتى نحصل على كذبة ونعود إلى فرع آخر ، ولكن انظر إلى القرارات حسب المستويات ، وانخفض في نفس الوقت لكل خيار وانتقل تدريجياً إلى أبعد من ذلك.

سأحاول أن أجعلها ثعبانًا ، وبعد ذلك سأعرض المقدمة.

 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.

bagof (+ قالب ،: هدف ، حقيبة)
توحيد الحقيبة مع بدائل القالب. إذا كان الهدف يحتوي على متغيرات مجانية إلى جانب المشاركة مع القالب ، فإن bagof / 3 سوف يتراجع عن بدائل هذه المتغيرات المجانية ، ويوحد الحقيبة مع البدائل المقابلة للقالب. يطلب البناء + Var ^ Goal من bagof / 3 عدم ربط Var في Goal. فشل bagof / 3 إذا لم يكن للهدف حلول.
setof (+ قالب ، + هدف ، -إعداد)
يكافئ bagof / 3 ، ولكن يفرز النتيجة باستخدام sort / 2 للحصول على قائمة بالبدائل مرتبة بدون تكرارات.

Setof المسند يعمل بشكل جيد منذ ذلك الحين يعرف بالفعل كيفية إزالة التكرارات (في بايثون ، كان علي أن أتعلم عن المجموعات).

لذا ، سأقوم بعمل مسند يحصل على حل من مستوى واحد ، ثم نجمعه مع مسند آخر وأتعمق ، إليك الحل الكامل:

 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 

وهذا بالفعل حل ناجح ، ليس فقط منطقيًا ولكن أيضًا في الوقت المناسب.

الاستنتاجات

في مقال سابق ، أردت أن أرى الاهتمام بموضوع النهج التعريفي. تم فتح موضوع "مثل هذا النهج" على الفور ، ولكن لا يزال من الممكن إظهار الاهتمام. هنا بينت أن هناك مشكلة في الأداء ، ما يكتب بشكل واضح لا يعمل بسرعة. لم تنجح محاولات إنشاء مقدمة متوازية. ربما هنا سؤال المستقبل هل يمكن لجهاز كمبيوتر الكم ؟؟
إجمالي نستخدم الألغاز في الموقع أعلاه من أجل هواية ممتعة بحكمة.

حسنًا ، في المرة القادمة ، ستكون هناك محاولة لحل مهمة صعبة أخرى على الفور.