Schwartzian transform
कंप्यूटर प्रोग्रामिंग में, श्वार्टज़ियन परिवर्तन एक तकनीक है जिसका उपयोग वस्तुओं की सूची को क्रमबद्ध करने की दक्षता में सुधार करने के लिए किया जाता है। यह मुहावरा तुलना-आधारित छँटाई के लिए उपयुक्त है जब क्रम वास्तव में तत्वों के एक निश्चित गुण (कुंजी) के क्रम पर आधारित होता है, जहां उस गुण की गणना एक गहन संचालन है जिसे कम से कम बार किया जाना चाहिए। श्वार्टज़ियन परिवर्तन उल्लेखनीय है कि यह नामित अस्थायी सरणियों का उपयोग नहीं करता है। श्वार्टज़ियन परिवर्तन एक लिस्प मुहावरे का एक संस्करण है जिसे डेकोरेट-सॉर्ट-अनडेकरेट के रूप में जाना जाता है, जो सॉर्ट कुंजी को अस्थायी रूप से इनपुट वस्तुओं के साथ जोड़कर पुनः गणना करने से बचाता है। यह दृष्टिकोण समान है, जो एक विशिष्ट इनपुट मूल्य के अनुरूप कुंजी की गणना को दोहराने से बचाता है। तुलनात्मक रूप से, यह मुहावरा आश्वस्त करता है कि प्रत्येक इनपुट वस्तु की कुंजी की गणना ठीक एक बार की जाती है, जिसके परिणामस्वरूप अभी भी कुछ गणनाएँ दोहराई जा सकती हैं यदि इनपुट डेटा में डुप्लिकेट आइटम हैं। इस मुहावरे का नाम रैंडल एल. श्वार्ट्ज के नाम पर रखा गया है, जिन्होंने 1994 में पर्ल 5 के रिलीज होने के तुरंत बाद इसे पहली बार पर्ल में प्रदर्शित किया था। "श्वार्टज़ियन परिवर्तन" शब्द कई वर्षों तक पूरी तरह से पर्ल प्रोग्रामिंग पर लागू हुआ, लेकिन बाद में इसे अन्य भाषाओं के कुछ उपयोगकर्ताओं द्वारा अपनाया गया, जैसे कि पायथन, उन भाषाओं में समान मुहावरों को संदर्भित करने के लिए। हालाँकि, एल्गोरिथ्म पहले से ही अन्य भाषाओं में उपयोग में था (किसी विशिष्ट नाम के तहत नहीं) इससे पहले कि इसे श्वार्ट्ज द्वारा उस विशेष मुहावरे के रूप में पर्ल समुदाय के बीच लोकप्रिय बनाया गया था। "श्वार्टज़ियन परिवर्तन" शब्द एक विशिष्ट मुहावरे को इंगित करता है, न कि सामान्य रूप से एल्गोरिथ्म को। उदाहरण के लिए, शब्द की लंबाई के अनुसार शब्द सूची ("एएए", "ए", "एए") को क्रमबद्ध करने के लिएः पहले सूची (["एएए", 4], ["ए", 1], ["एए", 2]) का निर्माण करें, फिर इसे संख्यात्मक मानों (["ए", 1], ["एए", 2], ["एएएए", 4]) के अनुसार क्रमबद्ध करें, फिर संख्याओं को हटा दें और आपको ("ए", "एएए", "एएएएए") मिलेगा। यह सामान्य रूप से एल्गोरिथ्म था, इसलिए इसे परिवर्तन के रूप में नहीं गिना जाता है। इसे एक सच्चा श्वार्टज़ियन परिवर्तन बनाने के लिए, इसे पर्ल में इस तरह किया जाएगाः @sorted = मानचित्र {$_-> [0]} क्रमबद्ध {$a-> [1] <= $b-> [1] या $a-> [0] cmp $b-> [0]} #संख्यात्मक तुलना का उपयोग करें, मूल मानचित्र पर स्ट्रिंग सॉर्ट पर वापस आएं {[$_, लंबाई ($_)]} #स्ट्रिंग की लंबाई की गणना करें @unsorted; पर्ल मुहावरा श्वार्टज़ियन परिवर्तन का सामान्य रूप हैः @sorted = मानचित्र {$_-> [0]] क्रमबद्ध {$a-> [1] cmp दाएँ से बाएँ (या नीचे से ऊपर) पढ़ने के लिएः मूल सूची @unsorted को एक मानचित्र संचालन में डाला जाता है जो प्रत्येक वस्तु को एक (एक अनाम 2-तत्व के संदर्भ में) सरणी में लपेटता है जिसमें स्वयं और गणना किए गए मूल्य शामिल होते हैं जो इसके क्रमबद्ध क्रम को निर्धारित करेंगे (वस्तु की सूची [वस्तु, मूल्य] की सूची बन जाती है); फिर मानचित्र द्वारा उत्पादित सूचियों की सूची को क्रमबद्ध किया जाता है, जो इसे पहले गणना किए गए मूल्यों के अनुसार क्रमबद्ध करता है (वस्तु, मूल्य की सूची); अंत में, एक और मानचित्र संचालन छँटाई के लिए उपयोग किए गए मूल्यों (अनाम सरणी से) को खोलता है, मूल सूची की वस्तुओं को क्रमबद्ध क्रम (वस्तु, मूल्य की क्रमबद्ध सूची) में उत्पन्न करता है। अनाम सरणी का उपयोग यह सुनिश्चित करता है कि छँटाई के तुरंत बाद पर्ल कचरा संग्राहक द्वारा स्मृति को पुनः प्राप्त किया जाएगा। दक्षता विश्लेषण श्वार्टज़ियन परिवर्तन के बिना, उपरोक्त उदाहरण में छँटाई को पर्ल में इस तरह लिखा जाएगाः @sorted = सॉर्ट {फू ($ए) सी. एम. पी. फू ($बी)} @unsorted; जबकि यह कोड से छोटा है, यहाँ सरल दृष्टिकोण बहुत कम कुशल हो सकता है यदि प्रमुख कार्य (जिसे उपरोक्त उदाहरण में कहा गया है) की गणना करना महंगा है। ऐसा इसलिए है क्योंकि ब्रैकेट के अंदर के कोड का मूल्यांकन हर बार दो तत्वों की तुलना करने की आवश्यकता होती है। एक इष्टतम तुलना सॉर्ट ओ (एन लॉग एन) तुलना करता है (जहां एन सूची की लंबाई है), प्रत्येक तुलना के लिए 2 कॉल के साथ, जिसके परिणामस्वरूप ओ (एन लॉग एन) कॉल होता है। इसकी तुलना में, श्वार्टज़ियन परिवर्तन का उपयोग करते हुए, हम केवल 1 कॉल प्रति तत्व करते हैं, शुरुआती चरण में, कुल n कॉल के लिए। हालाँकि, यदि कार्य अपेक्षाकृत सरल है, तो श्वार्टज़ियन परिवर्तन का अतिरिक्त उपरिभाग अनुचित हो सकता है। उदाहरण के लिए, फ़ाइलों की सूची को उनके संशोधन समय के अनुसार क्रमबद्ध करने के लिए, एक सरल दृष्टिकोण इस प्रकार हो सकता हैः फ़ंक्शन नैवेकंपेयर (फ़ाइल ए, फ़ाइल बी) {रिटर्न मॉडिफिकेशनटाइम (ए) <मॉडिफिकेशनटाइम (बी)}// मान लीजिए कि सॉर्ट (सूची, तुलना भविष्यवाणी) दो तत्वों की तुलना करने के लिए दी गई सूची को// तुलना भविष्यवाणी का उपयोग करके क्रमबद्ध करता है। सॉर्टडएरेः = सॉर्ट (फाइलसएरे, नाइवकम्पेयर) जब तक कि प्रत्येक फाइल के लिए संशोधन का समय न हो, इस विधि के लिए हर बार जब किसी फ़ाइल की तुलना सॉर्ट में की जाती है तो उन्हें फिर से गणना करने की आवश्यकता होती है। श्वार्टज़ियन रूपांतरण का उपयोग करते हुए, संशोधन समय की गणना प्रति फ़ाइल केवल एक बार की जाती है। एक श्वार्टज़ियन परिवर्तन में ऊपर वर्णित कार्यात्मक मुहावरा शामिल होता है, जो अस्थायी सरणियों का उपयोग नहीं करता है। एक ही एल्गोरिथ्म को बेहतर ढंग से स्पष्ट करने के लिए प्रक्रियात्मक रूप से लिखा जा सकता है कि यह कैसे काम करता है, लेकिन इसके लिए अस्थायी सरणियों का उपयोग करने की आवश्यकता होती है, और यह श्वार्टज़ियन परिवर्तन नहीं है। निम्नलिखित उदाहरण छद्म-कोड एल्गोरिथ्म को इस तरह से लागू करता हैः फ़ाइलों में प्रत्येक फ़ाइल के लिए परिवर्तित एरे फ़ंक्शन के अंत में एरे सम्मिलित करें सरणी (फ़ाइल, संशोधन समय (फ़ाइल)) सरल तुलना करें (सरणी a, सरणी b) {वापसी a [2] <b [2]} परिवर्तित एरेः = सॉर्ट (परिवर्तित एरे, सरल तुलना) सॉर्ट किए गए एरे इतिहास के अंत में परिवर्तित एरे सम्मिलित फ़ाइल [1] में प्रत्येक फ़ाइल के लिए श्वार्टज़ियन परिवर्तन की पहली ज्ञात ऑनलाइन उपस्थिति 16 दिसंबर, 1994 को रैंडल श्वार्टज़ द्वारा comp.unix.shell यूज़नेट समाचार समूह में एक धागे पर पोस्ट की गई थी, जिसे comp.lang.perl पर क्रॉसपोस्ट किया गया था। (पर्ल टाइमलाइन का वर्तमान संस्करण गलत है और 1995 में बाद की तारीख को संदर्भित करता है।) थ्रेड की शुरुआत इस सवाल के साथ हुई कि पंक्तियों की सूची को उनके "अंतिम" शब्द से कैसे क्रमबद्ध किया जाएः एडजनः जोशुआ एनजी एडक्टकः कालाप टिमोथी क्वोंग एडमिनः महालिंगम गोबिरामनन एडमिनः मार्था एल. नंगलाम श्वार्ट्ज ने जवाब दियाः #!/युसर/बिन/पर्ल को 5 की आवश्यकता है; #नई सुविधाएँ, नए बग! प्रिंट मैप {$_-> [0]} सॉर्ट {$a-> [1] cmp $b-> [1]} मैप {[$_,/(\S +) $/]} <>; यह कोड परिणाम देता हैः एडमग्ः महालिंगम गोबिरामानन एडक्टकः कालाप टिमोथी क्वोंग एडमल्नः मार्था एल. नांगलामा एडमिल्नः जोशुआ एनजी श्वार्ट्ज ने पोस्ट में उल्लेख किया कि वह "पर्ल में एक लिस्प के साथ बोल रहे थे", जो मुहावरे की लिस्प उत्पत्ति का एक संदर्भ था। "श्वार्टज़ियन परिवर्तन" शब्द स्वयं टॉम क्रिस्टियनसन द्वारा एक अनुवर्ती उत्तर में गढ़ा गया था। क्रिस्टियनसेन के बाद के पोस्टों ने यह स्पष्ट कर दिया कि उनका निर्माण का नाम रखने का इरादा नहीं था, बल्कि केवल मूल पोस्ट से इसका उल्लेख करने का इरादा थाः अंत में इसे "द ब्लैक ट्रांसफॉर्म" नाम देने का उनका प्रयास सफल नहीं हुआ ("ब्लैक" यहाँ "श्वार [टी] जेड" पर एक श्लेष है, जिसका जर्मन में अर्थ काला है)। अन्य भाषाओं के साथ तुलना कुछ अन्य भाषाएँ श्वार्टज़ियन परिवर्तन के समान अनुकूलन के लिए एक सुविधाजनक इंटरफेस प्रदान करती हैंः पायथन 2.4 और उससे ऊपर, फ़ंक्शन और इन-प्लेस विधि दोनों एक पैरामीटर लेते हैं जो उपयोगकर्ता को "प्रमुख फ़ंक्शन" प्रदान करने की अनुमति देता है (जैसे उपरोक्त उदाहरणों में)। पायथन 3 और उसके ऊपर, की फ़ंक्शन का उपयोग एक कस्टम सॉर्ट ऑर्डर को निर्दिष्ट करने का एकमात्र तरीका है (पहले समर्थित पैरामीटर जो उपयोगकर्ता को "तुलना फ़ंक्शन" प्रदान करने की अनुमति देता था उसे हटा दिया गया था)। पायथन 2.4 से पहले, डेवलपर्स लिस्प-ओरिजिनेटेड डेकोरेट-सॉर्ट-अनडेकरेट (डीएसयू) मुहावरे का उपयोग करते थे, आमतौर पर वस्तुओं को एक (सॉर्टकी, ऑब्जेक्ट) टुपल में लपेटकर। रूबी 1.8.6 और उससे ऊपर, अमूर्त वर्ग (जिसमें एस शामिल हैं) में एक विधि होती है, जो कोड ब्लॉक के रूप में "प्रमुख कार्य" (जैसे उपरोक्त उदाहरणों में) को निर्दिष्ट करने की अनुमति देती है। डी 2 और उसके ऊपर, फ़ंक्शन उपलब्ध है। इसके लिए कम अस्थायी डेटा की आवश्यकता हो सकती है और यह पर्ल मुहावरे या पायथन और लिस्प में मौजूद डेकोरेट-सॉर्ट-अनडेकरेट मुहावरे की तुलना में तेज हो सकता है। ऐसा इसलिए है क्योंकि छँटाई जगह-जगह की जाती है, और केवल न्यूनतम अतिरिक्त डेटा (परिवर्तित तत्वों की एक सरणी) बनाई जाती है। रैकेट का कोर सॉर्ट फ़ंक्शन एक #: कुंजीशब्द तर्क को एक फ़ंक्शन के साथ स्वीकार करता है जो एक कुंजी निकालता है, और एक अतिरिक्त #: कैश-कुंजी? अनुरोध करता है कि परिणामी मानों को छँटाई के दौरान कैश किया जाता है। उदाहरण के लिए, सूची को बदलने का एक सुविधाजनक तरीका है। पी. एच. पी. 5.3 और उससे ऊपर के परिवर्तन को उपयोग करके लागू किया जा सकता है, जैसे। PHP.function स्पेसबॉल _ सॉर्ट (ऐरे & $a) में अस्थिर सॉर्ट एल्गोरिदम की सीमाओं के आसपास काम करने के लिएः शून्य {ऐरे _ वॉक ($a, फ़ंक्शन (& $v, $k) {$v = ऐरे ($v, $k);}); ऐसोर्ट ($a); ऐरे _ वॉक ($a, फ़ंक्शन (& $v, $$) {$v = $v [0];} अमृत में, और विधियाँ उपयोगकर्ताओं को प्रोटोकॉल को लागू करने वाले किसी भी मॉड्यूल के लिए श्वार्टज़ियन परिवर्तन करने की अनुमति देती हैं। राकू में, एक तुलनित्र लैम्ब्डा की आपूर्ति करने की आवश्यकता होती है जो हुड के नीचे एक श्वार्टज़ियन परिवर्तन करने के लिए केवल 1 तर्क लेता हैः @a.sort ({$a.Str}) #या छोटाः @a.sort (*. Str) श्वार्टज़ियन परिवर्तन का उपयोग करके स्ट्रिंग प्रतिनिधित्व पर छँटाई करेगा, @a.sort ({$a.Str cmp $^ b.Str}) प्रत्येक तुलना से ठीक पहले तुलना करने के लिए तत्वों को परिवर्तित करने के लिए वही करेगा। रस्ट में, कुछ उलझन में, विधि एक श्वार्टज़ियन परिवर्तन नहीं करती है क्योंकि यह कुंजी के लिए अतिरिक्त भंडारण आवंटित नहीं करेगी, यह प्रत्येक तुलना के लिए प्रत्येक मूल्य के लिए प्रमुख कार्य को बुलाएगी। विधि प्रति तत्व एक बार कुंजी की गणना करेगी। रैंडल एल. श्वार्ट्ज मार्क-जेसन डोमिनस द्वारा श्वार्टज़ियन ट्रांसफॉर्म के साथ सॉर्टिंग श्वार्टज़ियन ट्रांसफॉर्म http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/52234 पायथन सॉफ्टवेयर फाउंडेशन (2005) की व्याख्या करता है। 1. 5. 2 मैं एक जटिल सॉर्ट करना चाहता हूँः क्या आप पायथन में श्वार्टज़ियन ट्रांसफॉर्म कर सकते हैं? 22 जून, 2005 को प्राप्त किया गया। मेमोइज़ पर्ल मॉड्यूल-महंगे कार्यों को उनके परिणामों को कैश करके तेजी से बनाना। एल्गोरिदम लेखों को क्रमबद्ध करना उदाहरण के साथ पर्ल कोड लेख उदाहरण के साथ रैकेट कोड पर्ल