Schwartzian transform
کمپیوٹر پروگرامنگ میں، شوارٹزیئن ٹرانسفارم ایک ایسی تکنیک ہے جو آئٹمز کی فہرست کو ترتیب دینے کی کارکردگی کو بہتر بنانے کے لیے استعمال ہوتی ہے۔ یہ فقرہ موازنہ پر مبنی چھانٹ کے لیے موزوں ہے جب آرڈر دراصل عناصر کی کسی خاص پراپرٹی (کلید) کی ترتیب پر مبنی ہوتا ہے، جہاں اس پراپرٹی کا حساب لگانا ایک گہری کارروائی ہے جسے کم سے کم بار انجام دیا جانا چاہیے۔ Schwartzian ٹرانسفارم اس لحاظ سے قابل ذکر ہے کہ یہ نامزد عارضی صفوں کا استعمال نہیں کرتا ہے۔ Schwartzian ٹرانسفارم ایک Lisp آئیڈیوم کا ایک ورژن ہے جسے ڈیکوریٹ-شارٹ-انڈیکوریٹ کے نام سے جانا جاتا ہے، جو ان پٹ آئٹمز کے ساتھ عارضی طور پر منسلک کرکے ترتیب کی چابیاں کو دوبارہ گننے سے گریز کرتا ہے۔ یہ نقطہ نظر اس سے ملتا جلتا ہے، جو کسی مخصوص ان پٹ ویلیو سے مطابقت رکھنے والی کلید کے حساب کو دہرانے سے گریز کرتا ہے۔ اس کے مقابلے میں، یہ فقرہ یقین دلاتا ہے کہ ہر ان پٹ آئٹم کی کلید کا حساب بالکل ایک بار لگایا جاتا ہے، جس کے نتیجے میں اگر ان پٹ ڈیٹا میں ڈپلیکیٹ آئٹمز ہوں تو پھر بھی کچھ حسابات دہرائے جا سکتے ہیں۔ اس فقرے کا نام رینڈل ایل شوارٹز کے نام پر رکھا گیا ہے، جس نے 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 = sort {foo ($a) cmp foo ($b)} @unsorted ؛ اگرچہ یہ کوڈ سے چھوٹا ہے، لیکن یہاں بے وقوف نقطہ نظر بہت کم موثر ہو سکتا ہے اگر کلیدی فنکشن (جسے اوپر کی مثال میں کہا گیا ہے) کا حساب لگانا مہنگا ہو۔ اس کی وجہ یہ ہے کہ جب بھی دو عناصر کا موازنہ کرنے کی ضرورت ہوتی ہے تو بریکٹ کے اندر موجود کوڈ کا جائزہ لیا جاتا ہے۔ ایک بہترین موازنہ ترتیب O (n لاگ n) موازنہ انجام دیتی ہے (جہاں n فہرست کی لمبائی ہے)، ہر موازنہ کے لیے 2 کالز کے ساتھ، جس کے نتیجے میں O (n لاگ n) کو کال کرتا ہے۔ اس کے مقابلے میں، شوارٹزیئن ٹرانسفارم کا استعمال کرتے ہوئے، ہم فی عنصر صرف 1 کال کرتے ہیں، ابتدائی مرحلے میں، کل n کالوں کے لیے۔ تاہم، اگر فنکشن نسبتا سادہ ہے، تو شوارٹزیئن ٹرانسفارم کا اضافی اوور ہیڈ غیر ضروری ہو سکتا ہے۔ مثال کے طور پر، فائلوں کی فہرست کو ان کے ترمیم کے اوقات کے مطابق ترتیب دینے کے لیے، ایک بے وقوف نقطہ نظر مندرجہ ذیل ہو سکتا ہے: فنکشن نییوکمپیر (فائل اے، فائل بی) {ریٹرن ترمیم ٹائم (اے) <ترمیم ٹائم (بی)}// فرض کریں کہ اس ترتیب (فہرست، موازنہ پیش گوئی) کا استعمال کرتے ہوئے دی گئی فہرست کو ترتیب دیں// موازنہ پیش گوئی دو عناصر کا موازنہ کرنے کے لیے۔ ترتیب شدہ صف: = ترتیب دیں (فائلوں کی صف، ناییو موازنہ) جب تک کہ ہر فائل کے لیے ترمیم کا وقت نہ ہو، اس طریقہ کار کے لیے ہر بار جب کسی فائل کا ترتیب میں موازنہ کیا جاتا ہے تو ان کی دوبارہ گنتی کرنے کی ضرورت ہوتی ہے۔ Schwartzian ٹرانسفارم کا استعمال کرتے ہوئے، ترمیم کے وقت کا حساب فی فائل صرف ایک بار لگایا جاتا ہے۔ شوارٹزیائی تبدیلی میں اوپر بیان کردہ فعال فقرہ شامل ہوتا ہے، جو عارضی صفوں کا استعمال نہیں کرتا ہے۔ اسی الگورتھم کو طریقہ کار کے لحاظ سے لکھا جا سکتا ہے تاکہ یہ بہتر طور پر واضح کیا جا سکے کہ یہ کیسے کام کرتا ہے، لیکن اس کے لیے عارضی صفوں کے استعمال کی ضرورت ہوتی ہے، اور یہ شوارٹزیئن تبدیلی نہیں ہے۔ مندرجہ ذیل مثال چھدم کوڈ الگورتھم کو اس طرح سے لاگو کرتی ہے: فائلوں میں ہر فائل کے لیے تبدیل شدہ ارے فنکشن کے آخر میں ارے داخل کریں (فائل، ترمیم کا وقت (فائل)) سادہ موازنہ کریں (صف 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 اور اس سے اوپر میں، تجریدی کلاس (جس میں s شامل ہیں) ایک طریقہ پر مشتمل ہے، جو "کلیدی فنکشن" (جیسے اوپر کی مثالوں میں) کو کوڈ بلاک کے طور پر متعین کرنے کی اجازت دیتا ہے۔ D2 اور اس سے اوپر، فنکشن دستیاب ہے۔ اس کے لیے کم عارضی ڈیٹا کی ضرورت پڑ سکتی ہے اور یہ پرل آئیڈیوم یا پائیتھن اور لیسپ میں موجود ڈیکوریٹ قسم کے غیر آرائشی آئیڈیوم سے تیز ہو سکتا ہے۔ اس کی وجہ یہ ہے کہ چھانٹنا جگہ جگہ کیا جاتا ہے، اور صرف کم سے کم اضافی ڈیٹا (تبدیل شدہ عناصر کی ایک صف) بنایا جاتا ہے۔ ریکٹ کا بنیادی ترتیب فنکشن ایک #: کلیدی لفظ کی دلیل کو ایک فنکشن کے ساتھ قبول کرتا ہے جو ایک کلید نکالتا ہے، اور ایک اضافی #: کیش-کیز؟ درخواست کرتا ہے کہ نتیجے میں آنے والی اقدار کو ترتیب دینے کے دوران کیش کیا جائے۔ مثال کے طور پر، فہرست کو تبدیل کرنے کا ایک آسان طریقہ ہے۔ پی ایچ پی 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. میموائز پرل ماڈیول-مہنگے افعال کو ان کے نتائج کیشنگ کے ذریعے تیز تر بنانا۔ الگورتھم ترتیب آرٹیکلز مثال کے طور پر پرل کوڈ آرٹیکلز مثال کے طور پر ریکٹ کوڈ پرل