एक बीएसटी में एक तत्व (ट्रैवर्स) ढूंढना किस तरह से एक सरणी के भीतर रैखिक रूप से स्कैन करने से धीमा होगा?

माना जाता है कि इसका उत्तर कैशिंग से संबंधित है। क्या कोई समझा सकता है कि इसका वास्तव में क्या अर्थ है और यह सत्य क्यों है?

BST के साथ कैशिंग करने के बजाय किसी सरणी का उपयोग करके आप वास्तव में "कैश-यह" कैसे करते हैं?

धन्यवाद

1
Brijendar Bakchodia 4 सितंबर 2018, 03:18

2 जवाब

मेरा अनुमान है कि बीएसटी का उपयोग करने से आपको कोई फायदा नहीं होता है, भले ही आप डेटा कैशिंग कर रहे हों (जिसका अर्थ है कि किसी प्रकार का इलाका है, उदाहरण के लिए आप बाद में उसी तत्व तक पहुंच सकते हैं), सम्मिलित करें ऑपरेशन और ऑपरेशन ढूंढें हमेशा लागत O(h) जहां h पेड़ की ऊंचाई है। सबसे खराब स्थिति में, यहां तक ​​कि O(n) भी।

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

0
Plutone11011 5 सितंबर 2018, 13:21

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

बीएसटी में आप अनुक्रमिक पहुंच नहीं करते हैं। सबसे खराब स्थिति में आपका BST सन्निहित मेमोरी में नहीं रहता है, लेकिन प्रत्येक नोड मेमोरी में किसी न किसी स्थान पर होता है। आपका प्रीफ़ेचर इसकी भविष्यवाणी नहीं कर सकता। तत्कालीन सीपीयू को प्रत्येक तत्व को स्मृति से प्राप्त करने की प्रतीक्षा करनी पड़ती है।

ए हालांकि प्रीफेचर्स के बिना कैश लाइन के संबंध में है। X86_64 पर कैश लाइन 64 बाइट लंबी होती है। प्रत्येक पूर्णांक या तो 4 या 8 बाइट है, इसलिए आप प्रति कैश लाइन 16 या 8 सरणी प्रविष्टियों को स्कैन कर सकते हैं। मेमोरी लोकेशन तक पहली पहुंच पूरी लाइन प्राप्त करती है, इसलिए आप केवल 8 तुलनाओं के लिए मेमोरी एक्सेस का भुगतान करते हैं। बीएसटी के लिए ऊपर जैसा तर्क लागू होता है। नोड मेमोरी संभवतः एक ही कैश लाइन पर नहीं है इसलिए प्रत्येक तुलना के लिए मेमोरी एक्सेस करना होगा।

संक्षेप में: ए) मेमोरी एक्सेस तुलना की तुलना में काफी अधिक समय लेता है; बी) यदि किसी सरणी या बीएसटी के माध्यम से खोजना तेज है तो वस्तुओं की मात्रा पर निर्भर करता है।

0
Philipp 5 सितंबर 2018, 15:08