वीएलआईएस

Question

फिल बैगवेल का उपयोग करके हैश टेबल, 2002 paper on the VList data structure में इंगित करता है कि आप एक सतत हैश तालिका को लागू करने के लिए एक वीएलआईस्ट का उपयोग कर सकते हैं। हालांकि, उनके काम के बारे में उनकी व्याख्या में बहुत विस्तार शामिल नहीं था, और मुझे यह समझ में नहीं आया। क्या कोई मुझे एक और विस्तृत स्पष्टीकरण, या यहां तक ​​कि उदाहरण भी दे सकता है?

आगे, ऐसा लगता है कि मैं यह डेटा संरचना देख सकता हूं, जबकि यह हैशटेबल के रूप में एक ही बड़ी-जटिलता हो सकती है, यह धीमी हो जाएगी क्योंकि यह अतिरिक्त लुकअप करता है। क्या कोई भी कैश व्यवहार सहित, कितना धीमा, इसका विस्तृत विश्लेषण करने की परवाह करता है? टकराव या कई के मामले में दो परिवर्तनों के बीच प्रदर्शन संबंध कैसे करता है?

Answer 1

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

Answer 2

एचआरएम प्रश्न में पेपर द्वारा प्रस्तावित डेटा संरचनाओं के साथ कई समस्याएं प्रतीत होती हैं।

कफ के बाहर, प्रस्तावित समय गारंटी के पास कुछ भी प्राप्त करने के लिए पहले उल्लेख किए गए बेवकूफ vlists को अद्वितीय संदर्भों की आवश्यकता होती है। आप पूंछ साझा करने के लिए अधिकांश भाग की क्षमता खो देते हैं। आप छोटे नोड्स को सूची के पीछे की ओर साझा कर सकते हैं, लेकिन आप उस समय के सबसे बड़े vlist नोड को डुप्लिकेट करने के लिए हवादार कर सकते हैं जब आप vlist के cdr पर कुछ ऐसा करते हैं जो अभी भी सक्रिय है। यह लागत पूरी सूची की प्रतिलिपि बनाने की लागत के समान है।

बाद में वर्णित 2 डी संशोधनों के साथ यह फिर से स्थिर हो जाता है, लेकिन यह एक बहुत बड़ा स्थिर है, क्योंकि आप कम से कम पृष्ठों की सूची (या बदतर, एक सूची) की सूची को कॉपी करते हैं और आपकी सूची में पहला पृष्ठ ।

वहां पर कार्यात्मक हैश सूची सामग्री मुझे ईमानदार होने के लिए बहुत समझ में नहीं आती। यह सिर्फ एक संक्षिप्त अस्पष्ट था जिसे किसी अन्य असंबंधित पेपर पर बोल्ट किया गया था, वास्तव में यह समझने के लिए कि वास्तव में यह कितना व्यावहारिक है।