उधार ली गई भरी हुई डिस्क कंप्यूटर को तेज़ बनाती है
कुछ समस्याएँ समय में सस्ती पर मेमोरी की भूखी होती हैं, कुछ इसके उलट। कुछ बुनियादी कामों के लिए सिद्धांतकारों ने इस लेन-देन की कठोर सीमाएँ साबित की हैं: छोटी कार्य-मेमोरी के साथ आप तेज़ नहीं हो सकते। एक नया शोधपत्र दिखाता है कि एक अजीब संसाधन, यानी ऐसी मेमोरी जो पहले से भरी है और जिसे जस-का-तस लौटाना है, इन सीमाओं को तोड़ देता है।
उधार की हार्ड ड्राइव
इस मॉडल को कैटेलिटिक कंप्यूटिंग कहा जाता है, जिसे 2014 में Buhrman, Cleve, Koucký, Loff और Speelman ने प्रस्तुत किया था। एक एल्गोरिद्म को एक बहुत छोटी साफ़ मेमोरी मिलती है, n आकार के इनपुट के लिए लगभग log n बिट, और साथ में एक विशाल गंदी मेमोरी, जो पहले से मनमाने डेटा से भरी है जिसे उसने नहीं चुना। वह दोनों का जैसे चाहे इस्तेमाल कर सकता है, लेकिन रुकते समय गंदी मेमोरी का हर बिट ठीक वैसा ही होना चाहिए जैसा पहले था।
लेखक मानक उदाहरण का सहारा लेते हैं: आप एक गणना चलाने के लिए किसी दोस्त की विशाल हार्ड ड्राइव उधार लेते हैं, जो क़ीमती डिजिटल यादों से भरी है। आप दोस्त को खोना नहीं चाहते, इसलिए काम ख़त्म होने पर हर बिट को बहाल कर देते हैं।
शुरुआत में यह मॉडल यह साबित करने के लिए बना था कि ऐसी मेमोरी बेकार है। सहज रूप से, सब कुछ बहाल करने के लिए आपको सारी जानकारी रखनी पड़ती है, इसलिए आप कभी कोई जगह ख़ाली नहीं कर पाते। हैरानी की बात यह कि उल्टा सच निकला: भरी हुई मेमोरी आपको ऐसी समस्याएँ हल करने देती है जिन्हें केवल साफ़ मेमोरी से हल करना कोई नहीं जानता। लेकिन वे नतीजे स्थान (space) के बारे में थे, और एल्गोरिद्म बेहद धीमे थे।
जो सिद्ध रूप से संभव है, उससे भी तेज़
Adelmo Morrison Orozco, Nathan Sheffield और Ryan Williams (MIT) अब गति पर ध्यान देते हैं। लघुगणकीय साफ़ मेमोरी और बहुपद मात्रा की उधार मेमोरी के साथ, वे ऐसे एल्गोरिद्म देते हैं जो:
- किसी सूची को सॉर्ट करते हैं और असतत फ़ूरिए रूपांतरण n^(1+o(1)) समय में, यानी लगभग रैखिक समय में, निकालते हैं;
- मैट्रिक्स का गुणन n^(ω+o(1)) समय में करते हैं, उतना ही तेज़ जितना असीमित मेमोरी के साथ सबसे अच्छा ज्ञात तरीक़ा।
उधार की डिस्क के बिना, यह सिद्ध है कि समय और मेमोरी का गुणनफल सॉर्टिंग और फ़ूरिए रूपांतरण के लिए कम से कम n² के क्रम का, और मैट्रिक्स गुणन के लिए n³ के क्रम का होना चाहिए। इसलिए ये कैटेलिटिक एल्गोरिद्म ऐसी गति तक पहुँचते हैं जहाँ कोई भी साधारण छोटी-मेमोरी एल्गोरिद्म नहीं पहुँच सकता। लेखक इसे पहला बिना-शर्त प्रदर्शन कहते हैं कि कैटेलिटिक एल्गोरिद्म अपने ग़ैर-कैटेलिटिक समकक्षों से बेहतर प्रदर्शन करते हैं।
बदलो, पढ़ो, पलटो
मुख्य घटक एक छोटी-सी संयोजनात्मक (कॉम्बिनेटोरियल) तरकीब है। मान लीजिए कोई एल्गोरिद्म उधार मेमोरी के एक हिस्से को एक अज्ञात मान τ और τ + x के बीच बदल सकता है, जहाँ x वह नतीजा है जिसमें उसकी रुचि है। एक बड़ी “सहायक” तालिका में, जो भी उधार की है, ध्यान से चुनी गई प्रविष्टियों के एक समूह में 1 जोड़िए। स्थान τ पर की प्रविष्टि एक से बढ़ती है यदि और केवल यदि x किसी दिए गए समुच्चय का सदस्य है। फिर हर क़दम को पीछे की ओर चलाइए, और डिस्क पहले जैसी हो जाती है, सिवाय उस उत्तर-बिट के जो आप चाहते थे।
इस तरकीब को परत-दर-परत जमाने से उथले सर्किट जल्दी हल हो जाते हैं। फिर लेखक सॉर्टिंग नेटवर्क, फ़ास्ट फ़ूरिए रूपांतरण और तेज़ मैट्रिक्स गुणन को ऐसे ही सर्किटों के रूप में दोबारा लिखते हैं। अंकगणित में, केवल वे परतें जो दो अज्ञातों का गुणा करती हैं, अतिरिक्त लागत लेती हैं; पूरी तरह रैखिक परतें लगभग मुफ़्त पड़ती हैं।
एक निष्पक्ष तुलना
एक आपत्ति: शास्त्रीय सीमाएँ मानती हैं कि उत्तर एक ही बार, बाएँ से दाएँ, एक अलग आउटपुट टेप पर लिखा जाता है, जबकि कैटेलिटिक एल्गोरिद्म अपना उत्तर उधार की डिस्क में लिखते हैं। शोधपत्र इसका जवाब देता है। लेखक दिखाते हैं कि उनके एल्गोरिद्म आउटपुट टेप पर दो बार गुज़रकर उत्तर लिख सकते हैं, और साधारण एल्गोरिद्म के लिए दो बार गुज़रना एक बार से ज़्यादा मदद नहीं करता। इसलिए सीमाएँ फिर भी लागू होती हैं, और यह अंतर बना रहता है। वे यह भी साबित करते हैं कि उधार की डिस्क के साथ भी एक बार गुज़रना काफ़ी नहीं है: तब सॉर्टिंग उसी n² की दीवार से टकराती है।
लाभार्थियों की लंबी सूची
यही उपकरण बड़े पूर्णांकों और बहुपदों के गुणन, नेटवर्क में त्रिभुज गिनने और क्लीक (clique) खोजने, पथ और चक्र पहचानने, और वाइल्डकार्ड के साथ टेक्स्ट पैटर्न मिलाने के लिए तेज़ कैटेलिटिक एल्गोरिद्म देते हैं। उनके चलने का समय, छोटे गुणकों तक, उन सबसे अच्छे ज्ञात एल्गोरिद्म के बराबर है जिनके पास जितनी चाहें उतनी मेमोरी है। हर मामले में उधार की मेमोरी को ठीक वैसे ही लौटाना पड़ता है जैसी वह दी गई थी।