संभव डुप्लिकेट पाते हैं:
C++ string::find complexityप्रदर्शन std :: strstr बनाम std :: स्ट्रिंग ::
हाल ही में मुझे पता चला, कि समारोह std::string::find
परिमाण के एक आदेश धीमी है फ़ंक्शन std::strstr
से - लिनक्स पर जीसीसी 4.7 के साथ मेरे पर्यावरण में। प्रदर्शन अंतर तारों की लंबाई और हार्डवेयर वास्तुकला पर निर्भर करता है।
हालांकि, अंतर के लिए एक आसान कारण है: std::string::find
मूल रूप से std::memcmp
को लूप में कॉल करता है - समय जटिलता O(m * n)
के साथ। इसके विपरीत, std::strstr
हार्डवेयर आर्किटेक्चर (उदा। एसएसई निर्देशों के साथ) के लिए अत्यधिक अनुकूलित है और एक अधिक परिष्कृत स्ट्रिंग मिलान एल्गोरिदम (स्पष्ट रूप से Knuth-Morris-Pratt) का उपयोग करता है।
मुझे आश्चर्य हुआ कि भाषा दस्तावेजों (यानी ड्राफ्ट्स एन 32 9 0 और एन 1570) में इन दो कार्यों की समय जटिलताओं को नहीं मिला। मुझे केवल char_traits
के लिए समय जटिलताएं मिली हैं। लेकिन इससे मदद नहीं मिलती है, क्योंकि char_traits
में खोज को सब्सक्राइब करने के लिए कोई फ़ंक्शन नहीं है।
मुझे उम्मीद है कि std::strstr
और memmem
में लगभग समान प्रदर्शन के साथ समान अनुकूलन शामिल हैं। और हाल ही में, मुझे लगता है कि std::string::find
आंतरिक रूप से memmem
का उपयोग करता है।
प्रश्न हैं: कोई अच्छा कारण है, क्यों std::string::find
std::memmem
उपयोग नहीं करता है? और यह अन्य कार्यान्वयन के साथ अलग है?
प्रश्न यह नहीं है: इस फ़ंक्शन का सबसे अच्छा कार्यान्वयन क्या है? सी ++ के लिए बहस करना वाकई मुश्किल है, अगर यह सी से धीमा है तो इससे कोई फर्क नहीं पड़ता कि दोनों कार्यान्वयन धीमे हो जाएंगे। यह प्रदर्शन अंतर है जो वास्तव में दर्द होता है।
@ फ्रैरिचराबे: आपका सही है, दो प्रश्नों में कुछ ओवरलैप है। लेकिन मेरे प्रश्न अधिक विशिष्ट हैं, और दूसरा लेख उनमें से कोई भी जवाब नहीं देता है। – nosid
@ नोसिड: हाँ यह करता है। औसत-मामले बनाम सबसे खराब मामले और अंतरिक्ष-जटिलता के बारे में dietmar kuhl द्वारा टिप्पणियों में अतिरिक्त स्पष्टीकरण के लिए विशेष रूप से देखें, इसका सबसे अधिक उपयोग क्यों नहीं किया जाता है। यदि आप 'std :: memmem' iso को स्क्रैच से एल्गोरिदम लागू करने का पुन: उपयोग करते हैं, तो वे तर्क नहीं बदलते हैं। – KillianDS