कैसे कैश Oblivious त्वरित प्रकार है?

Question

Burst sort कागज लेखक में दावा है कि जल्दी तरह बहुत ही कुशल कैश एल्गोरिथ्म छँटाई नहीं है। लेखक

उल्लेख किया है हालांकि, quicksort का नुकसान से कुछ अभी भी present.Each चरित्र का निरीक्षण किया कई बार कर रहे हैं, जब तक यह एक धुरी के बराबर partition.Each स्ट्रिंग में है हर बार में एक चरित्र को फिर से पहुंचा जा सकता है यह का निरीक्षण किया जाता है, और पहले विभाजन के बाद इन पहुंच प्रभावी ढंग से यादृच्छिक हैं। तारों के एक बड़े सेट के लिए, कैश मिस की दर अधिक होने की संभावना है।

मैं भी ppt जो त्वरित प्रकार कहते हैं और मर्ज तरह कैश बेखबर एल्गोरिथ्म लेकिन विकिपीडिया और few paper का दावा है कि जल्दी तरह बहुत कैश कुशल है पाया।

मैं जिन मामलों में त्वरित तरह कैश याद आती है अलग अनिवार्य याद आती से पूर्णांक के लिए किसी को भी data.Can मिल विस्तार से त्वरित तरह कैश याद आती है समझाने को समझने में सक्षम नहीं हूँ?

Answer 1

पारित होने आप उद्धृत मुख्य रूप से मुद्दों के बारे में बात कर रही है जब तार छँटाई। यदि क्विकसॉर्ट के दौरान तारों की एक सरणी को सरणी के रूप में एक सरणी के रूप में संग्रहीत किया जाता है (जो मूल रूप से ऐसा करने का एकमात्र आसान तरीका है), तो क्विकॉर्ट के पहले पास के बाद यह संभव है कि सरणी में आस-पास की स्थितियों में संग्रहीत पॉइंटर्स स्मृति को इंगित करें वे स्थान जो बहुत दूर हैं, भले ही स्ट्रिंग की मूल सरणी लगातार स्मृति में आवंटित की गई हो। ऐसा लगता है कि सॉर्टिंग तारों को एक विशेष समस्या के रूप में माना जा सकता है और इसके लिए विशेष एल्गोरिदम अधिक कैश कुशल हो सकते हैं।

यदि आप इसके बजाय, कहते हैं, पूर्णांक की सरणी को सॉर्ट कर रहे हैं, तो आप वास्तव में क्विकॉर्ट के दौरान सरणी में डेटा के चारों ओर तुलना और तुलना कर रहे हैं, और इसलिए जब आप सरणी में आस-पास के स्थानों तक पहुंचते हैं तो आपको कैश लाभ मिलेंगे। इस मामले में, मेरी समझ विक्टिपीडिया और अन्य जगहों पर जो कुछ भी मिली है, वैसे ही, क्विक्सोर्ट काफी कैश कुशल है। असल में ऐसा इसलिए होता है क्योंकि क्विकॉर्ट के प्रत्येक पास सरणी के अपने हिस्से को अत्यधिक स्थानीय फैशन में संसाधित करता है।