के लिए उपयोग करने के लिए कौन सी नोड डेटा संरचना पहली बार ट्राई का उपयोग कर रहा हूं। मैं जानना चाहता था कि अगली शाखा कौन सी शाखा है, यह तय करते समय ट्राई के लिए उपयोग करने के लिए सबसे अच्छी डेटा संरचना कौन सी है। मैं एक सरणी, एक हैशप और एक लिंक्ड सूची के बीच देख रहा था।ट्राई
इनमें से प्रत्येक विकल्प में उनके फायदे और नुकसान हैं।
यदि आप एक सरणी में बच्चे नोड्स को स्टोर करते हैं, तो आप देख सकते हैं कि कौन सा बच्चा सरणी में अनुक्रमणित करके बेहद कुशलतापूर्वक यात्रा करेगा। हालांकि, प्रति नोड का स्थान उपयोग उच्च होगा: ओ (| Σ |), जहां Σ अक्षरों का सेट है जो आपके शब्दों से बनाया जा सकता है, भले ही उनमें से अधिकतर बच्चे शून्य हैं।
यदि आप एक लिंक की गई सूची में बच्चे नोड्स को स्टोर करते हैं, तो बच्चे को खोजने के लिए आवश्यक समय ओ (| Σ |) होगा, क्योंकि आपको लिंक की गई सूची के सभी नोड्स को स्कैन करने की आवश्यकता हो सकती है बच्चा आप चाहते हैं। दूसरी तरफ, अंतरिक्ष दक्षता काफी अच्छी होगी, क्योंकि आप केवल उन बच्चों को स्टोर करते हैं जिनका आप उपयोग कर रहे हैं। आप यहां एक निश्चित आकार के सरणी का उपयोग करने पर भी विचार कर सकते हैं, जिसमें अंतरिक्ष स्थान भी बेहतर है लेकिन बहुत महंगा प्रविष्टियां और हटाना पड़ता है।
यदि आप एक हैश तालिका में बच्चे नोड्स को स्टोर करते हैं, तो बच्चे को खोजने के लिए (अपेक्षित) समय ओ (1) होगा और स्मृति उपयोग केवल आपके बच्चों की संख्या के लिए आनुपातिक (मोटे तौर पर) होगा। दिलचस्प बात यह है कि, क्योंकि आप पहले से जानते हैं कि आप कितने मूल्यों को हैशिंग करने जा रहे हैं, आप कुछ प्रीकंप्यूशन के खर्च पर सबसे खराब केस ओ (1) लुकअप सुनिश्चित करने के लिए dynamic perfect hash table का उपयोग करने पर विचार कर सकते हैं।
एक और विकल्प बाल नोड्स को बाइनरी खोज पेड़ में स्टोर करना होगा। इससे ternary search tree डेटा संरचना में वृद्धि होती है। यह विकल्प कहीं भी लिंक्ड सूची और हैश टेबल विकल्पों के बीच है - अंतरिक्ष का उपयोग कम है और आप पूर्ववर्ती और उत्तराधिकारी प्रश्नों को कुशलता से कर सकते हैं, लेकिन बीएसटी में खोज लागत के कारण लुकअप करने की लागत में मामूली वृद्धि हुई है। यदि आपके पास स्थिर ट्राई है जहां सम्मिलन कभी नहीं होता है, तो आप प्रत्येक बिंदु पर बीएसटी के रूप में weight-balanced trees का उपयोग करने पर विचार कर सकते हैं; यह खोजों के लिए उत्कृष्ट रनटाइम देता है (ओ (एन + लॉग के), जहां एन खोज के लिए स्ट्रिंग की लंबाई है और के tri में शब्दों की कुल संख्या है)।
संक्षेप में, सरणी लुकअप सबसे तेज़ हैं लेकिन सबसे खराब स्थिति में इसका स्थान उपयोग सबसे खराब है। एक स्थैतिक आकार के सरणी में सबसे अच्छा स्मृति उपयोग होता है लेकिन महंगा प्रविष्टि और हटाना होता है। हैश टेबल में तेजी से तेज़ लुकअप और अच्छी मेमोरी उपयोग (औसत पर) है। बाइनरी सर्च पेड़ बीच में कहीं हैं। मैं यहां हैश टेबल का उपयोग करने का सुझाव दूंगा, हालांकि यदि आप अंतरिक्ष पर प्रीमियम डालते हैं और लुकअप के समय की परवाह नहीं करते हैं तो लिंक्ड सूची बेहतर हो सकती है। इसके अलावा, यदि आपका वर्णमाला छोटा है (कहें, आप बाइनरी ट्राई बना रहे हैं), सरणी ओवरहेड बहुत खराब नहीं होगा और आप इसका उपयोग करना चाहेंगे।
आशा है कि इससे मदद मिलती है!
यदि आप केवल वर्णमाला के लिए त्रिभुज बनाने की कोशिश कर रहे हैं, तो मैं सरणी का उपयोग करने का सुझाव दूंगा और फिर कण पेड़ (अंतरिक्ष अनुकूलित त्रिभुज) का उपयोग करूंगा। http://en.wikipedia.org/wiki/Radix_tree
यह आपको सरणी के साथ तेजी से देखने करने की अनुमति देगा और अंतरिक्ष के बहुत ज्यादा बर्बाद नहीं करता है तो निश्चित नोड के शाखाओं में कारक कम है।
द्विआधारी प्रयासों के लिए आप वास्तव में (बहुत) 2-तत्व सरणी से बेहतर (0) बेहतर कर सकते हैं – harold
@ हेरोल्ड- अच्छा बिंदु। सी या सी ++ जैसी भाषा में दो-तत्व सरणी के बीच कोई अंतर अंतर नहीं होता है और केवल दो पॉइंटर्स धारण करते हैं, हालांकि जावा या पायथन जैसी भाषाओं में आप बिल्कुल सही हैं। – templatetypedef
अच्छी तरह से ऐसा है, लेकिन आप इससे भी बेहतर कर सकते हैं, कुछ चालबाजी के साथ जो आपको कुंजी के अग्रणी शून्य को छोड़ने और सीधे कई प्रमुख शून्य के – harold