तो, समुदाय, मैं आपको तीसरी बार आपको आश्चर्यचकित करने का मौका देने के लिए कहता हूं, पिछले फैसले में मैंने अजगर का इस्तेमाल किया था, मुझे लगा कि मैं यहां विशेषज्ञों का ध्यान आकर्षित करूंगा और वे तुरंत मुझे बताएंगे कि ऐसा क्यों करना है, सामान्य तौर पर नियमित अभिव्यक्ति होती है - मैंने इसे किया और सब कुछ सुनिश्चित है काम करेंगे, यह हमारे अजगर बाहर और अधिक गति दे सकते हैं।

लेख का अगला विषय बदले में एक और कार्य होना चाहिए, लेकिन नहीं, पहले वाले ने मुझे नहीं छोड़ा, इससे भी तेज समाधान प्राप्त करने के लिए क्या किया जा सकता है, क्योंकि साइट पर जीत को एक और प्रतियोगिता के साथ ताज पहनाया गया था।

मैंने एक कार्यान्वयन लिखा, जो औसतन, इस तरह की गति का था, इसका मतलब है कि अभी भी 90 प्रतिशत समाधान हैं जो मैंने नहीं देखा कि कोई जानता है कि इसे और भी तेजी से हल करना है और वह चुप है , और पिछले दो लेखों को देखने के बाद मैंने यह नहीं कहा कि ओह, अगर यह प्रदर्शन का मुद्दा, फिर सब कुछ स्पष्ट है - यहाँ प्रस्तावना फिट नहीं है। लेकिन अब प्रदर्शन के साथ सब कुछ सामान्य है, एक प्रोग्राम की कल्पना करना संभव नहीं है जो कमजोर हार्डवेयर पर चलेगा, "अंत में, इसके बारे में क्यों सोचते हैं?"

कॉल

समस्या को और भी तेजी से हल करने के लिए, एक अजगर था और समय था, और क्या अजगर पर एक तेज़ समाधान है?

मुझे सूचित किया गया है "वाइल्डकार्ड के लिए पायथन 3 ऑनलाइन सबमिशन के 1.55% से अधिक तेजी से रनटाइम: 2504 एमएस।"

मैं आपको चेतावनी देता हूं, आगे विचारों की एक धारा ऑनलाइन है।

1 नियमित?

शायद यहाँ एक नियमित अभिव्यक्ति का उपयोग करके एक तेज कार्यक्रम लिखने का विकल्प है।

जाहिर है, अजगर एक नियमित अभिव्यक्ति ऑब्जेक्ट बना सकता है जो इनपुट लाइन की जांच करेगा और परीक्षण कार्यक्रमों के लिए साइट पर सैंडबॉक्स में, वहीं पर चलाने के लिए निकल जाएगा।
बस पुनः आयात करें , मैं ऐसे मॉड्यूल को आयात कर सकता हूं, यह दिलचस्प है, मुझे कोशिश करनी होगी।

यह समझना आसान नहीं है कि त्वरित समाधान बनाना आसान नहीं है। हमें इस एक के समान खोज, प्रयास और कार्यान्वयन करना होगा:

1. इस नियमितता का एक उद्देश्य बनाओ,
2. चयनित पुस्तकालय के नियमित पुस्तकालय के नियमों द्वारा सही किए गए एक टेम्पलेट पर उसे छोड़ दें,
3. तुलना करें और जवाब तैयार है
देखा:

import re def isMatch(s,p): return re.match(s,pat_format(p))!=None def pat_format(pat): res="" for ch in pat: if ch=='*':res+="(.)*" if ch=='?':res+="." else: res+=ch return res 

यहाँ एक बहुत छोटा समाधान है, जैसे कि सही है।

मैं चलाने की कोशिश कर रहा हूं, लेकिन यह यहां नहीं था, यह पूरी तरह से सही नहीं है, कुछ विकल्प फिट नहीं है, आपको टेम्पलेट में रूपांतरण का परीक्षण करने की आवश्यकता है।

सच्चाई मजाकिया है, मैंने टेम्पलेट और स्ट्रिंग को मिलाया, लेकिन समाधान एक साथ आया, मैंने 1058 परीक्षण पारित किए और असफल रहा, केवल यहां।

मैं एक बार फिर से दोहराता हूं, इस साइट पर वे सावधानीपूर्वक परीक्षणों पर काम कर रहे हैं, जैसा कि ऐसा हुआ, पिछले सब कुछ अच्छा है, लेकिन यहां दो मुख्य मापदंडों को मिलाया गया है और यह दिखाया गया है, यहां टीडीडी के फायदे हैं ...

और ऐसे अद्भुत पाठ पर, मुझे अभी भी एक त्रुटि मिलती है

 import re def isMatch(s,p): return re.match(pat_format(p),s)==None def pat_format(pat): res="" for ch in pat: if ch=='*':res+="(.)*" else: if ch=='?':res+="." else:res+=ch return res 

कठिन

ऐसा लगता है कि यह कार्य विशेष रूप से परीक्षणों के साथ मढ़ा हुआ था ताकि जो लोग नियमित अभिव्यक्ति का उपयोग करना चाहते हैं उन्हें अधिक कठिनाइयों का सामना करना पड़े, मुझे इस समाधान से पहले था, कार्यक्रम में कोई तार्किक त्रुटियां नहीं थीं, लेकिन यहां हमें कई चीजों को ध्यान में रखना होगा।

इसलिए, नियमित अभिव्यक्ति मेल खाती है और पहला परिणाम हमारी रेखा के बराबर होना चाहिए।

जीतना?
नियमित अभिव्यक्ति का उपयोग करने के लिए उसे प्राप्त करना आसान नहीं था, लेकिन यह प्रयास विफल हो गया, यह नियमित करने के लिए ऐसा आसान निर्णय नहीं है। चौड़ाई-पहले खोज समाधान ने तेजी से काम किया।

यहाँ इस तरह के एक कार्यान्वयन है,

 import re def isMatch(s,p): res=re.match(pat_format(p),s) if res is None: return False else: return res.group(0)==s def pat_format(pat): res="" for ch in pat: if ch=='*':res+="(.)*" else: if ch=='?':res+="." else:res+=ch return res 

इस की ओर जाता है:

अपील

प्रिय निवासियों, इसे जांचने का प्रयास करें, और यह अजगर को तीन बनाता है, वह इस कार्य को जल्दी पूरा नहीं कर सकता है:

 import re def isMatch(s,p): res=re.match(pat_format(p),s) if res is None: return False else: return res[0]==s def pat_format(pat): res="" for ch in pat: if ch=='*':res+="(.)*" else: if ch=='?':res+="." else:res+=ch return res ##test 940 import time pt=time.time() print(isMatch("aaaabaaaabbbbaabbbaabbaababbabbaaaababaaabbbbbbaabbbabababbaaabaabaaaaaabbaabbbbaababbababaabbbaababbbba","*****b*aba***babaa*bbaba***a*aaba*b*aa**a*b**ba***a*a*")) print(time.time()-pt) "***** b * ए.बी.ए. *** babaa * bbaba *** एक * Aaba * b * आ ** एक * ख ** बा *** एक * एक *") import re def isMatch(s,p): res=re.match(pat_format(p),s) if res is None: return False else: return res[0]==s def pat_format(pat): res="" for ch in pat: if ch=='*':res+="(.)*" else: if ch=='?':res+="." else:res+=ch return res ##test 940 import time pt=time.time() print(isMatch("aaaabaaaabbbbaabbbaabbaababbabbaaaababaaabbbbbbaabbbabababbaaabaabaaaaaabbaabbbbaababbababaabbbaababbbba","*****b*aba***babaa*bbaba***a*aaba*b*aa**a*b**ba***a*a*")) print(time.time()-pt) 

आप इसे घर पर आजमा सकते हैं। चमत्कार, इसे हल करने में बस एक लंबा समय नहीं लगता, यह जमा देता है, ऊह।

क्या नियमित अभिव्यक्तियाँ प्रदर्शन में घोषित रूप से लंगड़ी हैं?
बयान अजीब है, वे सभी फैशनेबल भाषाओं में मौजूद हैं, इसलिए उत्पादकता को वाह किया जाना चाहिए, लेकिन यहां यह बिल्कुल भी यथार्थवादी नहीं है कि उनमें एक परिमित राज्य मशीन नहीं है?, एक अंतहीन चक्र में क्या होता है ??

वें

मैं एक किताब में पढ़ा था, लेकिन यह बहुत समय पहले था ... गो की नवीनतम भाषा बहुत जल्दी काम करती है, लेकिन नियमित अभिव्यक्ति के बारे में क्या?

मैं उसका परीक्षण करूंगा:

 func isMatch(s string, p string) bool { res:=strings.Replace(p, "*", "(.)*", -1) res2:=strings.Replace(res, "?", ".", -1) r, _ := regexp.Compile(res2) fr:=r.FindAllString(s,1) return !(len(fr)==0 || len(fr)!=0 && fr[0]!=s) } 

मैं मानता हूँ, इस तरह के संक्षिप्त पाठ को प्राप्त करना आसान नहीं था, वहाँ वाक्यविन्यास तुच्छ नहीं है, यहां तक ​​कि सी के ज्ञान के साथ, यह पता लगाना आसान नहीं है ...

यह एक अद्भुत परिणाम है, गति वास्तव में कुल ~ 60 मिलीसेकंड से अधिक है, लेकिन यह आश्चर्यजनक है कि यह समाधान एक ही साइट पर केवल 15% प्रतिक्रियाओं से तेज है।

और प्रोलोग कहां है

मुझे लगता है कि नियमित अभिव्यक्तियों के साथ काम करने के लिए यह भूल भाषा हमें पर्ल संगत संगत नियमित अभिव्यक्ति पर आधारित एक पुस्तकालय प्रदान करती है।

इसे इसी तरह से लागू किया जा सकता है, लेकिन एक अलग विधेय के साथ टेम्पलेट स्ट्रिंग को पूर्व-प्रक्रिया करें।

 pat([],[]). pat(['*'|T],['.*'|Tpat]):-pat(T,Tpat),!. pat(['?'|T],['.'|Tpat]):-pat(T,Tpat),!. pat([Ch|T],[Ch|Tpat]):-pat(T,Tpat). isMatch(S,P):- atom_chars(P,Pstr),pat(Pstr,PatStr),!, atomics_to_string(PatStr,Pat), term_string(S,Str), re_matchsub(Pat, Str, re_match{0:Str},[bol(true),anchored(true)]). 

और रनटाइम ठीक है:

 isMatch(aa,a)->ok:0.08794403076171875/sec isMatch(aa,*)->ok:0.0/sec isMatch(cb,?a)->ok:0.0/sec isMatch(adceb,*a*b)->ok:0.0/sec isMatch(acdcb,a*c?b)->ok:0.0/sec isMatch(aab,c*a*b)->ok:0.0/sec isMatch(mississippi,m??*ss*?i*pi)->ok:0.0/sec isMatch(abefcdgiescdfimde,ab*cd?i*de)->ok:0.0/sec isMatch(zacabz,*a?b*)->ok:0.0/sec isMatch(leetcode,*e*t?d*)->ok:0.0009980201721191406/sec isMatch(aaaa,***a)->ok:0.0/sec isMatch(b,*?*?*)->ok:0.0/sec isMatch(aaabababaaabaababbbaaaabbbbbbabbbbabbbabbaabbababab,*ab***ba**b*b*aaab*b)->ok:0.26383304595947266/sec isMatch(abbbbbbbaabbabaabaa,*****a*ab)->ok:0.0009961128234863281/sec isMatch(babaaababaabababbbbbbaabaabbabababbaababbaaabbbaaab,***bba**a*bbba**aab**b)->ok:0.20287489891052246/sec 

लेकिन, कुछ सीमाएँ हैं, अगला परीक्षण लाया गया:

 Not enough resources: match_limit Goal (directive) failed: user:assert_are_equal(isMatch(aaaabaaaabbbbaabbbaabbaababbabbaaaababaaabbbbbbaabbbabababbaaabaabaaaaaabbaabbbbaababbababaabbbaababbbba,'*****b*aba***babaa*bbaba***a*aaba*b*aa**a*b**ba***a*a*'),false) 

निष्कर्ष के रूप में

केवल प्रश्न रह गए। सब कुछ लागू किया जा सकता है, लेकिन गति लंगड़ा है।
पारदर्शी समाधान प्रभावी नहीं हैं?

किसी ने घोषणात्मक नियमित अभिव्यक्ति को लागू किया, किस तरह के तंत्र हैं?

और आप इन चुनौतियों को कैसे पसंद करते हैं, क्या कोई समस्या है जिसे हल किया जा सकता है, लेकिन सही समाधान कहां है?