हाय, डेवलपर्स का समुदाय , मुझे काम खत्म करने की आवश्यकता है।

मेरे पिछले ऑप्स में, यह दिखाने के लिए एक कॉल था कि प्रोलॉग भाषा का उपयोग कैसे किया जा सकता है, और यह दिखाने के लिए कि यह मज़ेदार होगा। इसे एक व्यायाम में बदल दें।

मैं जारी रखने की कोशिश करूंगा दिखावा करना प्रदर्शित करने के लिए।

मैं संक्षेप में कार्य को याद करता हूं :

समाधान की पूर्णता को साबित करना संभव नहीं था। साइट पर जो कार्य प्रदान करता है उसमें 1808 परीक्षण होते हैं जिन्हें तुरंत नहीं देखा जा सकता है, आपको एक कार्यक्रम लिखने और एक त्रुटि के रूप में एक और परीक्षण प्राप्त करने की आवश्यकता है।

कट्टर, मुझे उससे 66 मिले और मेरे फैसले को जांचा - जबकि सब कुछ काम किया। लेकिन यह इतना आसान नहीं हो सकता।

इतने सारे परीक्षण क्यों, मैं आगे की जांच करना चाहता हूं ...

मैं इस समाधान को भाषा में फिर से लिखने की कोशिश करूंगा बोधगम्य इस प्रणाली में उपलब्ध (वे आधुनिक प्रोग्रामिंग भाषाओं की लोकप्रियता को दर्शाते हैं)।

इसलिए, पायथन को चुनें।

प्रोलॉग की शक्ति खोज प्रक्रिया में है, जिसकी जड़ें प्रमेय साबित करने के तरीकों में हैं। सीधे शब्दों में कहें, इसमें एक अंतर्निहित एकीकरण और वापसी के साथ खोज तंत्र है। यह कहना और भी आसान है कि निर्णय वृक्ष के माध्यम से अधिक गहराई से मिलान किया जाए।

और पायथन आधुनिक पास्कल है ("पी" अक्षर के साथ पहले से ही तीन भाषाएं हैं), और छात्र इस पर कार्यक्रम लिख सकते हैं ।

अब मैं उस समाधान को फिर से लिखूंगा जो पिछले कार्यान्वयन में निर्धारित किया गया था और जल्दी से वापसी के साथ एक समान प्रस्तावना खोज को लागू करें।

अगला, मैं इसे परीक्षण प्रणाली में लॉन्च करूंगा, और मैं देखूंगा कि क्या कदम (कोड) सही था।

अब सम्मिलित हों।

इनपुट पर, परीक्षण स्ट्रिंग और पैटर्न:

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 

यह प्रोलॉग कार्यान्वयन के समान प्रतीत होता है:

 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) 

पायथन का निष्पादन समय 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). 

और यहाँ प्रोलॉग का परिणाम है (ऑनलाइन संपादक में नहीं, स्थानीय रूप से, पिछले एक के समान हार्डवेयर पर):

 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 सेकंड।
और ... यूआरए यह निर्णय किया जाता है

प्रस्तावना

मैं एक घोषणात्मक कार्यान्वयन में, चौड़ाई-पहली खोज को लागू करने का तरीका दिखाने की कोशिश करूंगा। ऐसा करने के लिए, विशेष दूसरे क्रम के विधेय हैं जो सूची में समाधान एकत्र कर सकते हैं, उदाहरण के लिए बैगोफ़, सेटोफ़, फाइंडॉल।

bagof (+ टेम्प्लेट, लक्ष्य: -बाग)
टेम्पलेट के विकल्पों के साथ बैग को एकीकृत करें। यदि Goal के पास टेम्पलेट के साथ एक साझाकरण के अलावा मुफ्त चर हैं, तो bagof / 3 इन मुफ्त चर के विकल्पों पर पीछे हट जाएगा, टेम्पलेट के संगत विकल्पों के साथ बैग को एकीकृत करता है। कंस्ट्रक्शन + वार ^ गोल, बैगो / 3 को बताता है कि वर को गोल में न बांधें। bagof / 3 विफल रहता है यदि लक्ष्य का कोई हल नहीं है।
सेटऑफ (+ टेम्प्लेट, + लक्ष्य,-सेट)
बैगोफ़ / 3 के बराबर, लेकिन डुप्लिकेट के बिना विकल्पों की क्रमबद्ध सूची प्राप्त करने के लिए सॉर्ट / 2 का उपयोग करके परिणाम को सॉर्ट करें।

सेटोफ प्रेडिकेट तब से अच्छा काम करता है वह पहले से ही जानता है कि डुप्लिकेट को कैसे निकालना है (अजगर में, मुझे सेट के बारे में सीखना था)।

इसलिए, मैं एक विधेय बनाता हूं जिसे एक स्तर का समाधान मिलता है, फिर इसे किसी अन्य विधेय के साथ एकत्रित करें और गहराई से जाएं, यहां पूरा समाधान है:

 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" तुरंत खोला, लेकिन ब्याज अभी भी दिखाया जा सकता है। यहां मैंने दिखाया कि प्रदर्शन की समस्या है, जो स्पष्ट रूप से लिखा गया है वह जल्दी से काम नहीं करता है। एक समानांतर प्रस्तावना बनाने के प्रयास असफल रहे। शायद यहाँ भविष्य का सवाल है, क्या क्वांटम कंप्यूटर हो सकता है ??
कुल मिलाकर हम एक सुखद शगल के लिए उपरोक्त साइट पर पहेली का उपयोग बुद्धिमानी से करते हैं।

खैर, अगली बार, एक और कठिन कार्य को प्रभावी ढंग से हल करने का प्रयास किया जाएगा।