कौन सा सी # डेटा संरचना स्ट्रिंग्स की एक जोड़ी को सबस्ट्रिंग्स के लिए सबसे कुशलता से खोजने की अनुमति देती है?

Question

मैं एक डेटा संरचना मान के जोड़े के होते हैं जो एक पूर्णांक और दूसरा एक अल्फ़ान्यूमेरिक स्ट्रिंग (जो अंकों के साथ शुरू कर सकते हैं) है, जिनमें से है जिसमें से पहला है:

+--------+-----------------+ 
| Number | Name   | 
+--------+-----------------+ 
| 15  | APPLES   | 
| 16  | APPLE COMPUTER | 
| 17  | ORANGE   | 
| 21  | TWENTY-1  | 
| 291 | 156TH ELEMENT | 
+--------+-----------------+ 

इन की एक तालिका होगा इसमें 100,000 पंक्तियां शामिल हैं।

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

• 1 पर खोज कर 15 APPLES, 16 APPLE COMPUTER, 17 ORANGE, और 291 156TH ELEMENT
• 15 आदर्श लौट 15 APPLES को खोज को संकीर्ण होगा, 291 156TH ELEMENT
• AP15 APPLES और 16 APPLE COMPUTER
• वापस आ जाएगी (, लेकिन आवश्यक नहीं) ELEM291 156TH ELEMENT वापस आ जाएगा।

मैं अंत में int रों तुलना में किया जा रहा है के बाद से दो Dictionary<string, string> रों उपयोग करने के बारे में सोच रहा था string रों के रूप में - पूर्णांक भाग के बाद एक अनुक्रमण किया जाएगा और स्ट्रिंग हिस्सा द्वारा अन्य।

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

आखिरकार सवाल यह है कि पाठ के लिए दो बड़े सूचियों को एक साथ करने के लिए कोई अच्छा प्रदर्शन करने वाला तरीका है?

विफल होने पर, SortedDictionary के बारे में कैसे? प्रदर्शन में वृद्धि हो सकती है लेकिन अभी भी हैश समस्या का समाधान नहीं होगा।

फ्लाई पर रेगेक्स बनाने के बारे में सोचा, लेकिन मुझे लगता है कि यह बहुत अच्छा प्रदर्शन करेगा।

मैं सी # के लिए नया हूं (जावा दुनिया से आ रहा हूं) इसलिए मैंने अभी तक LINQ में नहीं देखा है; क्या वह जवाब है?

संपादित करें 18:21 ईएसटी: "नाम" फ़ील्ड में तारों में से कोई भी 12-15 वर्णों से अधिक नहीं होगा, यदि यह आपके संभावित समाधान को प्रभावित करता है।

Answer 1

मैं Trie डेटा संरचना का उपयोग करने पर विचार करता हूं।

इसे कैसे प्राप्त करें? पत्तियां आपकी "पंक्ति" का प्रतिनिधित्व करती हैं, लेकिन आपके पास "पंक्ति" के प्रत्येक स्मृति उदाहरण (संख्या के लिए एक और दूसरे नाम के लिए) के "दो पथ" होंगे।

इसके बाद आप अपनी हालत का त्याग कर सकते हैं:

(ideally, but not required) ELEM will return 291 156TH ELEMENT. 

या अपने पंक्ति उदाहरणों के लिए और भी रास्तों प्रदान करते हैं।

Answer 2

यदि संभव हो, तो मैं स्मृति में सभी 100,000 प्रविष्टियों को लोड करने से बचूंगा। मैं मूल्यों को अनुक्रमणित करने के लिए या तो डेटाबेस या Lucene.Net का उपयोग करूंगा। फिर परिणामों की कुशलतापूर्वक खोज करने के लिए उपयुक्त क्वेरी वाक्यविन्यास का उपयोग करें।

Answer 3

चूंकि आप शब्दों की शुरुआत की खोज कर रहे हैं, इसलिए कुंजी आधारित संग्रह काम नहीं करेंगे, जब तक कि आप "ए", "एपी", "ऐप", "सेब", "सेब जैसे शब्दों के सभी संभावित टुकड़े स्टोर न करें "।

मेरा सुझाव एक बाइनरी खोज के साथ System.Collections.Generic.List<T> का उपयोग करना है। आपको अपना खुद का IComparer<T> प्रदान करना होगा, जो शब्दों की शुरुआत भी पाता है। आप दो डेटा संरचनाओं का उपयोग करेंगे।

एक List<KeyValuePair<string,int>> एकल शब्द या संख्या को कुंजी के रूप में और संख्या के रूप में संख्या को पकड़ना।

एक Dictionary<int,string> पूरा नाम धारण करना।

आप इस तरह आगे बढ़ना होगा:

1. एक शब्द में अपने वाक्य (पूरे नाम) विभाजित करें।

2. उन्हें KeyValuePair के मान के रूप में शब्द और संख्या के साथ सूची में जोड़ें।

3. कुंजी में और KeyValuePair के मान के रूप में सूची में नंबर जोड़ें।

4. जब सूची भर जाती है, तो बाइनरी खोज की अनुमति देने के लिए सूची को क्रमबद्ध करें। एक शब्द का एक शुरुआत के लिए

खोज: अपने IComparer<T> साथ संयोजन के रूप में BinarySearch का उपयोग करके सूची में

1. खोजें।

2. खोज से प्राप्त होने वाली अनुक्रमणिका शायद लागू होने वाली पहली नहीं हो सकती है, इसलिए जब तक आपको मेल खाने वाली पहली प्रविष्टि न मिल जाए तब तक सूची में वापस जाएं।

3. सूची में मूल्य के रूप में संग्रहीत संख्या का उपयोग करके, इस नंबर का उपयोग कुंजी के रूप में शब्दकोश में पूरा नाम देखें।