उनके उपयोग में सरणी और हैश मानचित्र निरंतर समय कैसे हैं?

Question

विशेष रूप से: हैश (या एक सरणी अनुक्रमणिका) दिया गया है, मशीन निरंतर समय में डेटा कैसे प्राप्त करती है?

ऐसा लगता है कि अन्य सभी मेमोरी स्थानों (या जो कुछ भी) से गुज़रने से गुजरने वाले स्थानों की संख्या बराबर होती है (इसलिए रैखिक समय)। एक सहकर्मी ने मुझे यह समझाने के लिए बहादुरी से कोशिश की है, लेकिन जब हम सर्किट में उतरे तो हार माननी पड़ी।

उदाहरण:

my_array = new array(:size => 20) 
my_array[20] = "foo" 
my_array[20] # "foo" 

स्थिति 20 में "foo" की पहुँच निरंतर क्योंकि हम जानते हैं जो बाल्टी "foo" में है हम कैसे जादुई रास्ते पर सभी दूसरों से गुजर बिना कि बाल्टी को मिला। ? ब्लॉक पर # 20 घर पर जाने के लिए आपको अभी भी अन्य 1 9 0 से गुज़रना होगा ...

Answer 1

हम कैसे जादुई रास्ते पर सभी दूसरों गुजर बिना कि बाल्टी के लिए मिला?

"हम" बाल्टी में "जाने" नहीं देते हैं। जिस तरह से रैम शारीरिक रूप से काम करता है वह एक चैनल पर बाल्टी की संख्या को प्रसारित करने जैसा है, जिस पर सभी बाल्टी सुनती हैं, और जिसकी संख्या बुलाई गई थी, वह आपको इसकी सामग्री भेज देगा।

सीपीयू में गणना होती है। सिद्धांत रूप में, सीपीयू सभी स्मृति स्थानों से समान "दूरी" है (अभ्यास में यह कैशिंग के कारण नहीं है, जो प्रदर्शन पर एक बड़ा प्रभाव डाल सकता है)।

यदि आप किरकिरा विवरण चाहते हैं, तो "What every programmer should know about memory" पढ़ें।

Answer 2

तब समझने के लिए कि आपको स्मृति को कैसे व्यवस्थित किया जाता है और एक्सेस किया जाता है। आपको address decoder कार्यों के तरीके को देखना पड़ सकता है। बात यह है कि, स्मृति में जो चाहते हैं उसे पाने के लिए आपको अन्य सभी पतों से गुजरना पड़ेगा। आप वास्तव में अपनी इच्छानुसार कूद सकते हैं। अन्यथा हमारे कंप्यूटर वास्तव में वास्तव में धीमी होगी।

Answer 3

एक ट्यूरिंग मशीन के विपरीत, जिसे क्रमशः स्मृति तक पहुंचना होगा, कंप्यूटर यादृच्छिक एक्सेस मेमोरी या रैम का उपयोग करते हैं, जिसका अर्थ है कि अगर उन्हें पता है कि सरणी कहां से शुरू होती है और वे जानते हैं कि वे सरणी के 20 वें तत्व तक पहुंचना चाहते हैं, तो वे पता है कि स्मृति का किस भाग को देखने के लिए।

यह एक सड़क को चलाने की तरह कम है और आपके अपार्टमेंट के लिए एक साझा मेलबॉक्स में सही मेल स्लॉट चुनना पसंद है।

Answer 4

2 बातें महत्वपूर्ण हैं:

1. my_array के बारे में जहां स्मृति कंप्यूटर में इस सरणी प्राप्त करने के लिए कूद करना होगा जानकारी नहीं है।
2. अनुक्रमणिका * आकार का प्रकार सरणी की शुरुआत से ऑफसेट हो जाता है।

1 + 2 = हे (1) जहां डाटा

Answer 5

पाया जा सकता है बिग ओ उस तरह काम नहीं करता। यह एक माप है कि कम्प्यूटेशनल संसाधनों का उपयोग एक विशेष एल्गोरिदम और फ़ंक्शन द्वारा किया जाता है। इसका उपयोग स्मृति की मात्रा को मापने के लिए नहीं है और यदि आप उस स्मृति को पार करने के बारे में बात कर रहे हैं, तो यह अभी भी एक स्थिर समय है। अगर मुझे किसी सरणी का दूसरा स्लॉट ढूंढना है तो यह एक पॉइंटर को ऑफसेट जोड़ने का मामला है। अब, अगर मेरे पास पेड़ की संरचना है और मैं एक विशेष नोड खोजना चाहता हूं तो अब आप ओ (लॉग एन) के बारे में बात कर रहे हैं क्योंकि इसे पहले पास पर नहीं मिला है। औसत पर यह नोड खोजने के लिए ओ (लॉग एन) लेता है।

Answer 6

चलो सी/सी ++ शर्तों में इसकी चर्चा करें; सी # सरणी के बारे में जानने के लिए कुछ अतिरिक्त सामान हैं लेकिन यह बिंदु के लिए वास्तव में प्रासंगिक नहीं है।

16-बिट पूर्णांक मूल्यों की एक सरणी को देखते हुए:

short[5] myArray = {1,2,3,4,5}; 

क्या वास्तव में हुआ है कि कंप्यूटर स्मृति में अंतरिक्ष के एक ब्लॉक आवंटित किया है। यह मेमोरी ब्लॉक उस सरणी के लिए आरक्षित है, बिल्कुल पूर्ण सरणी (हमारे मामले में 16 * 5 == 80 बिट्स == 10 बाइट्स) रखने के लिए आवश्यक आकार है, और यह संगत है। ये तथ्य givens हैं; यदि किसी भी समय या उनमें से कोई भी आपके पर्यावरण में किसी भी समय सत्य नहीं है, तो आमतौर पर एक्सेस वायलओशन के कारण आपके प्रोग्राम को क्रैश होने का जोखिम होता है।

तो, इस संरचना को देखते हुए, दृश्य myArray वास्तव में, दृश्यों के पीछे, स्मृति के ब्लॉक की शुरुआत का स्मृति पता है। यह भी, आसानी से, पहले तत्व की शुरुआत है। प्रत्येक अतिरिक्त तत्व क्रम में, पहले क्रम में स्मृति में रेखांकित किया गया है। स्मृति myArray के लिए आवंटित ब्लॉक इस प्रकार दिखाई देंगे:

00000000000000010000000000000010000000000000001100000000000001000000000000000101 
^    ^   ^   ^   ^
myArray([0]) myArray[1]  myArray[2]  myArray[3]  myArray[4] 

यह एक स्मृति पते का उपयोग और बाइट्स की एक निरंतर संख्या को पढ़ने के लिए एक निरंतर समय ऑपरेशन माना जाता है। उपर्युक्त आंकड़े के रूप में, यदि आप तीन चीजें जानते हैं तो आप प्रत्येक के लिए मेमोरी पता प्राप्त कर सकते हैं; मेमोरी ब्लॉक की शुरुआत, प्रत्येक तत्व का स्मृति आकार, और इच्छित तत्व की अनुक्रमणिका। इसलिए, जब आप अपने कोड में myArray[3] के लिए पूछना, उस अनुरोध को एक स्मृति पते में निम्नलिखित समीकरण द्वारा दिया जाता है: एक निरंतर समय गणना के साथ

myArray[3] == &myArray+sizeof(short)*3; 

इस प्रकार,, आप चौथे तत्व की स्मृति पता मिल गया है (सूचकांक 3), और एक और निरंतर समय के संचालन के साथ (या कम से कम माना जाता है; वास्तविक पहुंच जटिलता एक हार्डवेयर विवरण है और पर्याप्त तेज़ है कि आपको परवाह नहीं करनी चाहिए) आप उस स्मृति को पढ़ सकते हैं। यह है, यदि आपने कभी सोचा है, तो अधिकांश सी-शैली भाषाओं में संग्रहों की अनुक्रमणिका शून्य से क्यों शुरू होती है; सरणी के पहले तत्व सरणी के ही स्थान पर शुरू होता है, कोई ऑफसेट (sizeof (कुछ भी) * 0 == 0)

सी # में, वहाँ दो उल्लेखनीय मतभेद हैं। सी # सरणी में कुछ शीर्षलेख जानकारी होती है जो सीएलआर के उपयोग में होती है। शीर्ष लेख स्मृति ब्लॉक में पहले आता है, और इस शीर्ष लेख के आकार स्थिर है और जाना जाता है, इसलिए संबोधित कर रहे समीकरण सिर्फ एक मुख्य अंतर यह है:

myArray[3] == &myArray+headerSize+sizeof(short)*3; 

सी # आप सीधे अपने प्रबंधित में स्मृति को संदर्भित करने की अनुमति नहीं है पर्यावरण, लेकिन रनटाइम ही ढेर से मेमोरी एक्सेस करने के लिए ऐसा कुछ उपयोग करेगा।

दूसरी बात, जो सी/सी के सबसे जायके के लिए आम है ++ के साथ-साथ, कि कुछ प्रकार हमेशा "संदर्भ द्वारा" के साथ पेश कर रहे हैं। बनाने के लिए आपको new कीवर्ड का उपयोग करने के लिए कुछ भी संदर्भ प्रकार है (और कुछ ऑब्जेक्ट्स हैं, जैसे स्ट्रिंग्स, जो संदर्भ प्रकार भी हैं हालांकि वे कोड में मूल्य प्रकारों की तरह दिखते हैं)। एक संदर्भ प्रकार, जब तत्काल, स्मृति में रखा जाता है, स्थानांतरित नहीं होता है, और आमतौर पर प्रतिलिपि नहीं बनाई जाती है। इस ऑब्जेक्ट का प्रतिनिधित्व करने वाला कोई भी चर दृश्यों के पीछे, स्मृति में ऑब्जेक्ट का केवल स्मृति पता है। Arrays संदर्भ प्रकार हैं (याद रखें myArray सिर्फ एक स्मृति पता था)। संदर्भ प्रकारों की Arrays इन मेमोरी पतों के सरणी हैं, इसलिए किसी ऑब्जेक्ट को एक्सेस करना जो किसी सरणी में तत्व है, दो-चरणीय प्रक्रिया है; सबसे पहले आप सरणी में तत्व के स्मृति पते की गणना करते हैं, और उसे प्राप्त करते हैं।यह एक और स्मृति पता है, जो वास्तविक वस्तु का स्थान है (या कम से कम इसके परिवर्तनीय डेटा; स्मृति में कैसे मिश्रित प्रकार संरचित होते हैं, एक अन्य अन्य 'कीड़े) हो सकता है। यह अभी भी एक स्थिर समय ऑपरेशन है; एक के बजाय सिर्फ दो कदम।