पेड़ के नोड्स पर समानता कक्षाओं के निर्माण के लिए एक अच्छी डेटा संरचना क्या है?

Question

मैं एक पेड़ के नोड्स पर समकक्ष वर्ग बनाने के लिए एक अच्छी डेटा संरचना की तलाश में हूं। एक आदर्श संरचना में, निम्न कार्रवाई तेजी से (ओ (1)/ओ (जैसा उचित एन)) होना चाहिए और आसान (रहस्य कोड का कोई पैराग्राफ):

• (ए) जड़ से पेड़ चलो; प्रत्येक नोड पर -> बच्चे संक्रमण चाइल्ड नोड
• (बी) दो तुल्यता कक्षाओं मर्ज के सभी बराबर संस्करणों की गणना
• (सी) मौजूदा नोड्स (बच्चों) और अन्य डेटा
की एक सूची से नई नोड्स बनाएं
• (डी) नोड के संरचनात्मक रूप से समकक्ष किसी भी नोड्स खोजें (यानी उनके पास समान संख्या में बच्चे हैं, संबंधित बच्चे समान समकक्ष वर्ग के हैं, और उनका "अन्य डेटा" बराबर है) ताकि नए (या नए संशोधित) नोड्स हो सकें सही समकक्ष वर्ग (एक विलय के माध्यम से)

अब तक मैंने माना है (इनमें से कुछ संयोजन में उपयोग किया जा सकता है):

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

क्या मुझे एक मीठा विकल्प याद आ रहा है?

Answer 1

आपके पास सौदा करने के लिए समानता के दो रूप हैं। सादा समकक्ष (ए), समकक्ष वर्गों के रूप में ट्रैक किया जाता है जो अद्यतित और संरचनात्मक समकक्ष (डी) रखा जाता है, जिसके लिए आप कभी-कभी एक समकक्ष वर्ग का निर्माण करते हैं और फिर इसे फेंक देते हैं।

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

Answer 2

मुझे नहीं लगता कि कोई भी संरचना आपकी समस्याओं का समाधान करने जा रही है, लेकिन आप Disjoint-set data structure पर एक नज़र डाल सकते हैं। एक समकक्ष वर्ग, आखिरकार, एक सेट के विभाजन के समान ही है। यह उन परिचालनों में से कुछ को तेजी से संभालने में सक्षम होना चाहिए।

Answer 3

एक पल के लिए पीछे हटना मैं एक पेड़ का उपयोग करने के खिलाफ सुझाव देना चाहता हूं। पिछली बार मुझे एक ही समस्या का सामना करना पड़ा, मैंने एक पेड़ से शुरुआत की, लेकिन बाद में एक सरणी पर चले गए।

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

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