छोड़ें सूची बनाम बाइनरी ट्री

Question

मैं हाल ही में डेटा संरचना में आया था जिसे Skip list के नाम से जाना जाता है। ऐसा लगता है कि एक बाइनरी खोज पेड़ के लिए बहुत ही समान व्यवहार है ... मेरा सवाल है - आप कभी भी बाइनरी खोज पेड़ पर एक स्किप सूची का उपयोग क्यों करना चाहेंगे?

Answer 1

छोड़ें सूचियां समवर्ती पहुंच/संशोधन के लिए अधिक सक्षम हैं। हर्ब सटर ने समवर्ती वातावरण में डेटा संरचना के बारे में article लिखा था। इसमें अधिक जानकारी है।

बाइनरी खोज पेड़ का सबसे अधिक उपयोग किया जाने वाला कार्यान्वयन red-black tree है। जब पेड़ संशोधित होता है तो समवर्ती समस्याएं अक्सर इसे पुनर्व्यवस्थित करने की आवश्यकता होती है। रीबैलेंस ऑपरेशन पेड़ के बड़े हिस्सों को प्रभावित कर सकता है, जिसके लिए पेड़ नोड्स पर कई म्यूटेक्स लॉक की आवश्यकता होगी। एक स्किप सूची में नोड डालने से कहीं अधिक स्थानीयकृत होता है, केवल प्रभावित नोड से सीधे जुड़े नोड्स को लॉक करने की आवश्यकता होती है। जॉन Harrops से

---

अद्यतन टिप्पणी

मैं फ्रेजर और हैरिस की नवीनतम कागज Concurrent programming without locks पढ़ें। यदि आप लॉक-फ्री डेटा संरचनाओं में रूचि रखते हैं तो वास्तव में अच्छी चीजें। पेपर Transactional Memory पर केंद्रित है और एक सैद्धांतिक ऑपरेशन मल्टीवर्ड-तुलना-और-स्वैप एमसीएएस पर केंद्रित है। इन दोनों को सॉफ़्टवेयर में अनुकरण किया गया है क्योंकि कोई हार्डवेयर अभी तक उनका समर्थन नहीं करता है। मैं काफी प्रभावित हूं कि वे सॉफ्टवेयर में एमसीएएस बनाने में सक्षम थे।

मुझे लेनदेन संबंधी स्मृति सामग्री विशेष रूप से आकर्षक नहीं मिली क्योंकि इसे कचरा कलेक्टर की आवश्यकता होती है। इसके अलावा software transactional memory प्रदर्शन समस्याओं से ग्रस्त है। हालांकि, अगर हार्डवेयर लेनदेन की याददाश्त सामान्य हो जाती है तो मैं बहुत उत्साहित हूं। अंत में यह अभी भी शोध है और किसी अन्य दशक या उससे भी अधिक के लिए उत्पादन कोड के लिए उपयोग नहीं किया जाएगा।

धारा 8.2 में वे कई समवर्ती वृक्ष कार्यान्वयन के प्रदर्शन की तुलना करते हैं। मैं उनके निष्कर्षों का सारांश दूंगा। पीडीएफ डाउनलोड करना इसके लायक है क्योंकि इसमें पेज 50, 53 और 54 पर कुछ बहुत ही जानकारीपूर्ण ग्राफ हैं।

• लॉकिंग स्किप सूचियां बहुत तेज हैं। वे समवर्ती पहुंच की संख्या के साथ अविश्वसनीय रूप से अच्छी तरह से स्केल करते हैं। यही कारण है कि स्किप सूचियों को विशेष बनाता है, अन्य लॉक आधारित डेटा स्ट्रक्चर दबाव में क्रोक करते हैं।
• लॉक-फ्री स्किप सूचियां स्किप सूचियों को लॉक करने से लगातार तेज हैं लेकिन केवल मुश्किल से।
• लेनदेन संबंधी स्किप सूचियां लॉकिंग और गैर-लॉकिंग संस्करणों की तुलना में लगातार 2-3 गुना धीमी हैं।
• रेड-ब्लैक पेड़ लॉकिंग समवर्ती पहुंच के तहत क्रोक। उनका प्रदर्शन प्रत्येक नए समवर्ती उपयोगकर्ता के साथ रैखिक रूप से घटता है। दो ज्ञात लॉकिंग लाल-काले पेड़ कार्यान्वयनों में से एक के पास पेड़ के पुनर्वसन के दौरान अनिवार्य रूप से वैश्विक ताला है। दूसरा फैंसी (और जटिल) लॉक एस्केलेशन का उपयोग करता है लेकिन फिर भी वैश्विक लॉक संस्करण को निष्पादित करने में महत्वपूर्ण नहीं है।
• लॉक-फ्री लाल-काले पेड़ मौजूद नहीं है (अब सत्य नहीं है, अपडेट देखें)।
• लेनदेन लाल-काले पेड़ लेनदेन संबंधी स्किप-सूचियों के साथ तुलनीय हैं। यह बहुत ही आश्चर्यजनक और बहुत ही आशाजनक था। लेनदेन संबंधी स्मृति, हालांकि लिखने के लिए कहीं अधिक धीमी है। यह त्वरित खोज के रूप में आसान हो सकता है और गैर-समवर्ती संस्करण पर प्रतिस्थापित हो सकता है। Lock-Free Red-Black Trees Using CAS:

---

अद्यतन
यहाँ ताला मुक्त पेड़ों के बारे में कागज है।
मैंने इसे गहराई से नहीं देखा है, लेकिन सतह पर यह ठोस लगता है।

Answer 2

Wikipedia लेख आपको उद्धृत से:

Θ (एन) के संचालन, जो हमें (जैसे पूरी सूची मुद्रण के रूप में) का अवसर प्रदान आरोही क्रम में प्रत्येक नोड यात्रा करने के लिए मजबूर एक के पीछे-प्रदर्शन करने के लिए स्किप-सूची की स्तर संरचना की इष्टतम तरीके से स्केप सूची को लाने के लिए, (सूची एन) खोज समय को छोड़कर। [...] एक को छोड़ सूची, जिस पर हम नहीं हाल ही में प्रदर्शन किया [किसी भी तरह के] Θ (एन) के संचालन है, ही निरपेक्ष बुरी से बुरी हालत प्रदर्शन की गारंटी देता है और अधिक पारंपरिक संतुलित पेड़ डेटा के रूप में प्रदान नहीं करता है संरचनाओं, हमेशा होता है, क्योंकि यह संभव है (हालांकि बहुत कम संभावना रखता है) कि सिक्का flips इस्तेमाल किया छोड़ सूची का निर्माण करने के लिए एक बुरी तरह से संतुलित संरचना

संपादित का उत्पादन करेगा: तो यह एक व्यापार बंद है : छोड़ें सूची जोखिम पर कम स्मृति का उपयोग करें वाई एक असंतुलित पेड़ में गिरावट हो सकती है।

Answer 3

इसके अलावा, दिए गए उत्तरों के अलावा (एक संतुलित पेड़ के तुलनीय प्रदर्शन के साथ संयुक्त कार्यान्वयन में आसानी)। मुझे लगता है कि इन-ऑर्डर ट्रैवर्सल (आगे और पीछे की ओर) को कार्यान्वित करना बहुत आसान है क्योंकि एक स्किप-सूची प्रभावी रूप से इसके क्रियान्वयन के अंदर एक लिंक्ड सूची है।

Answer 4

प्रैक्टिस में मैंने पाया है कि मेरी परियोजनाओं पर बी-पेड़ प्रदर्शन स्किप-सूचियों से बेहतर साबित हुआ है। सूची छोड़ें समझने में आसान लगते हैं लेकिन बी-पेड़ को लागू करना नहीं है जो हार्ड है।

मुझे पता है कि एक लाभ यह है कि कुछ चालाक लोगों ने काम किया है कि लॉक-फ्री समवर्ती स्किप सूची को कैसे कार्यान्वित किया जाए जो केवल परमाणु संचालन का उपयोग करता है। उदाहरण के लिए, जावा 6 में ConcurrentSkipListMap क्लास है, और यदि आप पागल हैं तो आप स्रोत कोड को पढ़ सकते हैं।

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

Answer 5

सूचियों सूचियों का उपयोग कर लागू किया गया है।

सिंगल और दोगुनी लिंक्ड सूचियों के लिए लॉक फ्री समाधान मौजूद हैं - लेकिन कोई लॉक फ्री समाधान नहीं है जो सीधे किसी भी ओ (लॉग इन) डेटा संरचना के लिए केवल सीएएस का उपयोग कर रहा है।

हालांकि आप स्किप सूचियां बनाने के लिए सीएएस आधारित सूचियों का उपयोग कर सकते हैं।

(ध्यान दें कि सीएएस का उपयोग करके बनाई गई एमसीएएस, मनमाने ढंग से डेटा संरचनाओं की अनुमति देता है और एमसीएएस का उपयोग करके अवधारणा लाल-काले पेड़ बनाया गया है)।

तो, वे कर रहे हैं अजीब के रूप में, वे बाहर बारी बहुत उपयोगी :-) होने की

Answer 6

जाएं सूचियाँ अलग करना ताला का लाभ है। लेकिन, रनटाइम समय इस बात पर निर्भर करता है कि एक नए नोड का स्तर कैसे तय किया जाता है। आमतौर पर यह रैंडम() का उपयोग करके किया जाता है। 56000 शब्दों के शब्दकोश पर, स्किप सूची में एक स्प्ले पेड़ से अधिक समय लगा और पेड़ ने हैश टेबल से अधिक समय लिया। पहले दो हैश टेबल के रनटाइम से मेल नहीं खा सके। इसके अलावा, हैश तालिका की सरणी को एक समवर्ती तरीके से भी बंद कर दिया जा सकता है।

छोड़ें सूची और इसी तरह की आदेशित सूचियों का उपयोग तब किया जाता है जब संदर्भ की स्थानीयता की आवश्यकता होती है। पूर्व में: आवेदन में किसी तारीख से पहले और उससे पहले उड़ानें ढूंढना।

एक अनौपचारिक बाइनरी खोज splay पेड़ बहुत अच्छा और अधिक बार उपयोग किया जाता है।

Skip List Vs Splay Tree Vs Hash Table Runtime on dictionary find op

Answer 7

सबसे पहले, आप काफी एक है कि आप बुरी से बुरी हालत की गारंटी देता है देता है के साथ एक यादृच्छिक डेटा संरचना तुलना नहीं कर सकते।

एक स्किप सूची डीन और जोन्स के "Exploring the Duality Between Skip Lists and Binary Search Trees" में अधिक विस्तार से समझाए गए तरीके से यादृच्छिक रूप से संतुलित बाइनरी खोज पेड़ (आरबीएसटी) के बराबर है।

दूसरी तरफ, आप निर्धारक छोड़ने वाली सूचियां भी प्राप्त कर सकते हैं जो सबसे खराब केस प्रदर्शन की गारंटी देते हैं, सीएफ। Munro et al.

उपरोक्त कुछ दावाों के लिए कॉन्ट्रा, आप बाइनरी सर्च पेड़ (बीएसटी) के कार्यान्वयन कर सकते हैं जो समवर्ती प्रोग्रामिंग में अच्छी तरह से काम करते हैं। समेकन-केंद्रित बीएसटी के साथ एक संभावित समस्या यह है कि आप आसानी से संतुलन के बारे में गारंटी नहीं दे सकते क्योंकि आप लाल-काले (आरबी) पेड़ से करेंगे। (लेकिन "मानक", यानि यादृच्छिक, स्किप सूची आपको ये गारंटी नहीं देती है।) हर समय संतुलन बनाए रखने और समेकित (और प्रोग्राम करने में आसान) समवर्ती पहुंच के बीच एक व्यापार-बंद है, इसलिए आराम आरबी पेड़ हैं आमतौर पर जब अच्छी सहमति की वांछित होती है तो इसका उपयोग किया जाता है। विश्राम में पेड़ को फिर से संतुलित नहीं किया जाता है। कुछ हद तक दिनांकित (1 99 8) सर्वेक्षण के लिए हैंके के '' प्रदर्शन का समवर्ती लाल-काला वृक्ष एल्गोरिदम '' [ps.gz] देखें।

इन के बारे में अधिक नए सुधारों का एक (मूल रूप से आप कुछ वजन इस तरह है कि काले 1 होगा और लाल शून्य होगा, लेकिन आप यह भी बीच में मूल्यों की अनुमति देते हैं) तथाकथित रंगीन पेड़ है। और स्किप सूची के खिलाफ एक रंगीन पेड़ किराया कैसे करता है? चलो देखते हैं ब्राउन एट अल क्या। "A General Technique for Non-blocking Trees" (2014) में क्या कहना है: सूत्र

128 के साथ, हमारे एल्गोरिदम से बेहतर साबित जावा के गैर-अवरुद्ध skiplist 13% 156%, Bronson एट अल के लॉक-आधारित AVL पेड़ से। प्यूघ की लॉक-आधारित छोड़ सूची है, जो फ्रेजर और हैरिस में बेंचमार्क गया था (2007): 224% करने के लिए 63%, और एक RBT जोड़ने के लिए सॉफ्टवेयर व्यवहार स्मृति (एसटीएम) 13 134 बार

संपादित करें द्वारा उपयोग करता है के द्वारा "Concurrent Programming Without Lock" अपने लॉक-फ्री संस्करण के करीब आने के रूप में (यहां एक शीर्ष बिंदु पर शीर्ष उत्तर में जोर दिया गया है), अच्छे समवर्ती ऑपरेशन के लिए भी tweaked है, सीएफ। पुग के "Concurrent Maintenance of Skip Lists", हालांकि एक हल्के तरीके से। फिर भी एक नया/200 9 पेपर "A Simple Optimistic skip-list Algorithm" हर्लीह एट अल द्वारा।, जो समवर्ती स्किप सूचियों के लॉक-आधारित कार्यान्वयन के मुकाबले एक सरल (पुग के) लॉक-आधारित कार्यान्वयन का प्रस्ताव करता है, ने पुग की आलोचना की ताकि शुद्धता का प्रमाण उपलब्ध न हो सके। इस (शायद बहुत pedantic) qualm, Herlihy et al को छोड़कर छोड़कर।दिखाएं कि एक स्किप सूची का उनका सरल लॉक-आधारित कार्यान्वयन वास्तव में स्केल के साथ-साथ जेडीके के लॉक-फ्री कार्यान्वयन को विफल करने में विफल रहता है, लेकिन केवल उच्च विवाद (50% आवेषण, 50% हटाना और 0% लुकअप) के लिए ... जो फ्रेज़र और हैरिस ने बिल्कुल परीक्षण नहीं किया; फ्रेज़र और हैरिस ने केवल 75% लुकअप, 12.5% ​​आवेषण और 12.5% ​​हटाए गए (~ 500 के तत्वों के साथ स्किप सूची पर) का परीक्षण किया। Herlihy et al के सरल कार्यान्वयन। कम विवाद के मामले में जेडीके से लॉक-फ्री समाधान के करीब भी आता है (70% लुकअप, 20% आवेषण, 10% हटाना); वे वास्तव में इस परिदृश्य के लिए लॉक-फ्री समाधान को हराते हैं जब उन्होंने अपनी स्किप सूची को काफी बड़ा बना दिया, यानी 200K से 2M तत्वों तक जा रहा था, ताकि किसी भी लॉक पर विवाद की संभावना नगण्य हो जाए। यह अच्छा होगा अगर Herlihy et al। पुग के सबूत पर अपने हैंगअप पर कब्जा कर लिया था और उनके कार्यान्वयन का भी परीक्षण किया था, लेकिन उन्होंने ऐसा नहीं किया।

EDIT2: मुझे एक (2015 प्रकाशित) सभी मानकों का मातृभाषा मिला: ग्रामोली का "More Than You Ever Wanted to Know about Synchronization. Synchrobench, Measuring the Impact of the Synchronization on Concurrent Algorithms": यहां इस प्रश्न के लिए प्रासंगिक एक विस्तृत छवि है।

"Algo.4" ब्राउन एट अल के अग्रदूत (पुराने, 2011 संस्करण) है। जैसा कि ऊपर उल्लेख किया है। (मुझे नहीं पता कि 2014 संस्करण कितना बेहतर या बदतर है)। "Algo.26" Herlihy ऊपर उल्लिखित है; जैसा कि आप देख सकते हैं कि यह अपडेट पर ट्रैश हो जाता है, और मूल CPU से सूर्य CPUs की तुलना में यहां उपयोग किए गए इंटेल CPU पर बहुत अधिक खराब होता है। "Algo.28" JDK से ConcurrentSkipListMap है; यह अन्य सीएएस-आधारित स्किप सूची कार्यान्वयन की तुलना में उम्मीद नहीं करता है। उच्च-विवाद के तहत विजेता "Algo.2" हैं जो लॉक-आधारित एल्गोरिदम (!!) को्रेन एट अल द्वारा वर्णित हैं। "A Contention-Friendly Binary Search Tree" और "Algo.30" में "Logarithmic data structures for multicores" से "घूर्णन स्कीप्लिस्ट" है। "Algo.29" "No hot spot non-blocking skip list" है। सलाह दीजिये कि ग्रामोली इन सभी तीन विजेताओं-एल्गोरिदम पत्रों के सह-लेखक हैं। "Algo.27" फ्रेज़र की स्किप सूची का सी ++ कार्यान्वयन है।

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

एक पेड़ है कि ताला मुक्त की वजह से उपजी atomically कई संदर्भों को संशोधित करने की कठिनाई को डिजाइन करने में कठिनाई। सूची छोड़ें उत्तराधिकारी पॉइंटर्स और के माध्यम से एक दूसरे से जुड़े टावरों को शामिल करता है जिसमें प्रत्येक नोड तुरंत नीचे नोड को इंगित करता है। वे अक्सर पेड़ के समान मानते हैं क्योंकि प्रत्येक नोड उत्तराधिकारी टावर में इसके नीचे उत्तराधिकारी होता है, हालांकि, एक प्रमुख भेद है कि डाउनवर्ड पॉइंटर आमतौर पर अपरिवर्तनीय है इसलिए को नोड के परमाणु संशोधन को सरल बनाते हैं। यह भेद शायद है क्योंकि सूची में ऊपर दिए गए चित्रों के अनुसार भारी विवाद के तहत सूखे सूखे सूचियों को छोड़ दें।

ब्राउन एट अल के हालिया काम में इस कठिनाई को ओवरराइड करना एक प्रमुख चिंता थी। उनके पास एक अलग अलग (2013) पेपर "Pragmatic Primitives for Non-blocking Data Structures" मल्टी-रिकॉर्ड एलएल/एससी कंपाउंड "प्राइमेटिव्स" बनाने पर है, जिसे वे एलएलएक्स/एससीएक्स कहते हैं, जिसे स्वयं (मशीन-लेवल) सीएएस का उपयोग करके लागू किया जाता है। ब्राउन एट अल। 2014 में इस एलएलएक्स/एससीएक्स बिल्डिंग ब्लॉक का इस्तेमाल किया (लेकिन 2011 में नहीं) समवर्ती पेड़ कार्यान्वयन।

मुझे लगता है कि यह शायद "no hot spot"/contention-friendly (CF) skip list के मौलिक विचार को संक्षेप में लायक है। यह आराम से आरबी पेड़ (और समान समेकन तला हुआ डेटा संरचनाओं) से एक आवश्यक विचार जोड़ता है: टावरों को अब सम्मिलन पर तुरंत बनाया नहीं जाता है, लेकिन कम विवाद होने तक देरी हो जाती है।इसके विपरीत, एक लंबा टावर हटाने से कई विवाद पैदा हो सकते हैं; यह पुग के 1 99 0 समवर्ती स्किप-लिस्ट पेपर के रूप में अब तक देखा गया था, यही कारण है कि पुग ने हटाए जाने पर पॉइंटर रिवर्सल पेश किया (एक बोली है कि स्किप सूचियों पर विकिपीडिया का पृष्ठ अभी भी इस दिन का उल्लेख नहीं करता है)। सीएफ छोड़ने की सूची इसे एक कदम आगे ले जाती है और एक लंबा टावर के ऊपरी स्तर को हटाने में देरी होती है। सीएफ स्किप सूचियों में दोनों प्रकार के देरी वाले परिचालनों को एक (सीएएस आधारित) अलग कचरा-कलेक्टर-जैसे थ्रेड द्वारा किया जाता है, जिसके लेखकों ने "अनुकूलण धागा" कहा है।

सिन्क्रोबेंच कोड (परीक्षण किए गए सभी एल्गोरिदम सहित) पर उपलब्ध है: https://github.com/gramoli/synchrobench। नवीनतम ब्राउन एट अल। कार्यान्वयन (उपरोक्त में शामिल नहीं) http://www.cs.toronto.edu/~tabrown/chromatic/ConcurrentChromaticTreeMap.java पर उपलब्ध है क्या किसी के पास 32+ कोर मशीन उपलब्ध है? जे/के मेरा मुद्दा यह है कि आप इन्हें स्वयं चला सकते हैं।