لذا ، أيها المجتمع ، أطلب منك أن تعطيني فرصة لمفاجئك في المرة الثالثة ، في القرار السابق الذي استخدمته python ، اعتقدت أنني سألفت انتباه الخبراء هنا وسيخبرونني على الفور عن سبب القيام بذلك ، بشكل عام هناك تعابير منتظمة - فعلت ذلك وكل شيء مؤكد ستنجح ، هذا الثعبان يمكن أن يعطي وسرعة أكبر.

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

لقد كتبت تنفيذًا كان ، في المتوسط ​​، من هذا النوع من السرعة ، وهذا يعني أنه لا يزال هناك 90 بالمائة من الحلول التي لم ألاحظها أن شخصًا ما يعرف كيفية حلها بشكل أسرع وهو صامت ، وبعد النظر في المادتين السابقتين لم أقل: أوه ، إذا كان مشكلة الأداء ، ثم كل شيء واضح - هنا لا تناسب المقدمة. لكن الآن كل شيء طبيعي مع الأداء ، لا يمكن تخيل برنامج يعمل على أجهزة ضعيفة ، "في النهاية ، لماذا تفكر في ذلك؟"

التحدي

لحل المشكلة بشكل أسرع ، كان هناك ثعبان وكان هناك وقت ، وهل هناك حل أسرع في الثعبان؟

أبلغني "وقت التشغيل: 2504 مللي ثانية ، أسرع من 1.55٪ من عمليات إرسال Python3 عبر الإنترنت لمطابقة Wildcard."

أحذركم ، هناك المزيد من الأفكار عبر الإنترنت.

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 اختبارات وفشلت ، هنا فقط.

أكرر مرة أخرى ، على هذا الموقع أنهم يعملون بعناية في الاختبارات ، كما حدث ، كل شيء سابق جيد ، ولكن هنا يتم خلط معلمتين رئيسيتين وهذا ظهر ، إليك مزايا TDD ...

وعلى مثل هذا النص الرائع ، ما زلت أتلقى خطأ

 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 

يؤدي إلى هذا:

الاستئناف

أيها السكان الأعزاء ، حاولوا التحقق من ذلك ، وجعلت python ثلاثة ، لا يمكنه إكمال هذه المهمة بسرعة:

 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) "***** ب * ابا *** البعباع * bbaba *** و* AABA * ب * أأ ** أ ب * ** *** با ل* على *") 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) 

يمكنك تجربته في المنزل. المعجزات ، لا يستغرق حلها وقتًا طويلاً فحسب ، بل تجمد ، أوه.

هل التعبيرات العادية هي مجموعة فرعية من المظهر التعريفي عرجاء في الأداء؟
البيان غريب ، فهي موجودة بجميع اللغات العصرية ، لذلك يجب أن تكون الإنتاجية رائعة ، ولكن هنا ليس من الواقعي على الإطلاق أنه لا توجد آلة حالة محدودة فيها؟ ماذا يحدث هناك في دورة لا نهاية لها ؟؟

اذهب

لقد قرأت في كتاب واحد ، ولكن منذ وقت طويل ... أحدث لغة Go تعمل بسرعة كبيرة ، ولكن ماذا عن التعبير العادي؟

سأختبره:

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

أعترف ، أنه لم يكن من السهل الحصول على مثل هذا النص المختصر ، هناك بنية ليست تافهة ، حتى مع معرفة si ، ليس من السهل معرفة ذلك ...

هذه نتيجة رائعة ، فالسرعة تتدحرج بالفعل ، إجمالي 60 ~ مللي ثانية ، ولكن من المدهش أن هذا الحل أسرع من 15 ٪ فقط من الردود على نفس الموقع.

وأين مقدمة

أجد أن هذه اللغة المنسية للعمل مع التعبيرات العادية توفر لنا مكتبة تعتمد على التعبير العادي المتوافق مع Perl.

هذه هي الطريقة التي يمكن تنفيذها بها ، ولكن معالجة سلسلة القالب مسبقًا بمسند منفصل.

 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) 

خاتمة

بقيت الأسئلة فقط. يمكن تنفيذ كل شيء ، ولكن السرعة عرجاء.
الحلول الشفافة ليست فعالة؟

قام شخص ما بتطبيق التعابير العادية التوضيحية ، ما نوع الآليات الموجودة؟

وكيف تحب هذه التحديات ، هل هناك مشكلة يمكن حلها ، ولكن أين الحل الأمثل؟