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