पायथन में साधारण (या बिल्कुल सामान्य नहीं) लिप्यंतरण

एक बार पाइथन में लिप्यंतरण लिखने की आवश्यकता थी - सिरिलिक से लैटिन में। शब्द से "सिथ" को "सिथ" और "सरसराहट" से "आश्रय" मिलता है।

ऐसा लगता है, वहाँ क्या लिखने के लिए है - कार्य "हैलो दुनिया" प्रिंट की तुलना में शायद ही अधिक कठिन है। और यह आंशिक रूप से सच है - लेकिन काफी नहीं।

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

लेकिन, चूंकि हम निश्चित रूप से लिप्यंतरण के नियमों को बदलने नहीं जा रहे हैं, हम देखेंगे कि साधारण लिप्यंतरण का उपयोग करते समय क्या होता है।

उदाहरण के लिए, वाक्यांश "हाट और जूलिया" को "शेपका और यूलिया" या "श्पका और यूल्या" में बदल दिया जाता है - "श" और "यू" (कभी-कभी "एसएच") और लिप्यंतरण तालिका में निर्दिष्ट के आधार पर। "YU" और कभी-कभी "Sh" और "Yu")।

यही है, मानक लिप्यंतरण कार्यों में अगले पत्र के मामले पर ध्यान नहीं दिया जाता है, और ऊपरी मामले के सभी पत्रों को सामान्य नियमों के अनुसार बदल दिया जाता है। इसलिए, "BOWL" और "गोभी का सूप" शब्दों के लिए लिप्यंतरण के दौरान "चश" या "शि" जैसी कोई चीज़ प्राप्त करना आसान है, जब वास्तव में हमें "CHASHA" और "SCHI" मिलेगा।

फिर भी, सभी ने साइरिलिक से लैटिन में पायथन में लिप्यंतरण कार्यान्वयन पाया, जैसा कि यह निकला, इस सुविधा को ध्यान में नहीं रखा गया। ये मंचों पर उपलब्ध कराए गए कई समाधान हैं, और pytils पुस्तकालय जो इसके एक मॉड्यूल में लिप्यंतरण को लागू करता है।

इसलिए, हम अपने लिप्यंतरण फ़ंक्शन को लाठी और ^ W ^ W ^ W ^ H ^ H के साथ लिखते हैं। :)


तो, पहला विकल्प चरित्र द्वारा लाइन चरित्र के माध्यम से जाना है। इस मामले में, यह हमेशा ज्ञात होता है कि कौन सा चरित्र अगला है (यदि यह स्ट्रिंग में अंतिम वर्ण नहीं है)।

सिद्धांत यह है:

1. प्रत्येक वर्ण के लिए, यह जांचा जाता है कि क्या यह लोअर_केस_लेटर्स शब्दकोश की कुंजियों में से है।
2. यदि वहाँ है, तो इसे लोअर_केस_लेटर्स में दी गई कुंजी के मान से बदल दिया जाता है।
3. यदि नहीं, तो यह देखने के लिए जाँचता है कि क्या यह अक्षर Capital_letters डिक्शनरी में कुंजियों के बीच है।
4. यदि वहाँ है, तो यह जाँच की जाती है कि क्या यह स्ट्रिंग में अंतिम वर्ण है (यदि स्ट्रिंग वर्तमान वर्ण की स्थिति से अधिक है + 1 - तो यह अंतिम वर्ण नहीं है, बशर्ते कि स्थिति शून्य से गिना जाए)।
5. यदि चरित्र अंतिम नहीं है, तो यह जांचा जाता है कि क्या अगला वर्ण शब्दकोष_केस_लेटर्स की कुंजियों के बीच है।
6. यदि नहीं, या यदि यह स्ट्रिंग में अंतिम वर्ण है, तो कैपिटल_लेटर्स शब्दकोश में दिए गए कुंजी के लिए वर्तमान वर्ण को प्रतिस्थापित किया जाता है, और ऊपरी () विधि का उपयोग मूल्य के लिए किया जाता है - अर्थात, "SH" इस "Sh" से प्राप्त होता है, और इसी तरह।
7. यदि अगला वर्ण शब्दकोष_केस_लेटर्स की कुंजियों में से है, तो ऊपरी () विधि का उपयोग नहीं किया जाता है।

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

अधिक सटीकता के लिए, निष्पादन समय (यह दोनों और दूसरे ग्राफ पर) एक लिप्यंतरण ऑपरेशन के लिए नहीं, बल्कि 500 ​​के लिए इंगित किया जाता है। कंप्यूटर पर स्थापित प्रोसेसर Intel Core 2 Quad CPU Q9400 @ 2.66GHz है।



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

सामान्य तौर पर, यह कहा जाना चाहिए कि प्रतीक समूहों की जगह केवल एकमात्र समाधान नहीं है जो दिमाग में आया था। सबसे पहले, उदाहरण के लिए, विचार एक स्ट्रिंग को शब्दों में विभाजित करने के लिए उत्पन्न हुआ, फिर प्रत्येक शब्द के लिए, मामले की जांच करें (यदि शब्द जिसमें सभी वर्ण ऊपरी मामले में बदल दिए गए हैं, मूल शब्द के बराबर है, तो ऐसा शब्द ऊपरी मामले में है), और यदि शब्द में लिखा गया है अपरकेस, फिर एक अलग लिप्यंतरण तालिका लागू करें, विशेष रूप से अपरकेस में शब्दों के लिए। तदनुसार, इस मामले में "शतरंज" शब्द में "Sh" अक्षर "Sh" के रूप में अनुवादित किया जाएगा, लेकिन शब्द "CHESS" में पहले से ही "SH" के रूप में।

सच है, मिश्रित मामले में लिखे गए शब्दों में (उदाहरण के लिए, "CHESS"), किसी भी मामले में, सामान्य लिप्यंतरण तालिका का उपयोग किया जाएगा (अर्थात, यह ShAHmatY को बाहर कर देगा)। लेकिन यह सामान्य तौर पर इतना महत्वपूर्ण नहीं है।

या, एक विकल्प के रूप में, कोई इसे और भी अधिक सार्वभौमिक रूप से कर सकता है - निचले मामले में लिखे गए शब्दों के लिए प्रतिस्थापित करें, और बाकी के शब्दों को चरित्र द्वारा संसाधित करें। लेकिन यह शायद धीमा होगा, क्योंकि ऐसे कई शब्द होने की संभावना है।

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

लेकिन बस इस तरह का एक विकल्प बहुत धीमा हो गया (वास्तव में, कार्यान्वयन धीमी गति से निकला - लेकिन इसके नीचे और अधिक)।

अधिक सटीक रूप से, यह केवल पहले विकल्प की तुलना में बहुत बड़ी संख्या में पात्रों के साथ तेज है - लगभग 10 हजार।

और जब 100 से 1000 वर्णों तक प्रसंस्करण लाइनें होती हैं, तो पहला विकल्प लगभग 10 गुना तेज होता है।

खैर, 7 * 33 = 231. यही है, 231 अतिरिक्त प्रतिस्थापन। बेशक, शब्दकोश में हम इनमें से कई पत्र संयोजनों को पूरा नहीं करेंगे - अर्थात्, सैद्धांतिक रूप से, प्रतिस्थापन कार्यों की एक छोटी संख्या हो सकती है। लेकिन, दूसरी ओर, पाठ में केवल उन शब्दों को शामिल नहीं किया जा सकता है जो शब्दकोश में हैं, और वास्तव में मैं एक बार फिर से इस तरह के प्रतिबंध नहीं लगाना चाहता हूं।

वास्तव में, जैसा कि यह निकला, बिंदु यह नहीं है कि बड़ी संख्या में प्रतिस्थापन ऑपरेशन किए जाते हैं, लेकिन वास्तव में पात्रों के प्रतिस्थापन को कैसे लागू किया जाता है (चौथा विकल्प देखें)।

हालांकि, पहले तीसरे विकल्प पर विचार करें।

तीसरा विकल्प कुछ हद तक दूसरे के समान है, लेकिन लोअरकेस अक्षरों के प्रत्येक संभव संयोजन के लिए 231 अलग-अलग प्रतिस्थापन नहीं हैं, ज़ी, त्स, च, श, श, यू और जेड। इसके बजाय, यह एक नियमित अभिव्यक्ति का उपयोग करता है, जो केवल 7 प्रतिस्थापन के लिए लागू होता है। कई लैटिन अक्षरों से संबंधित अक्षरों में से प्रत्येक, जिसके बाद एक लोअरकेस वर्ण ([ए)) है, उस पत्र के लैटिन प्रतिनिधित्व द्वारा प्रतिस्थापित किया जाता है, उसके बाद उसी लोअरकेस वर्ण (लिप्यंतरण के बिना) के द्वारा। उसके बाद, क्रमशः, शेष निचले अक्षरों को अलग-अलग प्रतिस्थापित किया जाता है, हालांकि, अपरकेस हैं। कई लैटिन वर्णों के अनुरूप अपरकेस अक्षरों को प्रतिस्थापित करते समय, अक्षर के लैटिन प्रतिनिधित्व के लिए ऊपरी () विधि का उपयोग किया जाता है।

और यह विकल्प पहले से ही दूसरे की तुलना में बहुत तेज साबित हुआ।

100 वर्णों की तर्ज पर, इसे पहले विकल्प की तुलना में धीमा होना चाहिए। लेकिन 1000 वर्णों की एक पंक्ति में, यह पहले विकल्प के रूप में पहले से दोगुना तेज है, और दूसरे की तुलना में 19.5 गुना तेज है।

सिद्धांत रूप में, यह समाप्त हो सकता है, लेकिन वास्तव में कुछ और है जिसे जोड़ा जा सकता है और जोड़ा जाना चाहिए।

यदि हम इसे लिखते हैं, तो हमें प्रसिद्ध पाठ, ज़ेन ऑफ़ पायथन भाषा मिलती है। अन्य बातों के अलावा, एक वाक्यांश है कि "एक होना चाहिए - और, अधिमानतः, केवल एक - ऐसा करने का स्पष्ट तरीका।" हालांकि, जो कोई भी लंबे समय से पायथन प्रोग्राम करता है, वह जानता है कि ऐसे मामले हैं जब एक ही काम करने के लिए काफी कुछ तरीके हैं, और उनमें से किसी का उपयोग करते समय, परिणाम बिल्कुल समान हो सकता है, लेकिन ऑपरेशन पूरा करने में लगने वाला समय हो सकता है बहुत अलग।

इसलिए, उदाहरण के लिए, u "आपका नाम% s है"% उपयोगकर्ता नाम u की तुलना में बहुत तेज है "आपका नाम" + उपयोगकर्ता नाम है। यह "पायथन में कुशल स्ट्रिंग कॉनटेनटेशन" लेख में अच्छी तरह से और अच्छी तरह से लिखा गया है।

इसी तरह यहाँ - स्ट्रिंग को re.sub के माध्यम से बदला जा सकता है, या आप स्ट्रिंग विधि को प्रतिस्थापित करने का उपयोग कर सकते हैं। इसके अलावा, अगर किसी भी प्रतिस्थापन के लिए नियमित अभिव्यक्तियों का उपयोग नहीं किया जाता है, तो दूसरी विधि का उपयोग करने के लिए दृढ़ता से सिफारिश की जाती है, जो इसके अलावा, बहुत तेजी से काम करती है। वैसे, समान पाइलिल्स में स्ट्रिंग विधि को प्रतिस्थापित किया जाता है।

तो, चौथा विकल्प (संपादन के साथ दूसरा विकल्प)। केवल तीन पंक्तियों को संपादित किया गया है, लेकिन उत्पादकता में जबरदस्त वृद्धि हुई है।

यह विकल्प 1000 और 10000 वर्णों की पंक्तियों के साथ बाकी की तुलना में बेहतर है। 100 वर्णों की तर्ज पर, (दूसरा विकल्प) की तुलना में अंतर भी बहुत बड़ा है।

लेकिन तीसरे विकल्प के संपादन के बारे में क्या? आखिरकार, तीन चक्रों में जहां पात्रों को प्रतिस्थापित किया जाता है, केवल एक में नियमित अभिव्यक्ति का उपयोग किया जाता है। अच्छा, ठीक है, तीसरे विकल्प को भी संपादित करते हैं।

पांचवा विकल्प केवल तीसरे में दो चक्रों में भिन्न होता है जहां प्रतिस्थापन के लिए नियमित अभिव्यक्ति का उपयोग नहीं किया जाता है, प्रतिस्थापन ऑपरेशन को प्रतिस्थापित स्ट्रिंग विधि का उपयोग करके किया जाता है।

एक शक के बिना, यह प्रदर्शन को बहुत प्रभावित करना चाहिए था: पांचवें विकल्प की गति तीसरे की तुलना में औसतन 1.5 गुना अधिक थी। और यह पता चला कि 100 वर्णों की एक पंक्ति में, पाँचवाँ विकल्प पहले की तुलना में और भी तेज़ी से काम करता है (जो कि चरित्र-दर-वर्ण प्रसंस्करण से तेज़ है)।



यह पता चलता है कि प्रतिस्थापन एल्गोरिदम 100, 1000 और 10000 वर्णों के तार के लिए चरित्र-दर-वर्ण प्रसंस्करण से अधिक तेज़ निकला।

और फिर भी, प्रत्येक विकल्प के अपने फायदे और नुकसान हैं। उदाहरण के लिए, भले ही पांचवें अवतार में, 100 वर्णों की एक स्ट्रिंग को एक लाइन के चरित्र-दर-वर्ण आघात का उपयोग करने की तुलना में तेजी से संसाधित किया जाता है, बहुत छोटी रेखाओं पर (कुछ वर्ण - और ऐसा होता है) चरित्र-दर-वर्ण प्रसंस्करण अभी भी सबसे तेज़ विकल्प होगा।

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

अंत में, मैं फ्रीस्टैड-करंट मेलिंग सूची पर अपने संदेश से माइक हर्टेल (माइक हैर्टल - जीएनयू ग्रीप के लेखक) को उद्धृत करना चाहता हूं कि जीएनयू ग्रीप इतनी तेज क्यों है:

कार्यक्रमों को तेजी से बनाने की कुंजी उन्हें व्यावहारिक रूप से कुछ भी नहीं करना है। ;-)

"तेजी से कार्यक्रम बनाने की कुंजी उन्हें लगभग कुछ भी नहीं करने के लिए प्राप्त करना है।"

यदि कोई अन्य विचार हैं - जोड़ने के लिए स्वतंत्र महसूस करें, पूरक। यदि कोई अन्य सुधार हैं, तो मुझे लगता है कि कई लोगों के लिए यह दिलचस्प हो सकता है।