ادھاری بھری ڈسک کمپیوٹراں نوں تیز کر دیندی اے
کجھ مسئلے ویلے وچ سستے پر یادداشت دے بھُکھے ہوندے نیں، کجھ ایہدے اُلٹ۔ کجھ بنیادی کماں لئی، نظریہ داناں نے ایس لین دین اُتے سخت حداں ثابت کیتیاں نیں: نکی کم والی یادداشت نال تسیں تیز نئیں ہو سکدے۔ اک نواں مقالہ وکھاندا اے کہ اک عجیب وسیلہ، یعنی اجیہی یادداشت جیہڑی پہلاں ای بھری ہوئی اے تے جیہنوں صحیح سلامت واپس کرنا اے، ایہناں حداں نوں توڑ دیندا اے۔
ادھاری ہارڈ ڈرائیو
ایس ماڈل نوں عمل انگیز حساب (catalytic computing) آکھدے نیں، جیہڑا 2014 وچ بورمین، کلیو، کوتسکی، لوف تے سپیلمین نے پیش کیتا۔ اک الگورتھم نوں اک نکی صاف یادداشت ملدی اے، n ناپ دے اِن پُٹ لئی log n بِٹاں دے لگ بھگ، نال اک وڈی گندی یادداشت جیہڑی پہلاں ای اجیہے مَن مرضی ڈیٹے نال بھری اے جیہڑا اوہنے آپ نئیں چُنیا۔ اوہ دوواں نوں جیویں چاہوے ورت سکدا اے، پر جدوں رُکے، گندی یادداشت دا ہر بِٹ ٹھیک اونج ای ہونا چاہیدا اے جیویں پہلاں سی۔
لکھاری عام مثال ورتدے نیں: تسیں اک حساب چلان لئی کسے یار دی بہت وڈی ہارڈ ڈرائیو ادھار لیندے او، جیہڑی قیمتی ڈیجیٹل یاداں نال بھری اے۔ تسیں یار نئیں گوانا چاہندے، ایس لئی کم مُکن مگروں ہر بِٹ واپس رکھ دیندے او۔
ایہہ ماڈل پہلاں ایہہ ثابت کرن لئی بنایا گیا سی کہ اجیہی یادداشت بیکار اے۔ اندروں لگدا اے کہ سب کجھ واپس کرن لئی تہانوں ساری معلومات رکھنی پیندی اے، ایس لئی تسیں کدی کوئی تھاں خالی نئیں کردے۔ حیرانی دی گل اے کہ ایہدا اُلٹ سچ نکلیا: بھری یادداشت اجیہے مسئلے حل کرن دیندی اے جنہاں نوں صرف صاف یادداشت نال حل کرنا کسے نوں نئیں آندا۔ پر اوہ نتیجے تھاں (یادداشت) بارے سن، تے الگورتھم بہت ای سُست سن۔
ثابت شدہ ممکن توں وی تیز
ایڈیلمو موریسن اوروزکو، نیتھن شیفیلڈ تے رائن ولیمز (MIT) ہُن رفتار ول ویکھدے نیں۔ لوگارتھمی صاف یادداشت تے کثیر رقمی مقدار دی ادھاری یادداشت نال، اوہ اجیہے الگورتھم دیندے نیں جیہڑے:
- اک لسٹ نوں ترتیب دیندے نیں تے اک وکھری فوریئر ٹرانسفارم کڈھدے نیں، n^(1+o(1)) ویلے وچ، یعنی تقریباً سدھی لکیر؛
- میٹرکساں نوں ضرب دیندے نیں، n^(ω+o(1)) ویلے وچ، یعنی بے حد یادداشت نال سب توں چنگے جانے پچھانے طریقے جِنّے تیز۔
ادھاری ڈسک توں بنا، ثابت ہو چکیا اے کہ ویلے تے یادداشت دی ضرب ترتیب دین تے فوریئر ٹرانسفارم لئی گھٹو گھٹ n² دے درجے دی، تے میٹرکس ضرب لئی n³ دے درجے دی ہونی چاہیدی اے۔ ایس لئی ایہہ عمل انگیز الگورتھم اوہ رفتاراں پھڑدے نیں جیہڑیاں کوئی عام نکی یادداشت والا الگورتھم نئیں پھڑ سکدا۔ لکھاری ایہنوں پہلا غیر مشروط ثبوت آکھدے نیں کہ عمل انگیز الگورتھم اپنے غیر عمل انگیز ساتھیاں توں اگے نکل جاندے نیں۔
بدلو، پڑھو، واپس کرو
مُکھ جُز اک نکی ترتیبیاتی چال اے۔ فرض کرو اک الگورتھم ادھاری یادداشت دے اک حصے نوں اک انجانی قیمت τ تے τ + x وچکار بدل سکدا اے، جتھے x اوہ نتیجہ اے جیہدی اوہنوں لوڑ اے۔ اک وڈی “مددگار” جدول وچ، جیہڑی وی ادھاری اے، دھیان نال چُنے اندراجاں دے اک سیٹ وچ 1 جمع کرو۔ τ تھاں والا اندراج صرف تے صرف اوس ویلے اک ودھدا اے جدوں x کسے دتے گئے سیٹ وچ ہووے۔ فیر ہر قدم پِچھے ول چلاؤ، تے ڈسک پہلاں ورگی ہو جاندی اے، سوائے جواب دے اوس بِٹ دے جیہڑا تسیں چاہندے سو۔
ایس چال نوں تہہ تہہ اُتے رکھن نال گھٹ ڈونگھے سرکٹ چھیتی جانچے جاندے نیں۔ فیر لکھاری ترتیب دین والے نیٹ ورکاں، تیز فوریئر ٹرانسفارماں تے تیز میٹرکس ضرب نوں اجیہے سرکٹاں دے روپ وچ دوبارہ لکھدے نیں۔ حساب وچ، صرف اوہ تہاں جیہڑیاں دو انجانیاں نوں ضرب دیندیاں نیں ودھ خرچ منگدیاں نیں؛ نری سدھی لکیر والیاں تہاں تقریباً مفت نیں۔
اک انصاف والا مقابلہ
اک اعتراض: پرانیاں حداں ایہہ مندیاں نیں کہ جواب اک وکھری آؤٹ پُٹ ٹیپ اُتے کھبے توں سجے اک واری لکھیا جاندا اے، جدکہ عمل انگیز الگورتھم اپنا جواب ادھاری ڈسک وچ لکھدے نیں۔ مقالہ ایس گل نوں سانبھدا اے۔ لکھاری وکھاندے نیں کہ اوہناں دے الگورتھم اک آؤٹ پُٹ ٹیپ اُتے دو پھیریاں وچ جواب لکھ سکدے نیں، تے عام الگورتھماں لئی دو پھیرے اک توں ودھ مدد نئیں کردے۔ ایس لئی حداں ہلے وی لاگو نیں تے وکھریواں قائم اے۔ اوہ ایہہ وی ثابت کردے نیں کہ ادھاری ڈسک ہوندیاں وی اک پھیرا کافی نئیں: فیر ترتیب دینا اوسے n² دی کندھ نال ٹکراندا اے۔
فائدہ لین والیاں دی لمی لسٹ
ایہو اوزار وڈے پورے عدداں تے کثیر رقمیاں نوں ضرب دین، نیٹ ورکاں وچ تکوناں گنن تے کلیکاں (clique) لبھن، رستے تے چکر پھڑن، تے وائلڈ کارڈ والے متن نمونے ملان لئی تیز عمل انگیز الگورتھم دیندے نیں۔ اوہناں دے چلن دے ویلے، نکے ضرباں تک، اوہناں سب توں چنگے جانے پچھانے الگورتھماں نال ملدے نیں جنہاں کول جِنّی چاہن یادداشت ہوندی اے۔ ہر حالت وچ ادھاری یادداشت نوں ٹھیک اونج ای واپس آنا پیندا اے جیویں اوہ ادھار دتی گئی سی۔