एक बार फिर से स्किलिस्ट के बारे में ...

... या मुझे कंसोल एप्लीकेशन के लिए अलेंका कैसे मिला

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

कल्पना करें कि आपके सहकर्मी-नौसिखिए अपने मुश्किल काम के बारे में बात करने के लिए आए थे - उन्हें बढ़ते हुए क्रम में पूर्णांकों के सेट को न केवल क्रमबद्ध करने की आवश्यकता है, बल्कि लेट से लेकर आरथ समावेशी के लिए निर्धारित आदेश के सभी तत्वों को शामिल करने की आवश्यकता है!
आपने कहा कि यह एक प्राथमिक कार्य है और C # में समाधान लिखने के लिए आपको दस मिनट का समय चाहिए। खैर, या एक घंटा। या दो। या चॉकलेट "एलोनका"

यह माना जाता है कि सेट में डुप्लिकेट की अनुमति है, और तत्वों की संख्या 10 ^ 6 से अधिक नहीं होगी।

समाधान के मूल्यांकन के लिए कई टिप्पणियाँ हैं:

तीन प्रोग्रामर आपके कोड का मूल्यांकन और परीक्षण करेंगे:

• बिल आपके समाधान को 10Kb से बड़े परीक्षणों पर नहीं चलाएगा।
• स्टीफन के परीक्षणों में, अनुरोधों की संख्या 10 ^ 5 से अधिक नहीं होगी, जबकि इसके अलावा अनुरोधों की संख्या 100 से अधिक नहीं होगी।
• मार्क के परीक्षणों में, प्रश्नों की संख्या 10 ^ 5 से अधिक नहीं होगी।

समाधान बहुत दिलचस्प हो सकता है, इसलिए मैंने इसका वर्णन करना आवश्यक समझा।

निर्णय

हमें एक अमूर्त भंडार है।

जोड़ना (ई) को अस्वीकार करें - स्टोर में एक आइटम जोड़ें, और रेंज (एल, आर) - एल से आर तत्व तक एक टुकड़ा लें।

एक तुच्छ भंडारण विकल्प यह हो सकता है:

• भंडारण एक आरोही गतिशील सरणी पर आधारित होगा।
• हर बार जब आप एक बाइनरी खोज सम्मिलित करते हैं, तो एक स्थिति होती है जहां आप एक तत्व सम्मिलित करना चाहते हैं।
• जब रेंज (एल, आर) को क्वेरी करते हैं, हम बस एल से आर तक सरणी का टुकड़ा लेते हैं।

हम एक गतिशील सरणी के आधार पर दृष्टिकोण की जटिलता का अनुमान लगाते हैं।

सी रेंज (एल, आर) - एक स्लाइस लेने का अनुमान ओ (आर - एल) के रूप में लगाया जा सकता है।

C Add (e) - सबसे खराब स्थिति में सम्मिलन O (n) के लिए काम करेगा, जहां n तत्वों की संख्या है। N ~ 10 ^ 6 के लिए, इंसर्ट एक अड़चन है। एक बेहतर भंडारण विकल्प बाद में लेख में प्रस्तावित किया जाएगा।

स्रोत कोड का एक उदाहरण यहां पाया जा सकता है ।

एक और अधिक उपयुक्त विकल्प हो सकता है, उदाहरण के लिए, यह:

• रिपॉजिटरी का आधार एक सेल्फ-बैलेंसिंग सर्च ट्री होगा , जिसमें डालने, खोज, डिलीट ऑपरेशन (AVL ट्री, आरबी ट्री और अन्य) के लिए O (ln n) जटिलता है।
• उप-नोड में नोड की संख्या पर जानकारी जोड़कर डेटा संरचना का विस्तार किया जाता है। ओ (ln n) के लिए पेड़ के आई-वें तत्व को प्राप्त करने के लिए यह आवश्यक है।
• आइटम को उपशीर्षक में नोड्स की संख्या को पुन: प्राप्त करने के लिए पेड़ में जोड़ा जाता है। यह किया जा सकता है ताकि ऐड ऑपरेशन की लागत O (ln n) बनी रहे।

मैं कॉर्मेन को खोलने के लिए लगभग तैयार था और यह याद रखना शुरू कर दिया कि आरबी-ट्री कैसे काम करता है, लेकिन संयोग से मैं स्किप्पलिस्ट पर एक विकिपीडिया लेख में आया था।

Skiplist

कई लिंक की गई सूचियों के आधार पर, पेड़ की खोज करने के लिए स्किलिस्ट एक यादृच्छिक विकल्प है। इसका आविष्कार विलियम पुघ ने 1989 में किया था। लॉगरिदमिक रूप से यादृच्छिक समय में खोज, सम्मिलित करना और हटाना ऑपरेशन किए जाते हैं।

यह डेटा संरचना व्यापक रूप से ज्ञात नहीं है (वैसे, और यह हैबे पर काफी प्रचुर मात्रा में लिखा गया है), हालांकि इसके अच्छे विषम अनुमान हैं। जिज्ञासा के लिए, मैं इसे महसूस करना चाहता था, सभी अधिक उपयुक्त कार्य था।

आगे मैं उन सभी स्रोतों से एक संक्षिप्त निचोड़ दूंगा जिन्हें मैंने हल किया था।

मान लीजिए कि हमारे पास एक क्रमबद्ध, बस जुड़ी हुई सूची है:

सबसे खराब स्थिति में, खोज O (n) में की जाती है। इसे कैसे त्वरित किया जा सकता है?

जब मैं कार्य कर रहा था, तो मैंने अपने वीडियो व्याख्यान में, मैंने न्यूयॉर्क में एक्सप्रेस लाइनों के बारे में एक अद्भुत उदाहरण दिया था:

• स्पीड लाइनें कुछ स्टेशनों को जोड़ती हैं
• नियमित लाइनें सभी स्टेशनों को जोड़ती हैं
• सामान्य गति लाइन स्टेशनों के बीच नियमित लाइनें हैं

विचार यह है: हम एक निश्चित संख्या में स्तरों को एक निश्चित संख्या में नोड्स के साथ जोड़ सकते हैं, जबकि स्तरों में नोड्स समान रूप से वितरित किए जाने चाहिए। उदाहरण पर विचार करें जब प्रत्येक overlying स्तरों में अंतर्निहित स्तर से तत्वों के आधे होते हैं:


सही SkipList उदाहरण पर दिखाया गया है, वास्तव में सब कुछ समान दिखता है, लेकिन थोड़ा गलत है :)

खोज

इसी से खोज होती है मान लीजिए कि हम 72 वें तत्व की तलाश कर रहे हैं:

डालने

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

इसे इस तरह से हल करने का प्रस्ताव है: सम्मिलित करते समय, हम एक नए तत्व को निम्नतम स्तर पर जोड़ते हैं और एक सिक्के को उछालना शुरू करते हैं जब तक कि यह बाहर नहीं निकल जाता है, हम तत्व को अगले ओवरलेइंग स्तर तक धकेलते हैं।
आइए तत्व को सम्मिलित करने का प्रयास करें - 67. पहले हम पाते हैं कि इसे नीचे दी गई सूची में कहां सम्मिलित करना है:



उन्होंने सुझाव दिया कि सिक्का लगातार दो बार गिरा। तो आपको तत्व को दो स्तरों तक बढ़ाने की आवश्यकता है:

इंडेक्स एक्सेस

सूचकांक द्वारा एक्सेस करने के लिए, यह निम्न करने का प्रस्ताव है: प्रत्येक संक्रमण को नोड्स की संख्या के साथ चिह्नित करें जो इसके तहत निहित हैं:



जब हम ith तत्व तक पहुँच प्राप्त कर लेते हैं (वैसे, हम इसे O (ln n)) में प्राप्त करते हैं, तो इसे काटना मुश्किल नहीं लगता।

रेंज (5, 7) को खोजने के लिए यह आवश्यक है। पहले हमें सूचकांक पाँच में एक तत्व मिलता है:


और अब रेंज (5, 7):

कार्यान्वयन के बारे में

जब यह इस तरह दिखता है तो कार्यान्वयन स्वाभाविक लगता है:

SkipListNode {
int Element;
SkipListNode[] Next;
int [] Width;
}


दरअसल, यह विलियम पग द्वारा सी पर कार्यान्वयन में किया गया था।

लेकिन सी # में, इसकी लंबाई भी सरणी में संग्रहीत की जाती है, लेकिन मैं इसे स्मृति की सबसे छोटी संभव मात्रा के लिए करना चाहता था (जैसा कि यह निकला, कार्य की स्थितियों में सब कुछ इतनी सख्ती से मूल्यांकन नहीं किया गया था)। उसी समय, मैं SkipList के कार्यान्वयन और विस्तारित आरबी ट्री को लगभग समान मात्रा में मेमोरी बनाना चाहता था।

मेमोरी की खपत को कम करने का जवाब अप्रत्याशित रूप से java.util.concurrent पैकेज से समवर्तीSkipListMap के घनिष्ठ निरीक्षण पर मिला।

दो आयामी स्केपिस्ट

चलो एक आयाम में सभी तत्वों की एक बस जुड़ी हुई सूची हो। दूसरे में, निचले स्तर के लिंक के साथ संक्रमण के लिए "एक्सप्रेस लाइनें" होंगी।

ListNode {
int Element;
ListNode Next;
}

Lane {
Lane Right;
Lane Down;
ListNode Node;
}

बेईमान सिक्का

स्मृति की खपत को कम करने के लिए, आप "बेईमान" सिक्के का उपयोग कर सकते हैं: एक तत्व को अगले स्तर तक धकेलने की संभावना को कम करें। विलियम पुघ ने कई पुश संभावना मूल्यों के एक स्लाइस की समीक्षा की। व्यवहार में values ​​और मूल्यों पर विचार करते समय, स्मृति खपत में कमी के साथ लगभग एक ही खोज समय प्राप्त किया गया था।

यादृच्छिक संख्या पीढ़ी के बारे में थोड़ा

समवर्तीSkipListMap की हिम्मत में कमी, मैंने देखा कि यादृच्छिक संख्याएँ निम्नानुसार उत्पन्न होती हैं:

int randomLevel() {
int x = randomSeed;
x ^= x << 13;
x ^= x >>> 17;
randomSeed = x ^= x << 5;
if ((x & 0x80000001) != 0)
return 0;
int level = 1;
while (((x >>>= 1) & 1) != 0) ++level;
return level;
}

इस लेख में XOR का उपयोग करके छद्म आयामी संख्या उत्पन्न करने के बारे में और पढ़ें। मैंने गति में कोई विशेष वृद्धि नहीं देखी, इसलिए, मैंने इसका उपयोग नहीं किया।

परिणामी संग्रहण का स्रोत कोड यहां देखा जा सकता है ।

सभी एक साथ आप googlecode.com (प्रोजेक्ट पेजिनेशन) से चुन सकते हैं।

परीक्षण

तीन प्रकार के भंडारण का उपयोग किया गया था:

1. सरणी (गतिशील सरणी)
2. SkipListBased (पैरामीटर L के साथ छोड़ें)
3. आरबीट्रीबेड (लाल-काला पेड़: मेरे दोस्त का एक कार्यान्वयन जो एक समान कार्य करता है)।

10 ^ 6 तत्वों को सम्मिलित करने के लिए तीन प्रकार के परीक्षण किए गए थे:

1. आरोही आइटम
2. अवरोही वस्तुएँ
3. यादृच्छिक आइटम

टेस्ट मशीन पर i5, 8gb ram, sdd और विंडोज 7 x64 के साथ आयोजित किए गए थे।
परिणाम:

	सरणी	RBTree	SkipList
बिना सोचे समझे	127033 एमएस	1020 मि	1737 मि
आदेश दिया	108 एमएस	457 मि	536 मि
उतर कर आदेश दिया	256337 मि	358 मि	407 मि

काफी अपेक्षित परिणाम। यह देखा जा सकता है कि एक तत्व में डालने पर जब कोई तत्व कहीं डाला जाता है, तो अंत में छोड़कर, सबसे धीरे से काम करता है। वहीं, स्किपबीस्ट आरबीट्री से धीमा है।

माप भी लिया गया था: प्रत्येक भंडारण में 10 ^ 6 तत्वों के साथ स्मृति में कितना ले जाता है। एक स्टूडियो प्रोफाइलर का उपयोग किया गया था, सरलता के लिए, निम्नलिखित कोड लॉन्च किया गया था:

var storage = ...
for ( var i = 0; i < 1000000; ++i)
storage.Add(i);


परिणाम:

	सरणी	RBTree	SkipList
कुल बाइट्स आवंटित	8,389,066 बाइट्स	24,000,060 बाइट्स	23,985,598 बाइट्स

अभी भी काफी अपेक्षित परिणाम हैं: डायनेमिक ऐरे पर स्टोरेज ने कम से कम मेमोरी ली, जबकि स्किपलिस्ट और आरबीट्री ने एक ही राशि के बारे में सोचा।

ऐलोनका के साथ हैप्पी एंड

एक सहकर्मी, एक समस्या के हालात के अनुसार, एक whiner, मेरे लिए एक बार खोला। मेरे निर्णय को अधिकतम अंक के साथ श्रेय दिया गया। मुझे उम्मीद है कि किसी को यह लेख मददगार लगेगा। यदि आपके कोई प्रश्न हैं, तो मुझे उत्तर देने में खुशी होगी।

पुनश्च: मैं SKB कोंतुर में एक इंटर्नशिप पर था। यह एक ही सवाल का जवाब नहीं है =)