उसनी घेतलेली भरलेली डिस्क संगणकांना अधिक वेगवान करते

काही प्रश्न वेळेच्या दृष्टीने स्वस्त पण स्मृतीसाठी हावरे असतात, तर काही उलट. काही मूलभूत कामांसाठी सिद्धांतकारांनी या देवाणघेवाणीवर कठोर मर्यादा सिद्ध केल्या आहेत: लहान कार्य-स्मृती असेल, तर तुम्ही वेगवान होऊ शकत नाही. एक नवा शोधनिबंध दाखवतो की एक विचित्र संसाधन — आधीच भरलेली आणि अखंड परत करावी लागणारी स्मृती — या मर्यादा मोडते.

उसनी घेतलेली हार्ड ड्राइव्ह

या प्रारूपाला उत्प्रेरक संगणन (catalytic computing) म्हणतात. 2014 मध्ये Buhrman, Cleve, Koucký, Loff आणि Speelman यांनी ते मांडले. अल्गोरिदमला एक अगदी लहान स्वच्छ स्मृती मिळते, n आकाराच्या इनपुटसाठी log n बिट्सच्या क्रमाची, आणि त्याशिवाय एक प्रचंड मळलेली स्मृती, जी त्याने न निवडलेल्या कोणत्याही डेटाने आधीच भरलेली असते. तो दोन्ही स्मृती हव्या तशा वापरू शकतो, पण थांबताना मळलेल्या स्मृतीचा प्रत्येक बिट आधी होता अगदी तसाच असला पाहिजे.

लेखक नेहमीची उपमा वापरतात: गणना करण्यासाठी तुम्ही मित्राची प्रचंड हार्ड ड्राइव्ह उसनी घेता, मौल्यवान डिजिटल आठवणींनी भरलेली. तुम्हाला मित्र गमवायचा नाही, म्हणून काम झाल्यावर तुम्ही प्रत्येक बिट पूर्ववत करता.

सुरुवातीला हे प्रारूप अशी स्मृती निरुपयोगी आहे हे सिद्ध करण्यासाठी होते. अंतर्ज्ञानाने पाहता, सर्व काही पूर्ववत करायचे तर सर्व माहिती जपून ठेवावी लागते, त्यामुळे कधीच जागा मोकळी होत नाही. आश्चर्य म्हणजे उलटेच खरे ठरले: भरलेली स्मृती असे प्रश्न सोडवू देते जे फक्त स्वच्छ स्मृतीने कसे सोडवायचे हे कोणालाच माहीत नाही. पण ते निष्कर्ष जागेबद्दल होते, आणि ते अल्गोरिदम अत्यंत संथ होते.

सिद्धपणे शक्य असलेल्यापेक्षा अधिक वेगवान

MIT चे Adelmo Morrison Orozco, Nathan Sheffield आणि Ryan Williams आता वेगाकडे पाहतात. लॉगरिदमिक स्वच्छ स्मृती आणि बहुपदी (polynomial) प्रमाणातील उसनी स्मृती वापरून ते असे अल्गोरिदम देतात जे:

• यादीची क्रमवारी लावतात आणि विविक्त फूरिये रूपांतर (discrete Fourier transform) n^(1+o(1)) वेळेत, म्हणजे जवळजवळ रेषीय वेळेत, काढतात;
• आव्यूहांचा गुणाकार n^(ω+o(1)) वेळेत करतात, म्हणजे अमर्याद स्मृतीसह ज्ञात असलेल्या सर्वोत्तम पद्धतीइतक्या वेगाने.

उसन्या डिस्कशिवाय, हे सिद्ध झालेले आहे की वेळ आणि स्मृती यांचा गुणाकार क्रमवारी व फूरिये रूपांतरासाठी किमान n² च्या क्रमाचा, आणि आव्यूह-गुणाकारासाठी n³ च्या क्रमाचा असलाच पाहिजे. त्यामुळे हे उत्प्रेरक अल्गोरिदम असा वेग गाठतात जो कोणताही साधा लहान-स्मृतीचा अल्गोरिदम गाठू शकत नाही. उत्प्रेरक अल्गोरिदम त्यांच्या अनुत्प्रेरक प्रतिस्पर्ध्यांपेक्षा सरस ठरतात याचे हे पहिले बिनशर्त प्रात्यक्षिक आहे, असे लेखक म्हणतात.

बदला, वाचा, पूर्ववत करा

मुख्य घटक म्हणजे एक छोटीशी संयोजनात्मक (combinatorial) युक्ती. समजा एखादा अल्गोरिदम उसन्या स्मृतीचा एखादा भाग एका अज्ञात मूल्य τ आणि τ + x यांच्यात बदलू शकतो, जिथे x हा त्याला हवा असलेला निकाल आहे. एका मोठ्या “साहाय्यक” तक्त्यात — तोही उसनाच — काळजीपूर्वक निवडलेल्या नोंदींच्या संचात 1 मिळवा. τ या स्थानावरील नोंद एकाने वाढते जर आणि केवळ जर x एखाद्या दिलेल्या संचात असेल. मग प्रत्येक पायरी उलट चालवा, आणि डिस्क पूर्वीसारखी होते, फक्त तुम्हाला हवा असलेला उत्तराचा तो बिट सोडून.

ही युक्ती थरावर थर रचून उथळ परिपथांचे (circuits) मूल्यमापन वेगाने करता येते. मग लेखक क्रमवारी-जाळी (sorting networks), जलद फूरिये रूपांतरे आणि जलद आव्यूह-गुणाकार यांची मांडणी अशा परिपथांच्या रूपात करतात. अंकगणितात, फक्त दोन अज्ञातांचा गुणाकार करणाऱ्या थरांनाच जास्तीचा खर्च येतो; पूर्णपणे रेषीय थर जवळजवळ मोफत मिळतात.

न्याय्य तुलना

एक आक्षेप असा: पारंपरिक मर्यादा असे गृहीत धरतात की उत्तर एका वेगळ्या आउटपुट टेपवर डावीकडून उजवीकडे एकदाच लिहिले जाते, तर उत्प्रेरक अल्गोरिदम आपले उत्तर उसन्या डिस्कवर लिहितात. शोधनिबंध या मुद्द्याला उत्तर देतो. लेखक दाखवतात की त्यांचे अल्गोरिदम आउटपुट टेपवरून दोन फेऱ्यांमध्ये उत्तर लिहू शकतात, आणि साध्या अल्गोरिदमसाठी दोन फेऱ्या एका फेरीपेक्षा अधिक उपयोगी पडत नाहीत. त्यामुळे मर्यादा लागू राहतात, आणि हा फरक टिकून राहतो. ते हेही सिद्ध करतात की उसन्या डिस्कसहसुद्धा एक फेरी पुरेशी नाही: तेव्हा क्रमवारी त्याच n² च्या अडथळ्याला धडकते.

लाभार्थ्यांची मोठी यादी

हीच साधने मोठ्या पूर्णांकांचा व बहुपदींचा गुणाकार, जाळ्यांमधील त्रिकोण मोजणे आणि क्लिक्स (cliques) शोधणे, मार्ग व आवर्तने (cycles) ओळखणे, आणि वाइल्डकार्डसह मजकुराचे नमुने जुळवणे यांसाठीही वेगवान उत्प्रेरक अल्गोरिदम देतात. त्यांचा धावण्याचा वेळ, लहान घटक वगळता, हवी तेवढी स्मृती असलेल्या सर्वोत्तम ज्ञात अल्गोरिदमशी जुळतो. प्रत्येक बाबतीत, उसनी स्मृती उसनी दिली होती अगदी तशीच परत यावी लागते.