External sorting
بیرونی چھانٹ الگورتھم کی ایک کلاس ہے جو بڑی مقدار میں ڈیٹا کو سنبھال سکتی ہے۔ بیرونی چھانٹ اس وقت درکار ہوتی ہے جب ترتیب دیا جانے والا ڈیٹا کمپیوٹنگ ڈیوائس (عام طور پر رام) کی مرکزی میموری میں فٹ نہیں ہوتا ہے اور اس کے بجائے انہیں سست بیرونی میموری، عام طور پر ڈسک ڈرائیو میں رہنا چاہیے۔ اس طرح، بیرونی چھانٹ الگورتھم بیرونی میموری الگورتھم ہیں اور اس طرح کمپیوٹیشن کے بیرونی میموری ماڈل میں لاگو ہوتے ہیں۔ بیرونی چھانٹ الگورتھم عام طور پر دو اقسام میں آتے ہیں، ڈسٹری بیوشن چھانٹنا، جو کوئکسورٹ سے ملتا جلتا ہے، اور بیرونی ضم ترتیب، جو ضم ترتیب سے ملتا جلتا ہے۔ بیرونی ضم ترتیب عام طور پر ایک ہائبرڈ ترتیب انضمام کی حکمت عملی کا استعمال کرتی ہے۔ چھانٹنے کے مرحلے میں، مرکزی میموری میں فٹ ہونے کے لیے کافی چھوٹے ڈیٹا کے ٹکڑوں کو پڑھا جاتا ہے، ترتیب دیا جاتا ہے، اور ایک عارضی فائل میں لکھا جاتا ہے۔ ضم مرحلے میں، ترتیب دی گئی ذیلی فائلوں کو ایک بڑی فائل میں ملا دیا جاتا ہے۔ ماڈل بیرونی چھانٹ الگورتھم کا تجزیہ بیرونی میموری ماڈل میں کیا جا سکتا ہے۔ اس ماڈل میں، سائز کی کیش یا اندرونی میموری اور ایک لامحدود بیرونی میموری کو سائز کے بلاکس میں تقسیم کیا جاتا ہے، اور الگورتھم کے چلنے کے وقت کا تعین اندرونی اور بیرونی میموری کے درمیان میموری کی منتقلی کی تعداد سے ہوتا ہے۔ ان کے کیش-اوبلییوس ہم منصبوں کی طرح، غیر علامتی طور پر زیادہ سے زیادہ بیرونی چھانٹ الگورتھم کا رننگ ٹائم (بگ او نوٹیشن میں) حاصل کرتے ہیں۔ بیرونی ضم ترتیب کی ایک مثال بیرونی ضم ترتیب الگورتھم ہے، جو کہ کے وے ضم الگورتھم ہے۔ یہ ان ٹکڑوں کو ترتیب دیتا ہے جو ہر ایک رام میں فٹ ہوتے ہیں، پھر ترتیب شدہ ٹکڑوں کو ایک ساتھ ملا دیتا ہے۔ الگورتھم پہلے ایک وقت میں آئٹمز کو ترتیب دیتا ہے اور ترتیب دی گئی فہرستوں کو بیرونی میموری میں واپس رکھتا ہے۔ اس کے بعد یہ بار بار ان ترتیب شدہ فہرستوں پر ایک-راستہ ضم کرتا ہے۔ اس انضمام کو کرنے کے لیے، ہر ترتیب شدہ فہرست کے عناصر کو اندرونی میموری میں لوڈ کیا جاتا ہے، اور کم سے کم بار بار آؤٹ پٹ کیا جاتا ہے۔ مثال کے طور پر، صرف 100 میگا بائٹس ریم کا استعمال کرتے ہوئے 900 میگا بائٹس ڈیٹا کو ترتیب دینے کے لیے: مرکزی میموری میں 100 ایم بی ڈیٹا کو پڑھیں اور کسی روایتی طریقے سے ترتیب دیں، جیسے کہ کوئکسورٹ۔ ترتیب شدہ ڈیٹا کو ڈسک پر لکھیں۔ مراحل 1 اور 2 کو اس وقت تک دہرائیں جب تک کہ تمام ڈیٹا 100 ایم بی حصوں میں ترتیب نہ دیا جائے (900 ایم بی/100 ایم بی = 9 حصے ہیں)، جنہیں اب ایک واحد آؤٹ پٹ فائل میں ضم کرنے کی ضرورت ہے۔ مین میموری میں ان پٹ بفر میں ہر ترتیب شدہ حصے کے پہلے 10 ایم بی (= 100 ایم بی/(9 حصے + 1)) کو پڑھیں اور بقیہ 10 ایم بی کو آؤٹ پٹ بفر کے لیے مختص کریں۔ (عملی طور پر، یہ آؤٹ پٹ بفر کو بڑا اور ان پٹ بفر کو قدرے چھوٹا بنانے کے لیے بہتر کارکردگی فراہم کر سکتا ہے۔) 9 طرفہ انضمام انجام دیں اور نتیجہ کو آؤٹ پٹ بفر میں محفوظ کریں۔ جب بھی آؤٹ پٹ بفر بھرتا ہے، اسے حتمی ترتیب شدہ فائل پر لکھیں اور اسے خالی کریں۔ جب بھی 9 ان پٹ بفرز میں سے کوئی بھی خالی ہوتا ہے، تو اسے اس سے وابستہ 100 ایم بی ترتیب شدہ حصے کے اگلے 10 ایم بی سے بھریں جب تک کہ حصے سے مزید ڈیٹا دستیاب نہ ہو۔ یہ وہ کلیدی مرحلہ ہے جو بیرونی انضمام کی ترتیب کو بیرونی طور پر کام کرتا ہے-کیونکہ ضم الگورتھم صرف ہر ایک حصے کے ذریعے ترتیب سے ایک پاس کرتا ہے، ہر حصے کو مکمل طور پر لوڈ کرنے کی ضرورت نہیں ہے ؛ بلکہ، حصے کے ترتیب وار حصوں کو ضرورت کے مطابق لوڈ کیا جا سکتا ہے۔ تاریخی طور پر، ایک قسم کے بجائے، بعض اوقات ابتدائی تقسیم کو انجام دینے کے لیے ایک متبادل انتخاب الگورتھم کا استعمال کیا جاتا تھا، تاکہ اوسط نصف زیادہ سے زیادہ آؤٹ پٹ حصے پیدا کیے جا سکیں جو لمبائی سے دوگنا ہوں۔ اضافی پاس پچھلی مثال دو پاس کی ترتیب ہے: پہلے ترتیب دیں، پھر ضم کریں۔ ترتیب ایک واحد کے-وے انضمام کے ساتھ ختم ہوتی ہے، بجائے اس کے کہ دو طرفہ انضمام پاس کی ایک سیریز جیسا کہ ایک عام ان میموری انضمام ترتیب میں ہوتا ہے۔ اس کی وجہ یہ ہے کہ ہر مرج پاس ڈسک سے ہر ویلیو کو پڑھتا اور لکھتا ہے، اس لیے پاس کی تعداد کو کم کرنا کے وے مرج کی اضافی لاگت کی تلافی سے زیادہ ہے۔ سنگل پاس انضمام کی حد یہ ہے کہ جیسے جیسے حصوں کی تعداد بڑھتی جائے گی، میموری کو مزید بفرز میں تقسیم کیا جائے گا، اس لیے ہر بفر چھوٹا ہوتا ہے۔ آخر کار، ریڈز اتنے چھوٹے ہو جاتے ہیں کہ ڈیٹا ٹرانسفر کے مقابلے ڈسک سیکس پر زیادہ وقت گزارا جاتا ہے۔ ایک عام مقناطیسی ہارڈ ڈسک ڈرائیو میں 10 ایم ایس رسائی کا وقت اور 100 ایم بی/ایس ڈیٹا کی منتقلی کی شرح ہو سکتی ہے، لہذا ہر تلاش میں 1 ایم بی ڈیٹا کی منتقلی میں اتنا ہی وقت لگتا ہے۔ اس طرح، ترتیب دینے کے لیے، فرض کریں، 100 ایم بی ریم میں 50 جی بی، ایک واحد 500 طرفہ مرج پاس کا استعمال موثر نہیں ہے: ہم ایک ہی وقت میں ہر حصے سے صرف 100 ایم بی/501 ≈ 200 کے بی پڑھ سکتے ہیں، اس لیے ڈسک کا 5/6 وقت تلاش کرنے میں صرف ہوتا ہے۔ دو مرج پاس استعمال کرنے سے مسئلہ حل ہو جاتا ہے۔ پھر چھانٹنے کا عمل اس طرح نظر آسکتا ہے: 500 × 100 ایم بی ترتیب شدہ حصے بنانے کے لیے ابتدائی چنک چھانٹنے والے پاس کو پہلے کی طرح چلائیں۔ ایک وقت میں 25 × 100 ایم بی کے حصوں کو ملا کر پہلا مرج پاس چلائیں، جس کے نتیجے میں 20 × 2.5 جی بی کے الگ الگ حصے بنتے ہیں۔ 20 × 2.5 جی بی ترتیب شدہ حصوں کو ایک ہی 50 جی بی ترتیب شدہ نتیجہ میں ضم کرنے کے لیے دوسرا ضم پاس چلائیں حالانکہ اس کے لیے ڈیٹا پر اضافی پاس کی ضرورت ہوتی ہے، ہر ریڈ اب 4 ایم بی لمبا ہے، اس لیے ڈسک کا صرف 1/5 وقت تلاش کرنے میں صرف ہوتا ہے۔ انضمام پاس کے دوران ڈیٹا کی منتقلی کی کارکردگی میں بہتری (16.6% سے 80 ٪ تک تقریبا 5 × بہتری ہے) انضمام پاس کی دوگنی تعداد سے زیادہ ہے۔ تغیرات میں کچھ مراحل کے لیے سولڈ اسٹیٹ ڈسک جیسے انٹرمیڈیٹ میڈیم کا استعمال شامل ہے۔ تیز رفتار عارضی اسٹوریج کو پورے ڈیٹا سیٹ کو برقرار رکھنے کے لیے اتنا بڑا ہونے کی ضرورت نہیں ہے، جو کہ دستیاب مین میموری سے کافی زیادہ ہے۔ 1 جی بی عارضی ایس ایس ڈی اسٹوریج کے ساتھ اوپر کی مثال کو دہراتے ہوئے، پہلا پاس اس عارضی جگہ سے پڑھے گئے 10 × 100 ایم بی ترتیب شدہ حصوں کو ضم کر سکتا ہے تاکہ 50x1 جی بی ترتیب شدہ حصوں کو ایچ ڈی ڈی میں لکھا جا سکے۔ ایس ایس ڈی کی اعلی بینڈوتھ اور بے ترتیب ریڈ تھرو پٹ پہلے پاس کو تیز کرنے میں مدد کرتی ہے، اور دوسرے پاس کے لیے ایچ ڈی ڈی ریڈز پھر 2 ایم بی ہو سکتے ہیں، جو اتنا بڑا ہے کہ سیکس زیادہ تر پڑھنے کا وقت نہیں لیں گے۔ ایس ایس ڈی کو انضمام کے مرحلے میں ریڈ بفر کے طور پر بھی استعمال کیا جا سکتا ہے، جس سے ایچ ڈی ڈی اسٹوریج سے کم بڑے ریڈز (اس مثال میں 20 ایم بی ریڈز) کی اجازت ملتی ہے۔ رام کے مقابلے میں ایس ایس ڈی کی صلاحیت کی کم لاگت کو دیکھتے ہوئے، ایس ایس ڈی بہت محدود میموری کے ساتھ بڑے ان پٹ کو ترتیب دینے کے لیے ایک کفایتی ٹول ہو سکتا ہے۔ ان میموری اقسام کی طرح، موثر بیرونی اقسام کے لیے O (n لاگ n) وقت درکار ہوتا ہے: تیزی سے بڑھتے ہوئے ڈیٹا سیٹس کے لیے لکیری طور پر بڑھتے ہوئے پاس کی تعداد درکار ہوتی ہے جو ہر ایک O (n) وقت لیتا ہے۔ معقول مفروضوں کے تحت ہارڈ ڈرائیو پر محفوظ کردہ کم از کم 500 جی بی ڈیٹا کو 1 جی بی مین میموری کا استعمال کرتے ہوئے ترتیب دیا جا سکتا ہے اس سے پہلے کہ تیسرا پاس فائدہ مند ہو جائے، اور کئی بار اس سے زیادہ ڈیٹا کو چوتھا پاس مفید ہونے سے پہلے ترتیب دیا جا سکتا ہے۔ اہم میموری کا سائز اہم ہے۔ ترتیب دینے کے لیے وقف ڈبلنگ میموری حصوں کی تعداد اور فی حصے پڑھنے کی تعداد کو نصف کر دیتی ہے، جس سے مطلوبہ تلاشوں کی تعداد تقریبا تین چوتھائی تک کم ہو جاتی ہے۔ سرورز پر ریم اور ڈسک اسٹوریج کا تناسب اکثر ایک سے زیادہ پاس والی مشین کے بجائے مشینوں کے کلسٹر پر بہت زیادہ اقسام کرنا آسان بناتا ہے۔ اعلی بے ترتیب پڑھنے کی کارکردگی والے میڈیا جیسے سالڈ اسٹیٹ ڈرائیوز (ایس ایس ڈی) بھی اس رقم میں اضافہ کرتے ہیں جسے اضافی پاس سے کارکردگی کو بہتر بنانے سے پہلے ترتیب دیا جا سکتا ہے۔ بیرونی تقسیم کی ترتیب بیرونی تقسیم کی ترتیب تیز رفتار کے مترادف ہے۔ الگورتھم تقریبا محوروں کو تلاش کرتا ہے اور ان کا استعمال عناصر کو تقریبا مساوی سائز کے ذیلی صفوں میں تقسیم کرنے کے لیے کرتا ہے، جن میں سے ہر عنصر اگلے سے چھوٹے ہوتے ہیں، اور پھر اس وقت تک دوبارہ استعمال ہوتا ہے جب تک کہ ذیلی صفوں کے سائز بلاک کے سائز سے کم نہ ہوں۔ جب سبارے بلاک سائز سے کم ہوتے ہیں، تو چھانٹنا تیزی سے کیا جا سکتا ہے کیونکہ تمام ریڈز اور رائٹس کیش میں کیے جاتے ہیں، اور بیرونی میموری ماڈل میں آپریشنز کی ضرورت ہوتی ہے۔ تاہم، بالکل محور تلاش کرنا اتنا تیز نہیں ہوگا کہ بیرونی تقسیم کی ترتیب کو غیر علامتی طور پر زیادہ سے زیادہ بہتر بنایا جا سکے۔ اس کے بجائے، ہمیں قدرے کم محور ملتے ہیں۔ ان محوروں کو تلاش کرنے کے لیے، الگورتھم ان پٹ عناصر کو حصوں میں تقسیم کرتا ہے، اور ہر عنصر کو لیتا ہے، اور محوروں کو تلاش کرنے کے لیے میڈینز الگورتھم کا بار بار استعمال کرتا ہے۔ ضم اور تقسیم پر مبنی الگورتھم کے درمیان ایک دوہری، یا بنیادی مماثلت ہے۔ کارکردگی کمپیوٹر سائنسدان جم گرے کے ذریعہ تخلیق کردہ ترتیب شدہ بینچ مارک، باریک ٹیونڈ ہارڈ ویئر اور سافٹ ویئر کا استعمال کرتے ہوئے نافذ کردہ بیرونی ترتیب دینے والے الگورتھم کا موازنہ کرتا ہے۔ جیتنے والے نفاذ کئی تکنیکوں کا استعمال کرتے ہیں: متوازی کا استعمال کرتے ہوئے متعدد ڈسک ڈرائیوز کو متوازی طور پر استعمال کیا جا سکتا ہے تاکہ ترتیب وار پڑھنے اور لکھنے کی رفتار کو بہتر بنایا جا سکے۔ یہ ایک بہت ہی لاگت سے موثر بہتری ہو سکتی ہے: لاگت پر مبنی پینی قسم کے زمرے میں ایک ترتیب شدہ بینچ مارک فاتح دوسری صورت میں مڈرینج مشین میں چھ ہارڈ ڈرائیوز کا استعمال کرتا ہے۔ جدید ملٹی کور کمپیوٹرز پر عمل کو تیز کرنے کے لیے ترتیب دینے والا سافٹ ویئر متعدد دھاگوں کا استعمال کر سکتا ہے۔ سافٹ ویئر اسنکرونس I/O کا استعمال کر سکتا ہے تاکہ ڈیٹا کے ایک رن کو ترتیب دیا جا سکے یا ضم کیا جا سکے جبکہ دوسرے رن کو ڈسک سے پڑھا یا لکھا جا رہا ہو۔ تیز نیٹ ورک لنکس کے ذریعے جڑی متعدد مشینیں متوازی طور پر ایک بڑے ڈیٹا سیٹ کے ہر حصے کو ترتیب دے سکتی ہیں۔ ہارڈ ویئر کی رفتار میں اضافہ ترتیب دینے کے لیے زیادہ رام کا استعمال ڈسک کی تلاش کی تعداد کو کم کر سکتا ہے اور مزید پاس کی ضرورت سے بچ سکتا ہے۔ سالڈ اسٹیٹ ڈرائیوز جیسی تیز بیرونی میموری ترتیبات کو تیز کر سکتی ہے، یا تو اگر ڈیٹا اتنا چھوٹا ہو کہ مکمل طور پر ایس ایس ڈی پر فٹ ہو یا، شاذ و نادر ہی، ایس ایس ڈی کے سائز کے حصوں کو تھری پاس ترتیب میں ترتیب دینے میں تیزی لانے کے لیے۔ بہت سے دوسرے عوامل ہارڈ ویئر کی زیادہ سے زیادہ چھانٹ کی رفتار کو متاثر کر سکتے ہیں: سی پی یو کی رفتار اور کور کی تعداد، رام تک رسائی کی تاخیر، ان پٹ/آؤٹ پٹ بینڈوتھ، ڈسک پڑھنے/لکھنے کی رفتار، ڈسک تلاش کا وقت، اور دیگر۔ رکاوٹوں کو کم کرنے کے لیے ہارڈ ویئر کو "متوازن" کرنا ایک موثر چھانٹ کے نظام کو ڈیزائن کرنے کا ایک اہم حصہ ہے۔ لاگت کی کارکردگی کے ساتھ ساتھ مطلق رفتار بھی اہم ہو سکتی ہے، خاص طور پر کلسٹر ماحول میں جہاں کم نوڈ کی لاگت زیادہ نوڈس خریدنے کی اجازت دیتی ہے۔ سافٹ ویئر کی رفتار میں اضافہ کچھ ترتیب شدہ بینچ مارک داخل کنندگان ترتیب دینے کے پہلے مرحلے کے لیے ریڈکس کی ترتیب پر ایک تغیر کا استعمال کرتے ہیں: وہ ڈیٹا کو اس کی قیمت کے آغاز کی بنیاد پر بہت سے "ڈبوں" میں سے ایک میں الگ کرتے ہیں۔ بینچ مارک ڈیٹا کو ترتیب دینا بے ترتیب ہے اور خاص طور پر اس اصلاح کے لیے موزوں ہے۔ ان پٹ، انٹرمیڈیٹ فائلوں اور آؤٹ پٹ کو کمپیکٹ کرنے سے I/O پر خرچ ہونے والے وقت کو کم کیا جا سکتا ہے، لیکن ترتیب شدہ بینچ مارک میں اس کی اجازت نہیں ہے۔ چونکہ ترتیب شدہ بینچ مارک مختصر (10-بائٹ) چابیاں استعمال کرتے ہوئے لمبے (100-بائٹ) ریکارڈز کو ترتیب دیتا ہے، اس لیے ترتیب دینے والا سافٹ ویئر بعض اوقات میموری I/O حجم کو کم کرنے کے لیے چابیاں کو اقدار سے الگ ترتیب دیتا ہے۔ مین فریم سارٹ مرج بیرونی میموری الگورتھم فنیلسورٹ کیش-اوبلیوئس ڈسٹری بیوشن سارٹ حوالہ جات ایس ٹی ایکس ایکس ایل، ایک الگورتھم ٹول کٹ جس میں بیرونی انضمام شامل ہے ایک بیرونی انضمام مثال جاوا میں اے کے-وے انضمام نفاذ بیرونی میموری ترتیب کا استعمال کرتے ہوئے نمونہ پینوسورٹ نفاذ جوڈی صف ترتیب ترتیب ترتیب ترتیب بیرونی میموری الگورتھم