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 = સૉર્ટ {ફૂ ($એ) સીએમપી ફૂ ($બી)} @unsorted; જ્યારે તે કોડથી ટૂંકો હોય છે, ત્યારે અહીં નિષ્કપટ અભિગમ ઘણો ઓછો કાર્યક્ષમ હોઈ શકે છે જો કી ફંક્શન (ઉપરના ઉદાહરણમાં કહેવાય છે) ની ગણતરી કરવી ખર્ચાળ હોય. આનું કારણ એ છે કે જ્યારે પણ બે તત્વોની સરખામણી કરવાની જરૂર પડે ત્યારે કૌંસની અંદરના કોડનું મૂલ્યાંકન કરવામાં આવે છે. એક શ્રેષ્ઠ સરખામણી સૉર્ટ દરેક સરખામણી માટે 2 કોલ સાથે ઓ (એન લોગ એન) સરખામણી કરે છે (જ્યાં એન એ સૂચિની લંબાઈ છે), પરિણામે ઓ (એન લોગ એન) કૉલ કરે છે. તેની સરખામણીમાં, શ્વાર્ટઝિયન ટ્રાન્સફોર્મનો ઉપયોગ કરીને, આપણે શરૂઆતના તબક્કે, કુલ n કોલ માટે, ઘટક દીઠ માત્ર 1 કોલ કરીએ છીએ. જો કે, જો કાર્ય પ્રમાણમાં સરળ હોય, તો શ્વાર્ટઝિયન ટ્રાન્સફોર્મનું વધારાનું ઓવરહેડ અયોગ્ય હોઈ શકે છે. ઉદાહરણ તરીકે, ફાઇલોની સૂચિને તેમના ફેરફારના સમય અનુસાર સૉર્ટ કરવા માટે, નિષ્કપટ અભિગમ નીચે મુજબ હોઈ શકે છેઃ ફંક્શન નાઇવકોમ્પેર (ફાઇલ 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 +) $/]} <>; આ કોડ પરિણામ ઉત્પન્ન કરે છેઃ એડમગ્ઃ મહાલિંગમ ગોબીરામાનન એડક્ટકઃ કાલાપ ટિમોથી ક્વોંગ એડમલ્નઃ માર્થા એલ. નાંગલામા એડમિલ્નઃ જોશુઆ એનજી શ્વાર્ટઝે પોસ્ટમાં નોંધ્યું હતું કે તેઓ "પર્લમાં લિસ્પ સાથે બોલો", જે રૂઢિપ્રયોગની લિસ્પ ઉત્પત્તિનો સંદર્ભ છે. "શ્વાર્ટઝિયન ટ્રાન્સફોર્મ" શબ્દ પોતે ટોમ ક્રિશ્ચિયનસેન દ્વારા ફોલો-અપ જવાબમાં રચવામાં આવ્યો હતો. ક્રિશ્ચિયનસેન દ્વારા પછીની પોસ્ટ્સમાં સ્પષ્ટ કરવામાં આવ્યું હતું કે તેઓ રચનાને નામ આપવાનો ઈરાદો ધરાવતા ન હતા, પરંતુ માત્ર મૂળ પોસ્ટમાંથી તેનો સંદર્ભ લેવાનો ઈરાદો ધરાવતા હતાઃ આખરે તેને "ધ બ્લેક ટ્રાન્સફોર્મ" નામ આપવાનો તેમનો પ્રયાસ સફળ થયો ન હતો ("બ્લેક" અહીં "શ્વાર [ટી] ઝેડ" પર એક શ્લોક છે, જેનો અર્થ જર્મનમાં કાળો થાય છે). અન્ય ભાષાઓ સાથે સરખામણી કેટલીક અન્ય ભાષાઓ શ્વાર્ટઝિયન ટ્રાન્સફોર્મની જેમ જ ઓપ્ટિમાઇઝેશન માટે અનુકૂળ ઇન્ટરફેસ પ્રદાન કરે છેઃ પાયથોન 2.4 અને તેનાથી ઉપર, ફંક્શન અને ઇન-પ્લેસ પદ્ધતિ બંને એક પરિમાણ લે છે જે વપરાશકર્તાને "કી ફંક્શન" પ્રદાન કરવાની મંજૂરી આપે છે (ઉપરના ઉદાહરણોની જેમ). પાયથોન 3 અને તેનાથી ઉપર, કી ફંક્શનનો ઉપયોગ એ કસ્ટમ સૉર્ટ ઓર્ડરને સ્પષ્ટ કરવાનો એકમાત્ર રસ્તો છે (અગાઉ સમર્થિત પરિમાણ કે જે વપરાશકર્તાને "સરખામણી કાર્ય" પ્રદાન કરવાની મંજૂરી આપે છે તે દૂર કરવામાં આવ્યું હતું). પાયથોન 2.4 પહેલાં, વિકાસકર્તાઓ લિસ્પ-ઓરિજિનેટેડ ડેકોરેટ-સૉર્ટ-અનડેકરેટ (DSU) રૂઢિપ્રયોગનો ઉપયોગ કરતા હતા, સામાન્ય રીતે વસ્તુઓને (સૉર્ટકી, ઓબ્જેક્ટ) ટુપલમાં લપેટીને. રૂબી 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. મેમોઇઝ પર્લ મોડ્યુલ-ખર્ચાળ કાર્યોને તેમના પરિણામોને કેશ કરીને ઝડપી બનાવે છે. સૉર્ટિંગ અલ્ગોરિધમ્સ ઉદાહરણ સાથે લેખ પર્લ કોડ ઉદાહરણ સાથે લેખ રેકેટ કોડ પર્લ