सी # की स्ट्रिंग.इंडेक्सओफ़ इतनी तेजी से कैसे कर सकता है, लूप खोजने के लिए सामान्य से 10 गुना तेज?

Question

मेरे पास एक बहुत लंबी स्ट्रिंग है (60MB आकार में) जिसमें मुझे यह पता लगाना होगा कि '<' और '>' के कितने जोड़े हैं।

 char pre = '!'; 
     int match1 = 0; 
     for (int j = 0; j < html.Length; j++) 
     { 
      char c = html[j]; 
      if (pre == '<' && c == '>') //find a match 
      { 
       pre = '!'; 
       match1++; 
      } 
      else if (pre == '!' && c == '<') 
       pre = '<'; 
     } 

ऊपर कोड मोटे तौर पर 1000 एमएस के लिए मेरे स्ट्रिंग पर चलता है:

---

मैं पहली बार अपने तरीके से कोशिश की है।

---

तो मैं इसके बाद के संस्करण कोड केवल लगभग 150 एमएस के लिए चलाता है string.IndexOf

 int match2 = 0; 
     int index = -1; 
     do 
     { 
      index = html.IndexOf('<', index + 1); 
      if (index != -1) // find a match 
      { 
       index = html.IndexOf('>', index + 1); 
       if (index != -1) 
        match2++; 
      } 
     } while (index != -1); 

उपयोग करने की कोशिश।

---

मैं सोच रहा हूँ जादू कि string.IndexOf रन इतनी तेजी से बनाता है क्या?

कोई भी मुझे प्रेरित कर सकता है?

---

संपादित

ठीक है, @ BrokenGlass के जवाब के अनुसार। मैंने अपने कोड को इस तरह से संशोधित किया कि वे जोड़ी की जांच नहीं करते हैं, इसके बजाय, वे स्ट्रिंग में कितने '<' की जांच करते हैं।

---

 for (int j = 0; j < html.Length; j++) 
     { 
      char c = html[j]; 
      if (c == '>') 
      { 
       match1++; 
      } 
     } 

ऊपर कोड के आसपास 760 एमएस के लिए चलाता है।

---

IndexOf

 int index = -1; 
     do 
     { 
      index = html.IndexOf('<', index + 1); 
      if (index != -1) 
      { 
       match2++; 
      } 
     } while (index != -1); 

उपरोक्त कोड का उपयोग कर के बारे में 132 एमएस के लिए चलाता है। अभी भी बहुत तेज़ है।

---

संपादित 2

के बाद पढ़ा @Jeffrey सैक्स टिप्पणी, मुझे एहसास हुआ कि मैं डीबग मोड के साथ वी.एस. में चल रहा था।

फिर मैंने रिलीज मोड में बनाया और भाग लिया, ठीक है, IndexOf अभी भी तेज़ है, लेकिन यह तेज़ नहीं है।

जोड़ी गिनती के लिए:: 207ms वी.एस. 144ms

सामान्य से एक चार गिनती के लिए: 141ms वी.एस. 111ms

यहाँ परिणाम है।

मेरे अपने कोड का प्रदर्शन वास्तव में बेहतर हुआ था।

---

सबक सीखा है: जब आप बेंचमार्क सामान करते हैं, को रिलीज़ मोड में यह करते हैं!

Answer 1

क्या आप विजुअल स्टूडियो के भीतर से अपना समय चला रहे हैं? यदि ऐसा है, तो आपका कोड अकेले उस कारण के लिए काफी धीमा होगा।

इसके अलावा, आप सेब और संतरे की तुलना में कुछ डिग्री के लिए हैं। दो एल्गोरिदम एक अलग तरीके से काम करते हैं।

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

यहां कुछ कोड है जो आपकी IndexOf विधि के समान तुलना करता है।

int match3 = 0; 
for (int j = 0; j < html.Length; j++) { 
    if (html[j] == '<') { 
     for (; j < html.Length; j++) 
      if (html[j] == '>') 
       match3++; 
    } 
} 

मेरी परीक्षणों में यह वास्तव में IndexOf विधि की तुलना में लगभग 3 गुना तेज है। कारण? स्ट्रिंग्स वास्तव में व्यक्तिगत पात्रों के अनुक्रम के रूप में काफी सरल नहीं हैं। मार्कर, उच्चारण, इत्यादि हैं String.IndexOf उस अतिरिक्त जटिलता को सही तरीके से संभालती है, लेकिन यह एक लागत पर आता है।

Answer 2

मैं string.IndexOf उम्मीद करेंगे चलाने के लिए अपने पहले कोड नमूने की तुलना में कम से कम दो बार के रूप में तेजी से जब से तुम के लिए अपने पुनरावृत्तियों में से प्रत्येक में दोनों आरंभ और अंत चरित्र की जांच (किसी अन्य अनुकूलन नहीं है जो वहाँ से किया जा सकता है के अलावा)। दूसरी तरफ string.IndexOf के साथ आपका कार्यान्वयन केवल प्रारंभ चरित्र को सफलतापूर्वक प्राप्त करने के बाद ही अंतिम चरित्र की जांच करेगा। यह प्रत्येक पुनरावृत्ति पर महत्वपूर्ण संचालन की संख्या में कटौती करता है (एक कम तुलना)।

Answer 3

केवल एक चीज है कि मेरे दिमाग में आता है IndexOf iniside स्ट्रिंग वर्ग के वास्तविक क्रियान्वयन, कि

callvirt System.String.IndexOf 

जो, अगर हम (यह संभव के रूप में ज्यादा के रूप में) परावर्तक की शक्ति का उपयोग फोन में समाप्त होता है है

CompareInfo.IndexOf(..) 

कॉल, जो बजाय सुपर तेजी से खिड़कियों देशी समारोह FindNLSString का उपयोग करें:

Answer 4

यह आपके प्रबंधित कार्यान्वयन और String.IndexOf विधि की तुलना करने की तुलना में थोड़ी सी झूठ है। IndexOf का कार्यान्वयन काफी हद तक देशी कोड है और इसलिए आपके प्रबंधित कार्यान्वयन की तुलना में प्रदर्शन विशेषताओं का एक अलग सेट है। विशेष रूप से देशी कोड टाइप सुरक्षा जांच से बचते हैं, और उनके संबंधित ओवरहेड, जो प्रबंधित एल्गोरिदम में सीएलआर द्वारा इंजेक्शन दिया जाता है।

एक उदाहरण सरणी सूचकांक

char c = html[j]; 

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

ध्यान दें कि यह लाभ पूर्ण नहीं है। जेआईटी इस लूप की बहुत अच्छी तरह से जांच कर सकता है और यह तय कर सकता है कि j कभी भी एक अवैध इंडेक्स नहीं हो सकता है और उत्पन्न देशी कोड में चेक को बढ़ा सकता है (और यह कुछ मामलों में आईआईआरसी में करता है)।

Answer 5

यदि परीक्षण की बजाय एक स्विच स्टेटमेंट का उपयोग करना थोड़ा सा चीजों को गति देता है। यह कोड कभी-कभी मेरी मशीन पर इंडेक्स कोड को धड़कता है।

 int count = 0; 
     bool open = false; 
     for (int j = 0; j < testStr.Length; j++) 
     { 
      switch (testStr[j]) 
      { 
       case '<': 
        open = true; 
        break; 
       case '>': 
        if (open) 
         count++; 

        open = false; 
        break;   
      } 
     }