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] வலமிருந்து இடமாக (அல்லது கீழிருந்து மேலே) வாசிப்புஃ அசல் பட்டியல் @unsorted ஒரு வரைபட செயல்பாட்டில் செலுத்தப்படுகிறது, இது ஒவ்வொரு உருப்படியையும் ஒரு (அநாமதேய 2-உறுப்பு பற்றிய குறிப்பு) வரிசையாக மூடுகிறது மற்றும் கணக்கிடப்பட்ட மதிப்பு அதன் வரிசை வரிசையை தீர்மானிக்கும் (உருப்படியின் பட்டியல் [உருப்படி, மதிப்பு] பட்டியலாக மாறும்); பின்னர் வரைபடத்தால் தயாரிக்கப்பட்ட பட்டியல்களின் பட்டியல் வரிசைப்படுத்தப்படுகிறது, இது முன்பு கணக்கிடப்பட்ட மதிப்புகளின்படி வரிசைப்படுத்தப்படுகிறது ([உருப்படி, மதிப்பு] இன் பட்டியல் வரிசைப்படுத்தப்பட்ட பட்டியல்); இறுதியாக, மற்றொரு வரைபட செயல்பாடு வரிசைப்படுத்துவதற்குப் பயன்படுத்தப்படும் மதிப்புகளை (அநாமதேய வரிசையிலிருந்து) அவிழ்த்து, வரிசைப்படுத்தப்பட்ட வரிசையில் அசல் பட்டியலின் உருப்படிகளை உருவாக்குகிறது (உருப்படி, மதிப்பு வரிசைப்படுத்தப்பட்ட பட்டியல்) அநாமதேய வரிசைகளின் பயன்பாடு வரிசைப்படுத்தப்பட்ட உடனேயே பெர்ல் குப்பை சேகரிப்பாளரால் நினைவகம் மீட்டெடுக்கப்படுவதை உறுதி செய்கிறது. ஷ்வார்ட்சியன் உருமாற்றம் இல்லாமல், மேலே உள்ள எடுத்துக்காட்டில் உள்ள வரிசைப்படுத்தல் பெர்ல் மொழியில் இவ்வாறு எழுதப்படும்ஃ @sorted = வரிசைப்படுத்தல் {ஃபூ ($a) சிஎம்பி ஃபூ ($b)} @unsorted; இது குறியீட்டிற்கு குறுகியதாக இருந்தாலும், முக்கிய செயல்பாடு (மேலே உள்ள எடுத்துக்காட்டில் அழைக்கப்படுகிறது) கணக்கிடுவதற்கு விலை உயர்ந்ததாக இருந்தால், இங்கே அப்பாவித்தனமான அணுகுமுறை மிகவும் குறைவான செயல்திறன் கொண்டதாக இருக்கும். ஏனென்றால், ஒவ்வொரு முறையும் இரண்டு கூறுகளை ஒப்பிட வேண்டியிருக்கும் போது அடைப்புக்குறிக்குள் உள்ள குறியீடு மதிப்பீடு செய்யப்படுகிறது. ஒரு உகந்த ஒப்பீட்டு வரிசை O (n log n) ஒப்பீடுகளைச் செய்கிறது (இங்கு n என்பது பட்டியலின் நீளம்), ஒவ்வொரு ஒப்பீட்டிற்கும் 2 அழைப்புகளுடன், இதன் விளைவாக O (n log n) அழைப்புகள். ஒப்பிடுகையில், ஷ்வார்ட்சியன் உருமாற்றத்தைப் பயன்படுத்தி, ஒரு உறுப்புக்கு 1 அழைப்பு மட்டுமே செய்கிறோம், தொடக்க கட்டத்தில், மொத்தம் n அழைப்புகளுக்கு. இருப்பினும், செயல்பாடு ஒப்பீட்டளவில் எளிமையாக இருந்தால், ஸ்வார்ட்சியன் உருமாற்றத்தின் கூடுதல் மேல்நிலை தேவையற்றதாக இருக்கலாம். எடுத்துக்காட்டாக, கோப்புகளின் பட்டியலை அவற்றின் மாற்றியமைக்கப்பட்ட நேரங்களின்படி வரிசைப்படுத்த, ஒரு அப்பாவித்தனமான அணுகுமுறை பின்வருமாறு இருக்கலாம்ஃ செயல்பாடு நைவே ஒப்பீடு (கோப்பு a, கோப்பு b) {திரும்பும் மாற்ற நேரம் (a) <மாற்ற நேரம் (b)}// அந்த வரிசைப்படுத்தலை (பட்டியல், ஒப்பீடு முன்கணிப்பு) இரண்டு கூறுகளை ஒப்பிடுவதற்கு ஒப்பீடு முன்கணிப்பைப் பயன்படுத்தி கொடுக்கப்பட்ட பட்டியலை வரிசைப்படுத்துகிறது என்று வைத்துக்கொள்வோம். வரிசைப்படுத்தப்பட்ட வரிசைஃ = வரிசைப்படுத்துதல் (கோப்புகள் வரிசை, அப்பாவித்தனமான ஒப்பீடு) ஒவ்வொரு கோப்புக்கும் மாற்றியமைக்கும் நேரங்கள் இல்லையென்றால், ஒவ்வொரு முறையும் ஒரு கோப்பு வரிசைப்படுத்தலில் ஒப்பிடும்போது அவற்றை மீண்டும் கணக்கிட வேண்டும். ஷ்வார்ட்சியன் உருமாற்றத்தைப் பயன்படுத்தி, மாற்றும் நேரம் ஒரு கோப்புக்கு ஒரு முறை மட்டுமே கணக்கிடப்படுகிறது. ஒரு ஸ்வார்ட்சியன் உருமாற்றம் மேலே விவரிக்கப்பட்ட செயல்பாட்டு முட்டாள்தனத்தை உள்ளடக்கியது, இது தற்காலிக வரிசைகளைப் பயன்படுத்தாது. அதே வழிமுறை அது எவ்வாறு செயல்படுகிறது என்பதை நன்கு விளக்குவதற்கு நடைமுறை ரீதியாக எழுதப்படலாம், ஆனால் இதற்கு தற்காலிக வரிசைகளைப் பயன்படுத்த வேண்டும், மேலும் இது ஒரு ஸ்வார்ட்சியன் உருமாற்றம் அல்ல. பின்வரும் உதாரணம் போலி-குறியீடு வழிமுறையை இந்த வழியில் செயல்படுத்துகிறதுஃ கோப்புகளில் உள்ள ஒவ்வொரு கோப்புக்கும், மாற்றப்பட்ட அரே செயல்பாட்டின் முடிவில் அரே செருகும் வரிசை (கோப்பு, மாற்றியமைக்கும் நேரம் (கோப்பு)) எளிமை ஒப்பிடுக (வரிசை a, வரிசை b) {திரும்பும் a [2] <b [2]} மாற்றப்பட்ட அரேஃ = வரிசைப்படுத்தப்பட்டது (மாற்றப்பட்ட அரே, எளிமையாக ஒப்பிடுக) வரிசைப்படுத்தப்பட்ட அரே வரலாற்றின் முடிவில் மாற்றப்பட்ட அரே செருகும் கோப்பில் உள்ள ஒவ்வொரு கோப்புக்கும் [1] ஷ்வார்ட்சியன் உருமாற்றத்தின் முதல் அறியப்பட்ட ஆன்லைன் தோற்றம் டிசம்பர் 16,1994 அன்று ராண்டல் ஸ்வார்ட்ஸால் comp.unix.shell யூஸ்நெட் செய்திக் குழுவில் ஒரு நூலுக்கு இடுகையிடப்பட்டது, இது comp.lang.perl க்கு குறுக்கு இடுகையிடப்பட்டது. (பெர்ல் காலவரிசையின் தற்போதைய பதிப்பு தவறானது மற்றும் 1995 ஆம் ஆண்டின் பிந்தைய தேதியைக் குறிக்கிறது.) வரிகளின் பட்டியலை அவற்றின் "கடைசி" வார்த்தையால் எவ்வாறு வரிசைப்படுத்துவது என்ற கேள்வியுடன் நூல் தொடங்கியதுஃ அட்ஜ்ன்ஃ ஜோஷுவா என்ஜி அட்க்டக்ஃ காலாப் திமோதி க்வாங் அட்ஜ்ஃ மஹாலிங்கம் கோபியரமானன் அட்ஜ்ஃ மார்த்தா எல். நங்கலாம ஷ்வார்ட்ஸ் பதிலளித்தார்ஃ #!/யுஎஸ்ஆர்/பின்/பெர்லுக்கு 5 தேவை; #புதிய அம்சங்கள், புதிய பிழைகள்! அச்சு வரைபடம் {$_-> [0]} வரிசைப்படுத்தப்பட்டது {$a-> [1] cmp $b-> [1] வரைபடம் {[$_,/(\S +) $/]} <>; இந்த குறியீடு பின்வரும் முடிவை உருவாக்குகிறதுஃ நிர்வாகம்ஃ மஹாலிங்கம் கோபிரமானன் adktk: காலாப் திமோதி க்வாங் நிர்வாகம்ஃ மார்த்தா எல். நங்கலாமாவின் நிர்வாகம்ஃ ஜோஷுவா என்ஜி ஸ்வார்ட்ஸ் இடுகையில் அவர் "பெர்லில் ஒரு லிஸ்புடன் பேசுகிறார்" என்று குறிப்பிட்டார், இது முட்டாள்தனத்தின் லிஸ்ப் தோற்றத்தைக் குறிக்கிறது. "ஸ்வார்ட்சியன் உருமாற்றம்" என்ற சொல் டாம் கிறிஸ்டியன்சனால் ஒரு பின்தொடர்தல் பதிலில் உருவாக்கப்பட்டது. கிறிஸ்டியன்செனின் பிற்கால பதிவுகள் அவர் கட்டுமானத்திற்கு பெயரிட விரும்பவில்லை என்பதை தெளிவுபடுத்தியது, ஆனால் அதை அசல் இடுகையிலிருந்து குறிப்பிட மட்டுமேஃ இறுதியாக அதற்கு "தி பிளாக் டிரான்ஸ்ஃபார்ம்" என்று பெயரிட அவர் மேற்கொண்ட முயற்சி பிடிக்கவில்லை ("பிளாக்" இங்கே "ஷ்வார் [டி] இசட்" என்பதற்கான ஒரு தண்டனையாக உள்ளது, அதாவது ஜெர்மன் மொழியில் கருப்பு என்று பொருள்படும்). பிற மொழிகளுடனான ஒப்பீடு சில பிற மொழிகள் ஷ்வார்ட்சியன் உருமாற்றத்தைப் போலவே அதே உகப்பாக்கத்திற்கு ஒரு வசதியான இடைமுகத்தை வழங்குகின்றனஃ பைதான் 2.4 மற்றும் அதற்கு மேல், செயல்பாடு மற்றும் இன்-பிளேஸ் முறை இரண்டும் ஒரு அளவுருவை எடுத்துக்கொள்கின்றன, இது பயனருக்கு ஒரு "முக்கிய செயல்பாட்டை" வழங்க அனுமதிக்கிறது (மேலே உள்ள எடுத்துக்காட்டுகளைப் போல). பைதான் 3 மற்றும் அதற்கு மேல், முக்கிய செயல்பாட்டைப் பயன்படுத்துவதே தனிப்பயன் வரிசைப்படுத்தல் வரிசையைக் குறிப்பிடுவதற்கான ஒரே வழியாகும் (முன்பு ஆதரிக்கப்பட்ட அளவுரு பயனர் ஒரு "ஒப்பீட்டு செயல்பாட்டை" வழங்க அனுமதித்தது). பைதான் 2.4 க்கு முன்பு, டெவலப்பர்கள் லிஸ்ப்-தோற்றுவிக்கப்பட்ட அலங்கரிக்கப்பட்ட-வகைப்படுத்தப்படாத (டி. எஸ். யூ) முட்டாள்தனத்தைப் பயன்படுத்துவார்கள், பொதுவாக பொருட்களை ஒரு (வரிசைப்படுத்தப்பட்ட விசை, பொருள்) டப்பிளில் மடக்குவதன் மூலம். ரூபி 1.8.6 மற்றும் அதற்கு மேல், சுருக்க வகுப்பில் (s ஐ உள்ளடக்கியது) ஒரு முறை உள்ளது, இது "முக்கிய செயல்பாட்டை" (மேலே உள்ள எடுத்துக்காட்டுகளைப் போல) ஒரு குறியீடு தொகுதியாகக் குறிப்பிட அனுமதிக்கிறது. டி 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. மெமோயிஸ் பெர்ல் தொகுதி-விலையுயர்ந்த செயல்பாடுகளை அவற்றின் முடிவுகளை தற்காலிக சேமிப்பின் மூலம் விரைவுபடுத்துகிறது. படிமுறைகளை வரிசைப்படுத்துதல் எடுத்துக்காட்டு பெர்ல் குறியீடு கொண்ட கட்டுரைகள் எடுத்துக்காட்டு ராக்கெட் குறியீடு பெர்ல் கொண்ட கட்டுரைகள்