रैम मॉडल क्या प्रेरित करता है?
ऐसा लगता है कि आज के अधिकांश एल्गोरिदम विश्लेषण निरंतर-समय यादृच्छिक अभिगम वाले मॉडल में किया जाता है, जैसे कि रैम मॉडल। मैं भौतिकी के बारे में ज्यादा नहीं जानता, लेकिन लोकप्रिय स्रोतों से मैंने सुना है कि प्रति सूचना संग्रहण और सूचना यात्रा की गति पर एक सीमा होनी चाहिए, इसलिए RAM भौतिक रूप से वास्तविक नहीं लगते हैं। आधुनिक कंप्यूटरों में ये सभी कैश स्तर होते हैं जो मैं कहता हूं कि यह बहुत ही रैम जैसा नहीं है। तो रैम में सैद्धांतिक एल्गोरिदम क्यों सेट किया जाना चाहिए?
जवाब
वॉनब्रांड की तुलना में मुझे इस पर एक अलग ले लेने दें। आपके द्वारा कहा गया सब कुछ सच है: रैम मॉडल कई कारणों से यथार्थवादी नहीं है, और जबकि इसके विभिन्न पहलुओं का बचाव करना संभव है, इस तरह की रक्षा वास्तव में मामले के दिल में नहीं आती है।
मामले का दिल - और आपके प्रश्न का उत्तर - यह है कि रैम मॉडल हमारे पास सबसे अच्छी चीज है। स्वीकार किए जाते हैं अन्य मॉडलों की तुलना में, यह वास्तविक जीवन की गणना के लिए अधिक सटीक मॉडल है। विशेष रूप से, हमने रैम मॉडल को अपनाया कारण मुख्य रूप से ट्यूरिंग मशीनों के लिए एक प्रतिक्रिया थी, क्योंकि हमने पाया कि ट्यूरिंग मशीनों के उपयोग से समय जटिलता के मामले में समस्याओं को हल करना मुश्किल हो जाता है। रैम मॉडल स्पष्ट रूप से इस चकाचौंध मुद्दे को हल करता है, और इस तरह इसे स्वीकार किया गया है, भले ही यह एकदम सही है।
एक शास्त्रीय उदाहरण जो ट्यूरिंग मशीनों के साथ चमकता मुद्दा दिखाता है, स्ट्रिंग समानता की समस्या है: दिया गया इनपुट
$$ w_1 \# w_2$$
कहाँ पे $w_1, w_2$ बाइनरी सीक्वेंस और हैं $\#$ एक विभाजक है, यह निर्धारित करता है कि क्या $w_1 = w_2$। यह दिखाया जा सकता है कि समानता समस्या के लिए कोई भी ट्यूरिंग मशीन लेता है$O(n^2)$समय। यह असुविधाजनक है, क्योंकि ट्यूरिंग मशीनें वह हैं जो हर कोई गणना के सार्वभौमिक मॉडल के रूप में सोचता है - फिर भी कोई सॉफ्टवेयर इंजीनियर या एल्गोरिदम शोधकर्ता का मानना है कि स्ट्रिंग समानता वास्तव में लेता है$O(n^2)$समय। तो क्या देता है? स्ट्रिंग की समानता रैखिक होनी चाहिए, इसलिए हम एक नया मॉडल का आविष्कार करते हैं जहां यह है, और अभी उपलब्ध सबसे अच्छा समाधान शब्द है रैम मशीनें।
शायद भविष्य में किसी दिन हम एक बेहतर मॉडल के साथ आएंगे - एक जो सरल, वैचारिक रूप से स्पष्ट है, और वास्तविक जीवन कम्प्यूटेशनल जटिलता को मॉडल करने की क्षमता में रैम में सुधार करता है। अभी के लिए, हम केवल वही कर सकते हैं जो हमारे पास है।
पहले, खुरदरे, सन्निकटन के रूप में, आप स्मृति में किसी शब्द तक पहुँचने के लिए समय निकाल सकते हैं, पूर्ववर्ती पहुँच से स्वतंत्र। यानी, रैम मॉडल।
आप सही कह रहे हैं, आज की मशीनें काफी अन-रैम-जैसे हैं, यह डेटा एक्सेस को व्यवस्थित करने के लिए ऑफ हैंड (समान रूप से) का भुगतान करती है ताकि मैनहैंड से पहले एक (शॉर्ट!) मेमोरी सेगमेंट से बाहर जानकारी के अंतिम बिट को अनुक्रमिक किया जा सके। अगला। लेकिन आपके पास ऐसा करने के लिए शायद ही कोई रास्ता है, आपकी मेमोरी एक्सेस अनिवार्य रूप से यादृच्छिक है और मॉडल सच्चाई से बहुत दूर नहीं है। प्लस आज की मशीनों में एक से अधिक सीपीयू हैं, मॉडल में सिर्फ एक है। और फिर वेक्टर प्रसंस्करण होता है (डेटा के वेक्टर पर एक ही ऑपरेशन कर रहा है, एक-एक करके नहीं) "मल्टीमीडिया निर्देश" के रूप में (और प्रसंस्करण के लिए ग्राफिक्स कार्ड का उपयोग करके भी)।
खोंग की द्विआधारी खोज के लिए उदाहरणों के लिए थोड़ी चर्चा की जाती है, जो कि कैश के लिए एक रोग संबंधी मामला है । जैसा कि आप देखते हैं, अधिक यथार्थवादी मेमोरी एक्सेस टाइम मॉडल के तहत सरल, अच्छी तरह से समझे जाने वाले एल्गोरिदम का विश्लेषण करना चुनौतीपूर्ण है।
रैम मॉडल एल्गोरिदम के एसिम्प्टोटिक विश्लेषण से प्रेरित है जिसे एकल-थ्रेडेड इन-मेमोरी कंप्यूटर्स के रूप में डिज़ाइन किया गया है।
विशिष्ट निर्देश सेट, कैश और व्हाट्सएप के लिए प्रदर्शन का अनुकूलन एक बात है। समस्या आकार के विकास के लिए दूसरी चीज तैयार की जानी है। यह अनुमान लगाने के लिए कि आपका इन-मेमोरी एल्गोरिथ्म कितना अच्छा है, आप शायद छोटे कारकों को अनदेखा करना चाहते हैं और बड़े पर ध्यान केंद्रित करना चाहते हैं$\mathcal{O}$संकेतन। बड़े$\mathcal{O}$ आपके लिए सब कुछ ऑप्टिमाइज़ करने वाला नहीं है, लेकिन कम से कम यह आपको बता सकता है कि आपका समाधान अच्छी तरह से (या कि आपको कुछ अलग करने की कोशिश करनी चाहिए)।
रैम छोटे निश्चित अनुदेश सेट को मानता है, जहां प्रत्येक ऑपरेशन में काम करता है $\mathcal{O}(1)$। ध्यान दें कि यह एक अच्छा मॉडल है अगर हम केवल विषम विकास के बारे में परवाह करते हैं:
आधुनिक सीपीयू का निर्देश सेट छोटा नहीं है, लेकिन हम दिखावा कर सकते हैं कि यह वास्तव में है। वे अतिरिक्त ऑप-कोड बड़े में अंतर नहीं करते हैं$\mathcal{O}$ संकेतन।
सीपीयू के निर्देश हो सकते हैं जिनका रनटाइम इनपुट पर निर्भर करता है। फिर से, हम उन्हें अनदेखा कर सकते हैं, क्योंकि हम बड़े को प्रभावित किए बिना सरल निर्देशों का उपयोग करके उन्हें मॉडल कर सकते हैं$\mathcal{O}$जटिलता। कैशे के स्तर के लिए समान है: उनका प्रदर्शन अभी भी कुछ छोटे स्थिरांक से घिरा हुआ है, इस प्रकार काम करते हैं$\mathcal{O}(1)$ परिभाषा से।
यदि आप इसे बढ़ाते रहते हैं, तो आप निरंतर समय में मेमोरी एक्सेस नहीं कर सकते। सौभाग्य से, सामान्य ज्ञान के लिए यह कभी आवश्यक नहीं है। कोई भी पूरे इंटरनेट को एक अकेले एकल-थ्रेडेड मशीन की गैर-निरंतर स्मृति में अनुक्रमित नहीं कर रहा है।