सी # बाइनरी पेड़ और शब्दकोश

Question

मैं बाइनरी खोज पेड़ों का उपयोग करने और शब्दकोशों का उपयोग कब करने की अवधारणा से जूझ रहा हूं।

मेरे आवेदन में मैंने थोड़ा प्रयोग किया जो सी 5 लाइब्रेरी TreeDictionary (जो मुझे लगता है कि एक लाल-काला बाइनरी खोज पेड़ है), और सी # शब्दकोश का उपयोग किया। शब्दकोश जोड़ने/ढूंढने के संचालन में हमेशा तेज़ था और हमेशा कम मेमोरी स्पेस भी इस्तेमाल किया जाता था। उदाहरण के लिए, 1680 9 <int, float> प्रविष्टियों पर, शब्दकोश ने 342 कीबी का उपयोग किया जबकि पेड़ 723 कीबी का इस्तेमाल किया।

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

साथ ही, एक साइड सवाल के रूप में, क्या किसी को पता है कि <int, float> स्टोर्स को किसी भी प्रकार की संरचनाओं की तुलना में शब्दकोश प्रकार के उपयोग के लिए जोड़े जाने के लिए तेज + अधिक मेमोरी कुशल डेटा संरचना है?

Answer 1

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

मैंने व्यक्तिगत रूप से इस तरह के सिद्धांत के बारे में कभी नहीं सुना है। फिर भी, यह केवल एक सामान्य सिद्धांत है, ब्रह्मांड के कपड़े में एक विशिष्ट तथ्य नहीं है।

आम तौर पर, शब्दकोश वास्तव में लिंक की गई सूचियों की एक श्रृंखला के आसपास एक फैंसी रैपर हैं।

LinkedList<Tuple<TKey, TValue>> list = 
    internalArray[internalArray % key.GetHashCode()]; 
if (list.Exists(x => x.Key == key)) 
    throw new Exception("Key already exists"); 
list.AddLast(Tuple.Create(key, value)); 

तो इसकी लगभग हे (1) आपरेशन: आप की तरह शब्दकोश कुछ में सम्मिलित करें। शब्दकोश O (internalArray.Length + n) मेमोरी का उपयोग करता है, जहां n संग्रह में आइटम की संख्या है।

• लिंक्ड सूची, जो हे (एन) स्थान का प्रयोग करें, जहां n संग्रह में नंबर आइटम है:

  सामान्य BSTs में के रूप में लागू किया जा सकता।

• arrays, जो ओ (2 ^एच - एन) का उपयोग करता है, जहां अंतरिक्ष पे एच की ऊंचाई है और एन संग्रह में वस्तुओं की संख्या है।

-

• के बाद से लाल-काले पेड़ों ओ (1.44 * एन) के एक घिरे ऊंचाई है, एक सरणी कार्यान्वयन के बारे में O (n 2 ^1.44n) के एक घिरे स्मृति उपयोग करना चाहिए था

  बाधाएं हैं, सी 5 ट्री डिक्शनरी सरणी का उपयोग करके कार्यान्वित किया गया है, जो शायद बर्बाद अंतरिक्ष के लिए ज़िम्मेदार है।

  क्या देता है? क्या कोई बिंदु है जहां बीएसटी शब्दकोशों से बेहतर है?

  • वहाँ स्मृति के लिए पर्याप्त continugous ब्लॉक अपने शब्दकोश धारण करने के लिए, भले ही इसकी मेमोरी जरूरतों कुल उपलब्ध रैम की तुलना में से बहुत कम हैं नहीं हो सकता है:

  शब्दकोश कुछ अवांछनीय गुण होते हैं।

• हैश फंक्शन का मूल्यांकन समय की एक मनमाने ढंग से लंबे समय तक लंबाई ले सकते हैं। स्ट्रिंग्स, उदाहरण के लिए, System.String.GetHashCode विधि की जांच करने के लिए परावर्तक का उपयोग करें - आपको पता चलेगा कि एक स्ट्रिंग हैशिंग हमेशा ओ (एन) समय लेती है, जिसका अर्थ है कि यह बहुत लंबे तारों के लिए काफी समय ले सकता है। हाथ पर, असमानता के लिए तारों की तुलना लगभग हैशिंग से लगभग हमेशा तेज है, क्योंकि इसे केवल पहले कुछ वर्णों को देखने की आवश्यकता हो सकती है। यदि हैश कोड मूल्यांकन बहुत लंबा लगता है तो पेड़ के आवेषण से तेज होने के लिए यह पूरी तरह से संभव है।

  • Int32 के GetHashCode विधि सचमुच return this है, तो आप एक मामले को खोजने के लिए जहां पूर्णांक कुंजी के साथ एक hashtable एक पेड़ शब्दकोश की तुलना में धीमी hardpressed होगी है।

    • आप पा सकते हैं/हे (लॉग एन) समय हे की तुलना में न्यूनतम और अधिकतम तत्वों को दूर (एन) समय एक का उपयोग कर:

  आरबी पेड़ कुछ वांछनीय गुण होते हैं शब्दकोश।

• यदि एक पेड़ को सरणी के बजाय लिंक की गई सूची के रूप में कार्यान्वित किया जाता है, तो पेड़ आमतौर पर एक शब्दकोश से अधिक स्थान कुशल होता है।

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

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

तो, डेटा संरचना की पसंद वास्तव में आपकी आवश्यकताओं के आधार पर निर्भर करती है। यदि आप सिर्फ एक अनियंत्रित बैग चाहते हैं और गारंटी दे सकते हैं कि आपके हैश फ़ंक्शन का मूल्यांकन जल्दी से हो, तो नेट शब्दकोश के साथ जाएं। अगर आपको ऑर्डर किए गए बैग की आवश्यकता है या धीमी गति से चल रहे हैंश फ़ंक्शन हैं, तो TreeDictionary के साथ जाएं।

Answer 2

ऐसा लगता है कि आप समयपूर्व अनुकूलन कर रहे हैं।

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

यदि स्मृति/प्रदर्शन एक मुद्दा बन जाता है (जो शायद 20k-numbers के लिए नहीं होगा), तो आप अन्य इंटरफ़ेस कार्यान्वयन बना सकते हैं, और जांच सकते हैं कि कौन सा बेस्ट काम करता है। आपको शेष कोड में लगभग कुछ भी बदलने की आवश्यकता नहीं होगी (सिवाय इसके कि आप किस कार्यान्वयन का उपयोग कर रहे हैं)।

Answer 3

यह समझ में आता है कि एक पेड़ नोड को एक शब्दकोश प्रविष्टि की तुलना में अधिक संग्रहण की आवश्यकता होगी। एक बाइनरी पेड़ नोड को मूल्य और बाएं और दाएं सबट्री दोनों को स्टोर करने की आवश्यकता होती है। सामान्य Dictionary<TKey, TValue> को हैश तालिका के रूप में कार्यान्वित किया गया है - मैं मान रहा हूं - या तो प्रत्येक बाल्टी (मूल्य प्लस एक पॉइंटर/संदर्भ) या किसी प्रकार के रीमेपिंग (केवल मान) के लिए एक लिंक्ड सूची का उपयोग करता है। मुझे सुनिश्चित करने के लिए परावर्तक में एक झलक देखना होगा, लेकिन इस सवाल के उद्देश्य से मुझे नहीं लगता कि यह महत्वपूर्ण है।

स्पेसर हैश तालिका, भंडारण/स्मृति के मामले में कम कुशल। यदि आप हैश टेबल (डिक्शनरी) बनाते हैं और इसकी क्षमता 1 मिलियन तक शुरू करते हैं, और केवल इसे 10,000 तत्वों से भरें, तो मुझे पूरा यकीन है कि यह 10,000 नोड्स के साथ बीएसटी की तुलना में बहुत अधिक मेमोरी खाएगा।

फिर भी, अगर मैं नोड्स/चाबियों की मात्रा केवल हजारों में है तो मैं इसके बारे में चिंता नहीं करता। भौतिक रैम के गीगाबाइट की तुलना में, किलोबाइट्स में मापा जा रहा है।

---

यदि प्रश्न है "आप हैश टेबल के बजाय बाइनरी पेड़ का उपयोग क्यों करना चाहते हैं?" फिर सबसे अच्छा जवाब आईएमओ यह है कि बाइनरी पेड़ का आदेश दिया जाता है जबकि हैश टेबल नहीं हैं। आप केवल उन चाबियों के लिए हैश तालिका खोज सकते हैं जो बिल्कुल कुछ के बराबर हैं; एक पेड़ के साथ, आप मूल्यों, निकटतम मूल्य इत्यादि की एक श्रृंखला की खोज कर सकते हैं। यदि आप एक इंडेक्स या कुछ समान बना रहे हैं तो यह एक बहुत ही महत्वपूर्ण भेद है।

Answer 4

एक पेड़ और एक हैश तालिका के लिए इंटरफ़ेस (जो मैं अनुमान लगा रहा हूं कि आपका शब्दकोश एक आधारित है) एक जैसा होना चाहिए। हमेशा कुंजीपटल लुकअप के आसपास घूमती है।

मैंने हमेशा सोचा था कि एक बार चीजें बनाने के लिए एक शब्दकोश बेहतर था और उसके बाद बहुत सारे लुकअप कर रहे थे। जबकि एक वृक्ष बेहतर था अगर आप इसे महत्वपूर्ण रूप से संशोधित कर रहे थे। हालांकि, मुझे नहीं पता कि मैंने उस विचार को कहाँ से उठाया था।

(कार्यात्मक भाषाएं अक्सर पेड़ों को संग्रह के आधार के रूप में उपयोग करती हैं क्योंकि आप पेड़ के अधिकांश उपयोग फिर से कर सकते हैं यदि आप इसमें छोटे बदलाव करते हैं)।

Answer 5

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

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