मेरे पास स्ट्रिंग का वेक्टर है और यह जांचना है कि वेक्टर में प्रत्येक तत्व 5000 शब्दों की दी गई सूची में मौजूद है या नहीं। दो नेस्टेड लूपों की सांसारिक विधि के अलावा, क्या सी ++ में ऐसा करने का कोई तेज़ तरीका है?फास्ट स्ट्रिंग खोज?
आपको स्ट्रिंग्स की सूची std::set में रखना चाहिए। यह खोज के लिए अनुकूलित एक डेटा संरचना है। यह पता लगाना कि कोई दिया गया तत्व सेट में है या नहीं, एक ऑपरेशन है जो सभी प्रविष्टियों को फिर से शुरू करने से बहुत तेज़ है।
जब आप पहले से ही C++ 11 का उपयोग कर रहे हैं, तो आप std::unordered_set का भी उपयोग कर सकते हैं जो लुकअप के लिए भी तेज़ है, क्योंकि इसे हैश तालिका के रूप में लागू किया गया है।
यह स्कूल/विश्वविद्यालय के लिए होना चाहिए: यह समझाने के लिए तैयार रहें कि ये डेटा संरचनाएं कैसे तेजी से प्रबंधित होती हैं। जब आपका प्रशिक्षक आपको यह बताने के लिए कहता है कि आपने उनका उपयोग क्यों किया, "इंटरनेट पर कुछ लोगों ने मुझे बताया" कक्षा पुस्तक में आपको स्टिकर कमाने की संभावना नहीं है।
हाहा, नहीं, अगर यह स्कूल के लिए था तो इसका उल्लेख किया होगा। यह एक यूएसको समस्या के लिए मेरे कोड का हिस्सा था। – ofey
आप std::unordered_set में शब्दों की सूची डाल सकते हैं। फिर, वेक्टर में प्रत्येक तत्व के लिए, आपको केवल परीक्षण करना होगा कि यह ओ (1) में unordered_set में है या नहीं। आपके पास ओ (एन) की अपेक्षित जटिलता होगी (यह देखने के लिए टिप्पणी देखें कि इसकी अपेक्षा क्यों की जाती है)।
यह सच नहीं है। प्रत्येक स्ट्रिंग के हैश की गणना की जानी चाहिए, और तारों की तुलना कम से कम एक बार की जानी चाहिए। उनमें से प्रत्येक तारों की कुल संख्या (अपेक्षित मामले में) से स्वतंत्र है, लेकिन यह उल्लेखनीय है। और जबकि सबसे खराब मामला बेहद असंभव है, यह सही रहने के लिए अच्छी शैली है और कहें कि * अपेक्षित * समय ओ (1) है। – delnan
आप पूरी तरह से सही हैं। मैंने परिणाम में अपना जवाब बदल दिया। धन्यवाद। –
आप वेक्टर को सॉर्ट कर सकते हैं, फिर आप इसे "लूप" के साथ हल कर सकते हैं (लिया गया है कि आपका शब्दकोश भी सॉर्ट किया गया है) जिसका अर्थ है ओ (एन) इस तरह की लागत में गिनती नहीं है।
तो आपके पास स्ट्रिंग का वेक्टर है, जिसमें प्रत्येक स्ट्रिंग में एक या अधिक शब्द होते हैं, और आपके पास एक वेक्टर है जो एक शब्दकोश है, और आपको यह निर्धारित करना होगा कि तारों के वेक्टर में कौन से शब्द शब्दकोश में भी हैं? तारों का वेक्टर एक परेशानी है, क्योंकि आपको प्रत्येक शब्द को देखने की आवश्यकता है। मैं एक नया वेक्टर बनाकर शुरू करता हूं, प्रत्येक स्ट्रिंग को शब्दों में विभाजित करता हूं, और प्रत्येक शब्द को नए वेक्टर में दबाता हूं। फिर नए वेक्टर को सॉर्ट करें और डुप्लिकेट को खत्म करने के लिए इसे std::unique एल्गोरिदम के माध्यम से चलाएं। फिर शब्दकोश को सॉर्ट करें। फिर परिणाम लिखने के लिए std::set_intersection के माध्यम से दोनों श्रेणियां चलाएं।
क्या यह एक सूची के बजाय पहले स्थान पर एक सहयोगी कंटेनर को पॉप्युलेट करने का विकल्प है? –
क्या यह 5000 शब्दों की सूची को सॉर्ट करने की संभावना है? यदि हां, तो क्रमबद्ध सूची पर आप वेक्टर में तारों के लिए बाइनरी खोज सकते हैं। – Satyajit
क्या आप स्ट्रिंग को अपने सेट में से किसी एक के * पूर्ण * से मिलान करना चाहते हैं, या यह पर्याप्त है कि सेट * में से एक * वह * है जिसे आप ढूंढ रहे हैं? –