मुझे आश्चर्य है कि यहां किसी ने कभी भी skip list का उपयोग किया है। ऐसा लगता है कि एक संतुलित बाइनरी पेड़ के रूप में लगभग समान फायदे हैं, लेकिन इसे लागू करने के लिए आसान है। यदि आपके पास है, तो क्या आपने अपना खुद का लिखा है, या प्री-लिखित लाइब्रेरी का उपयोग किया है (और यदि हां, तो इसका नाम क्या था)?सूची छोड़ें - कभी उनका इस्तेमाल किया?
साल पहले मैंने एक संभाव्य एल्गोरिदम कक्षा के लिए अपना खुद का कार्यान्वित किया था। मुझे किसी पुस्तकालय कार्यान्वयन से अवगत नहीं है, लेकिन यह एक लंबा समय रहा है। इसे लागू करना बहुत आसान है। जैसा कि मुझे याद है कि उनके पास बड़े डेटा सेट के लिए कुछ वाकई अच्छी संपत्तियां थीं और पुनर्विक्रय की कुछ समस्याओं से परहेज किया था। मुझे लगता है कि कार्यान्वयन सामान्य रूप से द्विआधारी प्रयासों से भी आसान है।
http://www.ddj.us/cpp/184403579?pgno=1
वहाँ भी एक चल रहा प्रदर्शन के साथ एक एप्लेट है: वहाँ एक अच्छा चर्चा और कुछ नमूना C++ यहाँ कोड है। प्यारा 90 जावा यहाँ चमक:
http://www.geocities.com/siliconvalley/network/1854/skiplist.html
मैं इसे डीडीजे लेख के संदर्भ में स्वीकार कर रहा हूं। यहां तक कि स्टीव के लिए माफ़ी, अगर मैं कर सकता हूं तो मैं तीनों उत्तरों को स्वीकार करूंगा। –
मैंने एक संस्करण लागू किया जिसे मैंने कुछ साल पहले नियम इंजन के लिए रिवर्स छोड़ने की सूची कहा था। वही, लेकिन संदर्भ लिंक पिछले तत्व से पीछे की ओर चलाते हैं।
ऐसा इसलिए है क्योंकि यह क्रमबद्ध वस्तुओं को सम्मिलित करने के लिए तेज़ था जो संग्रह के पीछे की ओर की ओर सबसे अधिक संभावना थी।
यह सी # में लिखा गया था और सफलतापूर्वक काम करने के लिए कुछ पुनरावृत्तियों को लिया।
क्या आप इस प्रकार की तुलना को उलटा नहीं कर सकते, और एक ही परिणाम प्राप्त करने के लिए मानक स्कीप्लिस्ट का उपयोग नहीं कर सकते? –
असल में, मेरी परियोजनाओं में से एक के लिए मैं अपना पूरा एसटीएल लागू कर रहा हूं। और मैंने अपने std::map को लागू करने के लिए एक स्कीप्लिस्ट का उपयोग किया। कारण मैं इसके साथ गया क्योंकि यह एक साधारण एल्गोरिदम है जो एक संतुलित पेड़ के प्रदर्शन के बहुत करीब है लेकिन बहुत सरल पुनरावृत्ति क्षमताओं है।
इसके अलावा, QT4's QMap एक स्कीप्लिस्ट भी था जो मेरे std::map में इसका उपयोग करने के लिए मूल प्रेरणा थी।
इवान, क्या आपने अपना स्कीप्लिस्ट कोड कहीं भी उपलब्ध कराया है? धन्यवाद – dkantowitz
अभी तक काफी नहीं है, लेकिन चीजें लगभग उस बिंदु पर हैं जहां मैं अपना एसटीएल जारी कर सकता हूं। लेकिन वहाँ बहुत सारे उदाहरण हैं सूची सूची कार्यान्वयन वहाँ। –
हां, बहुत सारे स्किप सूची कोड उपलब्ध हैं। मैं कुछ ऐसा ढूंढ रहा था जो विशेष रूप से std :: map <> इंटरफेस का अनुपालन करता है। क्यूमैप काफी करीब दिखता है, इसलिए मैं इसे आज़मा दूंगा। धन्यवाद – dkantowitz
जावा 1.6 (जावा SE 6) संग्रह ढांचे के लिए ConcurrentSkipListSet और ConcurrentSkipListMap की शुरुआत की। तो, मैं अनुमान लगाता हूं कि वहां कोई भी वास्तव में उनका उपयोग कर रहा है।
स्कीप्लिस्ट एक बहुप्रचारित स्थिति में ताले के लिए बहुत कम विवाद प्रदान करते हैं, और (संभाव्य रूप से) पेड़ के समान प्रदर्शन विशेषताओं का प्रदर्शन करते हैं।
the original paper [पीडीएफ] देखें विलियम प्यूघ द्वारा
मेरे समझ है कि वे इतना द्विआधारी पेड़ (जैसे लाल-काले पेड़) के रूप में वे बी पेड़ लिए कर रहे हैं के लिए एक उपयोगी विकल्प नहीं कर रहे हैं है डेटाबेस उपयोग के लिए, ताकि आप प्रदर्शन की विशेषताओं के लिए बेस-2 लॉग के बजाय स्तरों के # को कम से कम न्यूनतम और डब्ल्यू/बेस-के लॉग को सौंप सकें। संभाव्य स्किप-सूचियों के लिए एल्गोरिदम (आईएमएचओ) संबंधित बी-पेड़ एल्गोरिदम से सही प्राप्त करना आसान है। इसके अलावा लॉक-फ्री स्किप सूचियों पर कुछ साहित्य भी हैं। मैंने कुछ महीने पहले उनका उपयोग करने पर ध्यान दिया लेकिन फिर HDF5 लाइब्रेरी की खोज करने के प्रयास को त्याग दिया।इस विषय पर
साहित्य: विधेयक प्यूघ द्वारा
पत्रों:
गैर शैक्षिक पेपर/ट्यूटोरियल:
जाएं सूचियाँ लागू करने के लिए आसान है
प्रत्येक स्किप सूची नोड में आगे पॉइंटर्स हैं जो छोड़ने की सूची के विभिन्न स्तरों के वर्तमान-> अगले() कनेक्शन का प्रतिनिधित्व करते हैं। आम तौर पर यह स्तर अधिकतम एलएन (एन) पर बंधे होते हैं। तो यदि एन = 1 मिलियन स्तर 13 है। वहां बहुत अधिक पॉइंटर्स होंगे और जावा में इसका मतलब संदर्भ डेटा प्रकारों को लागू करने के लिए पॉइंटर्स की संख्या को जोड़ना होगा। जहां एक संतुलित खोज पेड़ कम है और यह एक ही रनटाइम देता है !!
SkipList Vs Splay Tree Vs Hash शब्दकोश के लिए प्रोफाइल के रूप में एक लॉक स्ट्रिप किए गए हैशटेबल के परिणामस्वरूप 0.010 एमएस के तहत परिणाम देगा, जहां एक स्प्ले पेड़ ~ 1 एमएस देता है और सूची ~ 720ms छोड़ देता है।
यह भी देखें http://stackoverflow.com/questions/256511/skip-list-vs-binary-tree –