नियमित अभिव्यक्ति सादगी परीक्षण

मैंने नियमित अभिव्यक्तियों के साथ बहुत सारी समस्याएं देखीं, लेकिन पिछले शुक्रवार, क्रिस और सीन के लिए धन्यवाद , मैंने एक नियमित पाया जो मुझे जांचने की अनुमति देता है कि क्या एक पूर्णांक प्रमुख है। मूल लेखों ने अभाज्य संख्या निर्धारित करने के लिए निम्नलिखित नियमित अभिव्यक्ति का प्रस्ताव दिया:







/^1?$|^(11+?)\1+$/







इसे पूर्णांक पर ही लागू नहीं किया जाना चाहिए। इसके बजाय, आपको इकाइयों की एक स्ट्रिंग बनाने की आवश्यकता है, जहां इकाइयों की संख्या स्वयं संख्या से मेल खाती है और इस स्ट्रिंग के लिए एक नियमित अभिव्यक्ति लागू करती है। यदि कोई मिलान नहीं है, तो संख्या अभाज्य है। इस नियमित अभिव्यक्ति में बैकलिंक्स शामिल हैं और इसलिए यह डीएफए इंजन पर काम नहीं करेगा, जैसे कि PHP ereg * फ़ंक्शन। लेकिन यह preg_ * फ़ंक्शन के साथ बहुत अच्छा काम करता है, या कम से कम मैंने ऐसा सोचा (उस पर अधिक)।



तो यह कैसे काम करता है? यह एक वास्तविक पहेली जैसा दिखता है, लेकिन यह वास्तव में सरल है। चरित्र से पहले इसके भाग को अनदेखा करें, क्योंकि यह केवल यह पता लगाने के लिए है कि क्या स्ट्रिंग पूरी तरह से खाली है या एक इकाई से बना है।



उप-एक्सप्रेशन (11+?) 11, 111 आदि जैसे तारों से मेल खाता है ... "\ 1+" भाग पहले उप-संपीड़न के लिए खोज परिणामों के साथ मिलान के लिए स्ट्रिंग में और खोज करेगा। पहली बार एक मैच लाइन "11" पर होगा और फिर लाइन "11" की खोज फिर से और फिर लाइन के अंत में की जाएगी। यदि खोज सफल होती है, तो संख्या अभाज्य नहीं है। क्यों? क्योंकि यह साबित हो जाएगा कि स्ट्रिंग की लंबाई 2 से विभाजित है और, तदनुसार, संख्या स्वयं भी दो से विभाजित होती है। यदि एक मैच नहीं होता है, तो नियमित अभिव्यक्ति इंजन स्ट्रिंग "111" और इसके दोहराव की खोज करना शुरू कर देगा (इस प्रकार एराटोस्थनीज की छलनी का एहसास - लगभग प्रति)। यदि पहला उपसंचाई अवधि काफी लंबी हो जाती है (n / 2) और कोई मिलान अभी भी नहीं मिला है, तो संख्या अभाज्य होगी।



सीन ने हाल ही में Phergie पर आधारित IRC बॉट के लिए कोड निष्पादित करने के लिए एक प्लगइन लिखा था, जो उसी चैनल पर लटका हुआ है जिसमें हम संवाद करते हैं। प्लगइन ही ideone.com के लिए एक प्रॉक्सी है, लेकिन यह त्वरित कोड परीक्षणों के लिए उपयोगी है। हमने इस रेगेक्स पैटर्न के साथ प्रयोग किया और एक PHP फ़ंक्शन लिखा जो उत्तीर्ण पूर्णांक के बाद अभाज्य संख्या देता है। मुसीबतें तब शुरू हुईं जब शॉन ने 99999999 इस समारोह में पारित किया और यह 100000001 वापस आ गया। ऐसा लगता है कि एक त्रुटि हुई है, क्योंकि 100000001 एक अभाज्य संख्या नहीं है (= 17 * 5882353)। वोल्फ्राम अल्फा ने इसकी पुष्टि की है।



इसी तरह के कई परीक्षणों के बाद, हमें अधिक संख्याएँ मिलीं जो कि प्रमुख नहीं थीं, लेकिन हमारी छोटी परीक्षा में उत्तीर्ण हुईं। हमने सोचा कि समस्या कहां हो सकती है। PHP कोड बग के लिए बहुत सरल था, हमारे फ़ंक्शन से प्राप्त उत्तरों में से अधिकांश सही थे। ऐसा लगता है कि यह जानवर बल का उपयोग करने का समय है। मैंने जल्दी से अपने टेम्प्लेट में विषम संख्याओं के अनुक्रम का परीक्षण करने के लिए कोड लिखा और हमारे फ़ंक्शन की प्रतिक्रियाओं की जांच करना शुरू कर दिया ताकि इरेटोस्थनीज़ चलनी के साथ यह समझने के लिए कि परिणाम गलत कहां हो जाएं। पहले गलत तरीके से पाई गई संख्या 22201 थी। हमारे नियमित द्वारा एक चेक ने हमें बताया कि यह सरल होना चाहिए, लेकिन वास्तव में यह 149 का वर्ग है। इस सीमा के बाद, गलत तरीके से निर्धारित सरल लोगों की संख्या में वृद्धि हुई है।



अचानक यह मुझ पर हावी हो गया कि समस्या नियमित अभिव्यक्तियों में बैकलिंक्स के तंत्र में छिपी हो सकती है। विशेष रूप से, पीसीआरई में इसे लागू करने के तरीके में, पीएचपी में नियमित अभिव्यक्तियों का दिल। जैसा कि मैंने रेगेक्स क्लिनिक पर एक पोस्ट में उल्लेख किया है, बैकलिंक्स के असीमित उपयोग से नियमित अभिव्यक्ति द्वारा पाठ प्रसंस्करण की गति में उल्लेखनीय कमी आती है, और इसलिए, जटिल नियमित अभिव्यक्तियों को लिखने के लिए उपयोग करने से पहले आपको सावधानी से सोचना चाहिए। इस तंत्र के दुरुपयोग के खतरे को खत्म करने के लिए, कई साल पहले पीसीआर में एक प्रतिबंधक पैरामीटर pcre.backtrack_limit लागू किया गया था। हमारे मामले में, बैकलिंक्स का उपयोग बड़ी संख्या में इकाइयों से पाठ को तोड़ने के लिए किया गया था और बहुत बड़ी लाइनों के साथ यह स्थापित सीमा को पार कर सकता है, जो कि डिफ़ॉल्ट रूप से 100000 है। मैंने सोचा था कि 22201 वर्णों की एक पंक्ति के साथ यह सीमा पर्याप्त नहीं थी। एक बार सीमा समाप्त हो जाने के बाद, मैच विफल हो गया और संख्या को सरल घोषित कर दिया गया।



मैंने सीमा को बढ़ाकर 200,000 कर दिया, और ध्वनि! .. 22201 को अब सरल रूप में परिभाषित नहीं किया गया था। संयोग संख्या 100000001 के साथ नियमित अभिव्यक्ति के काम को ठीक करने के लिए, सीमा को गंभीरता से 250,000,000 तक उठाना पड़ा! मेरे नए i5 मैकबुक प्रो पर नियमित अभिव्यक्ति रन में लगभग 14 सेकंड लगे।



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