जो निरंतर पर निर्भर करता है, बहुत निर्भर है। एक तरफ, ट्राई सभी तत्वों को सम्मिलित करने के लिए सख्त O(N) समय जटिलता प्रदान करता है, जबकि हैश तालिका खराब स्थिति पर क्वाड्रिक समय से क्षय हो सकती है।
दूसरी ओर, की कोशिश करता है जब यह cache की बात आती है बहुत ही कुशल नहीं हैं - प्रत्येक तलाश O(|S|)रैंडम एक्सेस स्मृति अनुरोध किया गया प्रदर्शन में काफी क्षय के कारण हो सकता की आवश्यकता है।
दोनों दृष्टिकोण मान्य हैं, और मुझे लगता है कि अधिकतम latency (यदि यह वास्तविक समय प्रणाली है), थ्रूपुट, और विकसित करने के लिए समय जैसे दूसरे को चुनते समय कई विचार-विमर्श किए जाने चाहिए।
यदि औसत केस प्रदर्शन सभी महत्वपूर्ण है, तो मैं फ़ाइलों का एक समूह उत्पन्न करने और statistical analysis चलाने का सुझाव देता हूं जो दृष्टिकोण बेहतर है। Wilcoxon हस्ताक्षरित परीक्षण उपयोग में कला परिकल्पना परीक्षण की वास्तविक तथ्य है।
एम्बेडेड सिस्टम के बारे में: दोनों दृष्टिकोण अभी भी मान्य हैं, लेकिन यहाँ में: प्रत्येक "नोड" (या नोड्स के गुच्छा) trie में डिस्क पर नहीं बल्कि उसके बाद राम पर होगा। ध्यान दें कि इसका अर्थ है ट्राई ओ (| एस |) यादृच्छिक पहुंच डिस्क प्रति प्रविष्टि प्रति प्रविष्टि चाहता है, जो धीमा हो सकता है।
हैशिंग समाधान के लिए, आपके पास 10 एमबी है, मान लीजिए कि वे डिस्क में पॉइंटर्स की हैश तालिका के लिए इनमें से 5 एमबी का उपयोग कर सकते हैं।आइए यह भी मान लें कि आप इन 5 एमबी (यहां निराशावादी विश्लेषण) पर 500 अलग-अलग डिस्क पतों को स्टोर कर सकते हैं, इसका मतलब है कि आपके पास प्रत्येक हैश की तलाश के बाद बाल्टी लोड करने के लिए 5 एमबी शेष है, और यदि आपके पास 0.5 बाल्टी के साथ 500 बाल्टी हैं, तो इसका मतलब है आप 500 * 5 एमबी * 0.5 ~ = 1.25 जीबी> डेटा का 1 जीबी स्टोर कर सकते हैं, इस प्रकार हैश टेबल समाधान का उपयोग कर रहे हैं, इसलिए हैशिंग का उपयोग करके - प्रत्येक खोज को केवल O(1)यादृच्छिक डिस्क की तलाश में बाल्टी खोजने के लिए प्रासंगिक स्ट्रिंग
ध्यान दें कि यदि यह अभी भी पर्याप्त नहीं है, तो हम पॉइंटर्स टेबल को रीहाश कर सकते हैं, वर्चुअल मेमोरी मैकेनिज्म में paging table में क्या किया जा रहा है।
इस हम एम्बेडेड प्रणाली के लिए, निष्कर्ष निकाल सकते हैं से, हैश समाधान ज्यादातर मामलों के लिए बेहतर है (यह नोट अभी भी खराब मामलों पर उच्च विलंबता से पीड़ित हो सकता है, कोई जादुई शब्द यहाँ)।
पुनश्च, radix tree आमतौर पर तेजी से और अधिक कॉम्पैक्ट तो trie है, लेकिन (बेशक, हालांकि कम महत्वपूर्ण) टेबल हैश करने के लिए की तुलना trie का एक ही साइड इफेक्ट से ग्रस्त है।
शायद 1 जीबी फ़ाइल में आप कितने अलग शब्द होने की उम्मीद कर रहे हैं? – NPE
मैं वास्तव में विशेष रूप से कुछ भी उम्मीद नहीं कर रहा हूं। इस समस्या को वास्तविक दुनिया के शब्दों में फिर से लिखा जा सकता है क्योंकि खोजों की सूची या उस तरह की किसी चीज़ से शीर्ष 10 खोज शब्द ढूंढते हैं, इसलिए मुझे लगता है कि यह किसी प्रकार की संभाव्यता वितरण का पालन करेगा, लेकिन मैं किसी विशेष पर सेट नहीं हूं। – user1921187