सी ++ - खोज योग्य डेटा की बड़ी मात्रा के लिए कुशल कंटेनर?

Question

मैं एक कॉलेज प्रोजेक्ट के लिए स्क्रैबल के टेक्स्ट-आधारित संस्करण को कार्यान्वित कर रहा हूं।

मेरा शब्दकोश काफी बड़ा है, वजन लगभग 400.000 शब्द (std::string) में है।

यदि मैं vector<string> (ओ (एन)) के लिए जाता हूं तो दक्षता के मामले में एक वैध शब्द खोजना, बड़ा समय चूसना होगा। क्या कोई अच्छा विकल्प है? ध्यान रखें, मैं नए साल में नामांकित हूं। जटिल नहीं कुछ भी!

आपके समय के लिए धन्यवाद!

फ्रांसिस्को

Answer 1

आप कुछ मानक पुस्तकालय में है कि के लिए जाना चाहते थे, तो आप कुंजी के रूप में शब्द के साथ std::set इस्तेमाल कर सकते हैं। यह आपको लॉगरिदमिक खोज समय देगा।

के बाद से अपने शब्दकोश शायद स्थिर है (यानी एक बार और नहीं संशोधित बनाया) है, तो आप भी एक std::vector, तरह यह std::sort का उपयोग कर इस्तेमाल कर सकते हैं, और फिर अनुसार क्रमबद्ध वेक्टर पर std::binary_search का उपयोग एक शब्द खोजने के लिए। यह लॉगरिदमिक खोज समय भी देगा, और संभवतः set से अधिक स्थान कुशल होगा।

यदि आप अपनी खुद की डेटा संरचना को कार्यान्वित करना चाहते हैं, तो एक तिहाई अच्छी पसंद होगी।

Answer 2

std :: सेट इसके लिए एक प्राकृतिक है क्योंकि यह एक वेक्टर का उपयोग करने के शीर्ष पर लगभग 0 कार्य करता है। इसके बावजूद, मैं आपको कुछ ऐसा सिखाऊंगा जो आप आमतौर पर तब तक नहीं सीखते जब तक कि आप पेशेवर न हों। समय से अनुकूलित नहीं है। मैं एक मॉडेन कंप्यूटर पर शर्त लगाता हूं कि एक 40 के स्ट्रिंग वेक्टर में एक रैखिक शब्दकोश लुकअप .001 सेकंड लेता है।

एक सेट में, यह ओ (लॉग एन) है और शायद .00001 सेकंड लेता है।

एसटीएल में कुछ भी नहीं समय की कुल बर्बादी है। 10 प्रतिशत की समस्या पर 10 डॉलर का काम न करें।

Answer 3

यदि वेक्टर सॉर्ट किया गया है, तो आप binary_search का उपयोग करके परीक्षण कर सकते हैं कि कोई शब्दकोष शब्दकोश में मौजूद है या नहीं।

Answer 4

ए trie या radix tree आपको खोज समय और सम्मिलन के समय देगा जो आपको खोज रहे स्ट्रिंग की लंबाई में रैखिक हैं।

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

यदि आपके पास पहले से ही आपकी लाइब्रेरी में नहीं है तो ये समाधान शायद अधिक हो गए हैं।

Answer 5

std::tr1::unordered_set का उपयोग करें, और यह आपको निरंतर समय लुकअप देता है। (स्ट्रिंग की लंबाई में रैखिक, मेरे अन्य उत्तर के अनुसार।)

Answer 6

आपकी डेटा संरचना का उद्देश्य क्या है? आप इसके साथ किस तरह की चीजें करना चाहते हैं?

• जांचें कि "tempest" जैसे पूरा शब्द सूची में है या नहीं?
• "टी" से शुरू होने और समाप्त होने वाले सभी सात अक्षर शब्द खोजें?
• "टी" के साथ शुरू होने और समाप्त होने वाले सभी सात अक्षर शब्द खोजें जो अक्षरों के दिए गए सेट के साथ किए जा सकते हैं?

पहला सवाल यह है कि यदि आप मानव खिलाड़ियों के समूह के लिए कुछ प्रकार के रेफरी को लागू कर रहे हैं, तो कुछ आधिकारिक शब्दकोश के खिलाफ प्रस्तावित शब्दों की जांच करने के लिए कुछ इकाई है। std::map, std::set, std::vector जैसे बुनियादी डेटा संरचनाएं, पहले से ही इस उद्देश्य के लिए पर्याप्त रूप से दूसरों द्वारा सुझाई गई हैं।

दूसरे और तीसरे प्रश्न इस प्रकार हैं कि आपको एक खिलाड़ी लिखने पर आपको उत्तर देने की आवश्यकता है। यहां आप प्रत्येक पत्र की स्थिति के लिए 26 सेटों पर विचार करना चाहेंगे, प्रत्येक सेट किसी दिए गए पद में किसी दिए गए पत्र के साथ शब्दों को धारण कर सकता है। आवश्यकता होने पर चौराहे की गणना करने के लिए आपको अतिरिक्त कोड की आवश्यकता होगी, और शायद आपके रैक पर उपलब्ध अक्षरों के खिलाफ शब्दों की जांच करें।

अद्यतन: मूल प्रश्न पर एक टिप्पणी में, ओपी ने यह स्पष्ट किया कि उसे केवल यह जांचना है कि शब्दकोष शब्द में है या नहीं। मैंने ऊपर पूछा पहला सवाल है, और मानक मानक डेटा संरचनाओं में से कोई भी ठीक है।

Answer 7

मैंने कुछ प्रोफाइलिंग किया और निम्नलिखित परिणाम प्राप्त किए (एमएसवीएस 2008,/ओ 2, रिलीज बिल्ड, लॉन्चिंग .exe अलग से)।

संपादित करें - अब मुझे एहसास है कि मैं वास्तव में अपने पहले टेस्ट को सीकेड कर चुका हूं, क्योंकि मैंने इमारत और खोज परीक्षण को विभाजित नहीं किया था। हालांकि यह "विजेताओं" को नहीं बदला, मैंने कुछ नए परीक्षण किए। तो, जब हम उन्हें विभाजित करते हैं तो परिणाम यहां दिए गए हैं।

सबसे पहले, अगर लगभग कोई बुरा खोज अनुरोध (4 मिलियन अच्छे खोज प्रयास) हैं।

[ RUN  ] Containers.DictionaryPrepare 
[  OK ] Containers.DictionaryPrepare (234 ms) 
[ RUN  ] Containers.VectorPrepare 
[  OK ] Containers.VectorPrepare (704 ms) 
[ RUN  ] Containers.SetPrepare 
[  OK ] Containers.SetPrepare (593 ms) 
[ RUN  ] Containers.MultisetPrepare 
[  OK ] Containers.MultisetPrepare (578 ms) 
[ RUN  ] Containers.UnorderedSetPrepare 
[  OK ] Containers.UnorderedSetPrepare (266 ms) 
[ RUN  ] Containers.UnorderedMultisetPrepare 
[  OK ] Containers.UnorderedMultisetPrepare (375 ms) 
[ RUN  ] Containers.VectorSearch 
[  OK ] Containers.VectorSearch (4484 ms) 
[ RUN  ] Containers.SetSearch 
[  OK ] Containers.SetSearch (5469 ms) 
[ RUN  ] Containers.MultisetSearch 
[  OK ] Containers.MultisetSearch (5485 ms) 
[ RUN  ] Containers.UnorderedSet 
[  OK ] Containers.UnorderedSet (1078 ms) 
[ RUN  ] Containers.UnorderedMultiset 
[  OK ] Containers.UnorderedMultiset (1250 ms) 
[----------] 11 tests from Containers (20516 ms total) 

इस रूपरेखा से पता चलता है कि आप के बजाय "बहु" "सामान्य" कंटेनर रूपों का उपयोग करना चाहिए, और आप unordered_set चयन करना चाहिए। समय और खोज संचालन के समय में यह बहुत अच्छा है।

यहाँ एक और मामले (लगता है कि इसे अपने ऐप्लिकेशन के बारे में नहीं है, लेकिन सिर्फ यह होने के लिए), जब बुरा खोजों की राशि अच्छा खोजें की राशि के बराबर होती है (और 2 लाख के बराबर होती है) के लिए परिणाम हैं। विजेता वही रहता है।

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

[ RUN  ] Containers.DictionaryPrepare 
[  OK ] Containers.DictionaryPrepare (235 ms) 
[ RUN  ] Containers.VectorPrepare 
[  OK ] Containers.VectorPrepare (718 ms) 
[ RUN  ] Containers.SetPrepare 
[  OK ] Containers.SetPrepare (578 ms) 
[ RUN  ] Containers.MultisetPrepare 
[  OK ] Containers.MultisetPrepare (579 ms) 
[ RUN  ] Containers.UnorderedSetPrepare 
[  OK ] Containers.UnorderedSetPrepare (265 ms) 
[ RUN  ] Containers.UnorderedMultisetPrepare 
[  OK ] Containers.UnorderedMultisetPrepare (375 ms) 
[ RUN  ] Containers.VectorSearch 
[  OK ] Containers.VectorSearch (3375 ms) 
[ RUN  ] Containers.SetSearch 
[  OK ] Containers.SetSearch (3656 ms) 
[ RUN  ] Containers.MultisetSearch 
[  OK ] Containers.MultisetSearch (3766 ms) 
[ RUN  ] Containers.UnorderedSet 
[  OK ] Containers.UnorderedSet (875 ms) 
[ RUN  ] Containers.UnorderedMultiset 
[  OK ] Containers.UnorderedMultiset (1016 ms) 
[----------] 11 tests from Containers (15438 ms total) 

परीक्षण कोड:

TEST(Containers, DictionaryPrepare) { 
    EXPECT_FALSE(strings_initialized); 
    for (size_t i = 0; i < TOTAL_ELEMENTS; ++i) { 
     strings.push_back(generate_string()); 
    } 
} 

TEST(Containers, VectorPrepare) { 
    for (size_t i = 0; i < TOTAL_ELEMENTS; ++i) { 
     vec.push_back(strings[i]); 
    } 
    sort(vec.begin(), vec.end()); 
} 

TEST(Containers, SetPrepare) { 
    for (size_t i = 0; i < TOTAL_ELEMENTS; ++i) { 
     set.insert(strings[i]); 
    } 
} 

TEST(Containers, MultisetPrepare) { 
    for (size_t i = 0; i < TOTAL_ELEMENTS; ++i) { 
     multiset.insert(strings[i]); 
    } 
} 

TEST(Containers, UnorderedSetPrepare) { 
    for (size_t i = 0; i < TOTAL_ELEMENTS; ++i) { 
     uo_set.insert(strings[i]); 
    } 
} 

TEST(Containers, UnorderedMultisetPrepare) { 
    for (size_t i = 0; i < TOTAL_ELEMENTS; ++i) { 
     uo_multiset.insert(strings[i]); 
    } 
} 

TEST(Containers, VectorSearch) { 
    for (size_t i = 0; i < TOTAL_SEARCHES; ++i) { 
     std::binary_search(vec.begin(), vec.end(), strings[rand() % TOTAL_ELEMENTS]); 
    } 
    for (size_t i = 0; i < TOTAL_BAD_SEARCHES; ++i) { 
     std::binary_search(vec.begin(), vec.end(), NONEXISTENT_ELEMENT); 
    } 
} 

TEST(Containers, SetSearch) { 
    for (size_t i = 0; i < TOTAL_SEARCHES; ++i) { 
     set.find(strings[rand() % TOTAL_ELEMENTS]); 
    } 
    for (size_t i = 0; i < TOTAL_BAD_SEARCHES; ++i) { 
     set.find(NONEXISTENT_ELEMENT); 
    } 
} 

TEST(Containers, MultisetSearch) { 
    for (size_t i = 0; i < TOTAL_SEARCHES; ++i) { 
     multiset.find(strings[rand() % TOTAL_ELEMENTS]); 
    } 
    for (size_t i = 0; i < TOTAL_BAD_SEARCHES; ++i) { 
     multiset.find(NONEXISTENT_ELEMENT); 
    } 
} 

TEST(Containers, UnorderedSet) { 
    for (size_t i = 0; i < TOTAL_SEARCHES; ++i) { 
     uo_set.find(strings[rand() % TOTAL_ELEMENTS]); 
    } 
    for (size_t i = 0; i < TOTAL_BAD_SEARCHES; ++i) { 
     uo_set.find(NONEXISTENT_ELEMENT); 
    } 
} 

TEST(Containers, UnorderedMultiset) { 
    for (size_t i = 0; i < TOTAL_SEARCHES; ++i) { 
     uo_multiset.find(strings[rand() % TOTAL_ELEMENTS]); 
    } 
    for (size_t i = 0; i < TOTAL_BAD_SEARCHES; ++i) { 
     uo_multiset.find(NONEXISTENT_ELEMENT); 
    } 
} 

Answer 8

मैं शब्द की लंबाई और खोज में पहले दो आइटम के रूप में पहले अक्षर का उपयोग करें। डेटा को इस एल्गोरिदम का समर्थन करने के लिए व्यवस्थित करने दें। ताकि एक द्विआधारी खोज का उपयोग किया जा सकता है,

typedef std::vector<std::string> Word_Container; 

इस डेटा संरचना हल कर दी जाएगी:

पहले, हमें सभी शब्दों है कि समान अवधि वाले एक कंटेनर को परिभाषित करते हैं।

अगला, एक अनुक्रमणिका तालिका बनाई जाएगी। सूचकांक तालिका के रूप में < शब्द लंबाई, शब्द कंटेनर> सूचक होगा:

typedef std::map<unsigned int, Word_Container *> Index_Table; 

और अंत में सूचकांक तालिकाओं की एक सरणी है, एक सूचकांक के रूप में शब्द के पहले अक्षर का उपयोग कर:

Index_Table alpha_array[26]; // ASCII A - Z. 

एल्गोरिथ्म तो है:
alpha_array में की गणना सूचकांक:
index = word[0] - 'A';

उपयोग सूचकांक जुड़ने की सूचकांक तालिका: सटीक शब्द
Word_Container * p_word_container = table[word.length()];

खोजें कंटेनर: टेबल देखने के लिए कुंजी के रूप में शब्द के
Index_Table& table = alpha_array[index];

उपयोग लंबाई, शब्द कंटेनर पाने के लिए

bool found = false; 
if (p_word_container) 
{ 
    found = std::binary_search(p_word_container->begin(), p_word_container->end(), word); 
} 

एक शब्द के लिए शब्दकोश खोजने के लिए और अधिक कुशल, लेकिन जटिल, तरीके हैं। उपरोक्त एल्गोरिदम को त्वरित "बचने" बिंदुओं का लाभ होता है जहां शब्द मौजूद नहीं है। इस अवधारणा को डेटाबेस टेबल तक बढ़ाया जा सकता है।

Answer 9

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