2012-04-11 29 views
6

संभव डुप्लिकेट पाते हैं:
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::findstd::memmem उपयोग नहीं करता है? और यह अन्य कार्यान्वयन के साथ अलग है?

प्रश्न यह नहीं है: इस फ़ंक्शन का सबसे अच्छा कार्यान्वयन क्या है? सी ++ के लिए बहस करना वाकई मुश्किल है, अगर यह सी से धीमा है तो इससे कोई फर्क नहीं पड़ता कि दोनों कार्यान्वयन धीमे हो जाएंगे। यह प्रदर्शन अंतर है जो वास्तव में दर्द होता है।

+0

@ फ्रैरिचराबे: आपका सही है, दो प्रश्नों में कुछ ओवरलैप है। लेकिन मेरे प्रश्न अधिक विशिष्ट हैं, और दूसरा लेख उनमें से कोई भी जवाब नहीं देता है। – nosid

+0

@ नोसिड: हाँ यह करता है। औसत-मामले बनाम सबसे खराब मामले और अंतरिक्ष-जटिलता के बारे में dietmar kuhl द्वारा टिप्पणियों में अतिरिक्त स्पष्टीकरण के लिए विशेष रूप से देखें, इसका सबसे अधिक उपयोग क्यों नहीं किया जाता है। यदि आप 'std :: memmem' iso को स्क्रैच से एल्गोरिदम लागू करने का पुन: उपयोग करते हैं, तो वे तर्क नहीं बदलते हैं। – KillianDS

उत्तर

2

पहला, memmem क्या है? मैं इसे सी ++ मानक में नहीं ढूंढ सकता, न ही पॉज़िक्स मानक (जिसमें सभी मानक सी फ़ंक्शन शामिल हैं)।

दूसरा, कोई भी माप मान वास्तविक डेटा पर निर्भर करेगा। केएमपी का उपयोग करना, उदाहरण के लिए, कई मामलों में एक निराशा होगी; शायद अधिकांश मामलों में जहां std::string के सदस्य कार्य का उपयोग किया जाता है; आवश्यक तालिकाओं को सेट करने का समय अक्सर से अधिक सीधे एल्गोरिदम के अधिक समय से अधिक होगा। O(m*n) जैसी चीजें बहुत अधिक नहीं होतीं जब स्ट्रिंग की सामान्य लंबाई कम होती है।

+0

मैंने asssumed, कि 'memmem' सी का हिस्सा है, लेकिन स्पष्ट रूप से यह नहीं है। 'memmem'' strcmp 'को' strcmp 'के लिए' strstrmp 'है। हालांकि, मुझे यकीन है कि आप उसे जानते हैं। फिर भी, जैसा कि मैंने पहले ही कुछ बार उल्लेख किया है। सवाल यह नहीं है कि केएमपी एक अच्छी पसंद है।सवाल यह है कि, वे 'strstr' और' std :: string :: find' के लिए पूरी तरह से अलग एल्गोरिदम का उपयोग क्यों कर रहे हैं। – nosid

+0

@nosid शायद क्योंकि अपेक्षित उपयोग पैटर्न अलग है? या क्योंकि विभिन्न लेखकों ने अलग-अलग उपयोग पैटर्न का विशेषाधिकार प्राप्त किया है? मैंने देखा है कि ज्यादातर अनुप्रयोगों में, अधिकांश तार काफी कम हैं, संभवतः एक रेखा से संबंधित सबसे लंबे तारों के साथ। ऐसे तारों के लिए, केएमपी जैसे कुछ का उपयोग शायद निराशाजनक होगा। यदि 'मेममेम' के लेखकों ने सोचा कि सामान्य उपयोग मामले में स्मृति के कई केबी या अधिक के ब्लॉक शामिल होंगे, दूसरी तरफ, यह निश्चित रूप से सार्थक है। –

+0

25.06.2013 के अनुसार, मेरे मानकों के अनुसार: जीसीसी के लिए, स्ट्रिंग :: खोज थोड़ा तेज़ (~ 10%) (x86_64, -march = मूल, एडब्ल्यूएस पर चलाया गया है) - एमएसवीसी 2 के लिए, धीमा धीमा (x86, एसएसई 2 , एएमडी डेस्कटॉप पर)। (पूर्ण अनुकूलन) – Etherealone

संबंधित मुद्दे