मेरे पास तारों की एक सूची है और यह पता लगाने की आवश्यकता है कि कौन से स्ट्रिंग किसी दिए गए इनपुट मान से मेल खाते हैं। स्ट्रिंग्स की इस सूची को स्टोर करने के लिए सबसे प्रभावी तरीका (मेमोरी बनाम निष्पादन गति) क्या है और इसके माध्यम से खोज करने में सक्षम हो? तारों की सूची का स्टार्ट-अप और लोडिंग महत्वपूर्ण नहीं है, लेकिन खोज के लिए प्रतिक्रिया समय है।कुशल तरीका?
क्या मुझे एक सूची या हैशसेट या सिर्फ एक बुनियादी स्ट्रिंग [] या कुछ और उपयोग करना चाहिए?
यह तार की प्रकृति और संग्रह के आकार पर बहुत ज्यादा निर्भर करता है। संग्रह की विशेषताओं और अपेक्षित खोज तारों के आधार पर, चीजों को बहुत चालाकी से व्यवस्थित करने के तरीके हैं ताकि खोज बहुत तेज हो। आपने हमें वह जानकारी नहीं दी है।
लेकिन यहां मैं क्या करूँगा। मैं एक उचित प्रदर्शन आवश्यकता निर्धारित करेंगे। तो मैं एक एन-ग्राम इंडेक्स का प्रयास करूंगा (क्यों? क्योंकि आपने एक टिप्पणी में कहा था कि आपको आंशिक मैचों के लिए खाते की आवश्यकता है; HashSet<string> आपकी मदद नहीं करेगा) और मैं इस समाधान के खिलाफ अपेक्षाकृत उचित इनपुट प्रोफाइल करूंगा और देखें कि यह मेरी प्रदर्शन आवश्यकताओं को पूरा करता है या नहीं। अगर ऐसा होता है, तो मैं समाधान स्वीकार करता हूं और आगे बढ़ता हूं। यदि ऐसा नहीं होता है, तो मैं बहुत सावधानी से सोचूंगा कि मेरी प्रदर्शन आवश्यकताओं उचित हैं या नहीं। यदि वे हैं, तो मैं इस बारे में सोचना शुरू कर दूंगा कि मेरे इनपुट और संग्रह के बारे में कुछ खास है या नहीं, जो मुझे कुछ और चालाक समाधानों का उपयोग करने में सक्षम बनाता है।
के गेटाफेक्स समाधान भी हैशसेट आंशिक मैचों के लिए अपनी आवश्यकताओं को पूरा नहीं कर सकता है (और यदि तारों को "डुप्लीकेट किया जा सकता है" तो इसका तात्पर्य है कि कुछ जानकारी को अलग करने के लिए कुछ जानकारी है डुप्लीकेट्स, तो यह हैशसेट के बजाए वैसे भी एक शब्दकोश होगा) – Random832
@ Random832: उसका प्रश्न आंशिक मैचों और न ही डुप्लीकेट के बारे में कुछ भी नहीं कहता है! – jason
एक फॉलोअप टिप्पणी - एफजीआईटीडब्ल्यू होने के लिए आपकी भीड़ में आपने यह पूछने से नहीं रोक दिया कि क्या आवश्यक था - मूल शब्द किसी समस्या को लागू करने के करीब नहीं आता है जो हैशसेट हल कर सकता है। "दिए गए इनपुट मान से मेल खाने वाले स्ट्रिंग्स" का सावधानीपूर्वक पढ़ने से पता चलता है कि बहुवचन आंशिक मिलान का तात्पर्य है (केवल एक स्ट्रिंग बिल्कुल मेल खा सकता है) – Random832
Dictionary<string>() या HashSet<string> का उपयोग करें आपके लिए शायद अच्छा है।
+1: यह पहली चीज है जो स्ट्रिंग की सूची में खोज स्ट्रिंग को अनुकूलित करने के बारे में सोचते समय मेरे दिमाग में आई: पहला आम समाधान "इंडेक्सिंग" है, जो एक शब्दकोश के साथ सबसे आम समाधान है। –
@StephaneRolland हाँ कुछ समय सबसे आसान है, लेकिन +1 –
शब्दकोश और हैशटेबल "खोज" पर सबसे तेज़ होने जा रहे हैं क्योंकि यह ओ (1) गति है। शब्दकोश और हैशटेबल्स में कुछ गिरावट आई हैं जिनमें वे क्रमबद्ध नहीं हैं।
एक बाइनरी खोज पेड़ का उपयोग करके आप ओ (लॉग एन) खोज प्राप्त कर पाएंगे।
एक अपरिवर्तित सूची का उपयोग करके आप खोज के लिए ओ (एन) गति होगी।
एक क्रमबद्ध सूची का उपयोग करके आपको ओ (लॉग एन) खोज मिल जाएगी लेकिन ध्यान रखें कि सूची को सॉर्ट किया जाना चाहिए ताकि समग्र गति में समय जोड़ा जा सके।
स्मृति उपयोग के लिए बस यह सुनिश्चित करें कि आप संग्रह के आकार को आरंभ करें।
तो शब्दकोश या हैश तालिका पुनर्प्राप्ति के लिए सबसे तेज़ है। सबसे अच्छा से सबसे खराब करने के लिए
स्पीड वर्गीकरण हैं हे (1) हे (लॉग एन) हे (एन) O (n लॉग ऑन एन) O (n^2) हे (2^n)
एन तत्वों की संख्या होने के नाते।
@FelicePollano मुझे नहीं लगता कि आपके पास ओ (1) सही का अर्थ है। – Random832
@ Random832 यह ओ (1) डालने में है। खोज में यह ओ (1) सूची का पता लगाने है और फिर यह एक रैखिक खोज करता है। आपके लिए क्या गलत है? –
तथ्य यह है कि "सूची" जिसे रैखिक रूप से खोजा जाना है [यानी। टकराव श्रृंखला] आम तौर पर संक्षेप में होती है, न कि शब्दकोश में वस्तुओं की कुल संख्या के अनुपात में (बशर्ते बाल्टी की उचित संख्या हो) का अर्थ है कि यह अभी भी ओ (1) अमूर्त है, जब तक कि एक ही हैश के साथ बड़ी संख्या में आइटम न हो कोड [अनजाने में जब तक जानबूझकर इस तरह से निर्मित नहीं किया जाता है] डाला जाता है। संपादन के लिए – Random832
ऐसा लगता है कि O (input_len) समय में आपके इनपुट का प्रत्यय वृक्ष बनाने का सबसे अच्छा तरीका है, तो O (pattern_length) समय में अपने पैटर्न के प्रश्न पूछें। तो यदि आपका पाठ आपके पैटर्न की तुलना में वास्तव में बड़ा है, तो यह अच्छी तरह से काम करेगा।
प्रत्यय पेड़ के निर्माण के लिए Ukkonen के एल्गोरिदम देखें।
यदि आप अचूक मिलान चाहते हैं ... गोंज़ालो नेवरो का काम देखें।
टीएक्स। :) –
"ट्राई में प्रत्येक नोड के लिए केवल 256 या उससे अधिक संभावना 128 वर्ण/बाइट सरणी बनाएं।" - सरणी 256/128 _pointers होगी nodes_, बाइट्स नहीं। – Random832
या ... और भी सही ढंग से ... ऑब्जेक्ट संदर्भ/पॉइंटर्स नोड नोड * = नया नोड [128] के चरित्र के एएससीआई (या अन्य वर्णसेट) कोड द्वारा अनुक्रमित एक सरणी। आपके सुधार के लिए धन्यवाद Random832। –
स्ट्रिंग्स की सूची कितनी "बड़ी" है? –
स्ट्रिंगकोलेक्शन क्लास के बारे में न भूलें - http://msdn.microsoft.com/en-us/library/system.collections.specialized.stringcollection.aspx –
क्या कोई स्ट्रिंग डुप्लिकेट हो सकती है? क्या आपको पूरे शब्दों/तारों से मिलान करने की आवश्यकता है या क्या यह एक स्ट्रिंग के भीतर निहित हो सकता है? –