कहें कि हमारे पास एक अनुरक्षित सरणी और लिंक की गई सूची है। डेटा संरचनाओं दोनों के लिए तत्व खोजते समय सबसे खराब मामला ओ (एन) होगा, लेकिन मेरा प्रश्न है:क्षेत्र के संदर्भ में Arrays बनाम लिंक्ड सूचियां
क्या कैश के भीतर स्थानिक इलाके के उपयोग के कारण सरणी अभी भी तेज हो जाएगी, या कैश शाखा इलाके का उपयोग करता है जो लिंक्ड सूचियों को किसी सरणी के जितना तेज हो सकता है?
एक सरणी के लिए मेरी समझ यह है कि यदि किसी तत्व को एक्सेस किया जाता है, तो स्मृति की उस ब्लॉक और आसपास के कई ब्लॉक को कैश में लाया जाता है ताकि बहुत तेज मेमोरी एक्सेस हो सके।
एक लिंक्ड सूची के लिए मेरी समझ यह है कि सूची को पार करने के लिए जो रास्ता लिया जाएगा, वह अनुमान लगाया जा सकता है, तो कैश इसका फायदा उठाएगा और फिर भी स्मृति के उपयुक्त ब्लॉक स्टोर करेगा, भले ही सूची के नोड्स दूर हो सकते हैं ढेर के भीतर।
इस "शाखा इलाके" के बारे में आप क्या बात करते हैं? मुख्य स्मृति की विलंबता के आसपास कैसे कैश हो सकता है? लिंक किए गए सूची नोड्स के साथ कैश क्या करता है, कृपया वर्णन करें। – delnan
@ डेलनान आप यहां शाखा इलाके के बारे में पढ़ सकते हैं: http://en.wikipedia.org/wiki/Locality_of_reference मुझे आपके दूसरे प्रश्न का उत्तर नहीं पता है। मैंने समझाया कि मुझे लगता है कि कैश मेरे प्रश्न के अंत में नोड्स के साथ क्या कर सकता है। – Kacy
शाखा इलाके का विवरण एक शाखा निर्देश (इसलिए नाम) के लक्ष्य जैसे विकल्पों के एक निश्चित छोटे सेट के बारे में प्रतीत होता है। इसके विपरीत, एक लिंक्ड सूची का अगला नोड * कहीं भी * हो सकता है। मेरे दूसरे प्रश्न के लिए: समस्या कैश फिक्स मुख्य रूप से सीमित बैंडविड्थ सीमित नहीं है लेकिन सीमित विलंबता है। कैश में एक बड़े महाद्वीपीय ब्लॉक को एक बार में लोड करना (जैसा कि स्थानिक इलाके/सरणी के लिए होता है) एक सुधार है क्योंकि कैश को केवल एक बार विलंबता लागत का भुगतान करना पड़ता है। तो मेरा सवाल यह है कि कैश एक विलंबित सूची के एन नोड्स को विलंबता लागत के भुगतान के बिना कैसे लोड कर सकता है? – delnan