स्ट्रिंग आपरेशन अनुकूलन

Question

निम्नलिखित सी # कोड 5 मिनट लगते हैं चलाने के लिए:

int i = 1; 
string fraction = ""; 
while (fraction.Length < 1000000) 
{ 
    fraction += i.ToString(); 
    i++; 
} 

"यह अनुकूलन" इस का कारण बनता है जैसे कि यह 1.5 सेकंड में चलाने के लिए:

int i = 1; 
string fraction = ""; 
while (fraction.Length < 1000000) 
{ 
    // concatenating strings is much faster for small strings 
    string tmp = ""; 
    for (int j = 0; j < 1000; j++) 
    { 
     tmp += i.ToString(); 
     i++; 
    } 
    fraction += tmp; 
} 

संपादित करें: कुछ लोगों ने StringBuilder का उपयोग करने का सुझाव दिया, जो कि एक उत्कृष्ट सुझाव भी है, और यह 0.06s:

int i = 1; 
StringBuilder fraction = new StringBuilder(); 
while (fraction.Length < 1000000) 
{ 
    fraction.Append(i); 
    i++; 
} 

पर आता है

j का इष्टतम मूल्य खोजने के लिए चारों ओर बजाना एक और समय है, लेकिन यह गैर-स्पष्ट अनुकूलन वास्तव में क्यों काम करता है? साथ ही, संबंधित विषय पर, मैंने सुना है कि आपने string.Format() के पक्ष में स्ट्रिंग के साथ + ऑपरेटर का कभी भी उपयोग नहीं करना चाहिए, क्या यह सच है?

Answer 1

आप शायद देखेंगे कि पहले 1000 वर्णों में पिछले 1000 वर्णों का विरोध करने में लगभग कोई समय नहीं लगेगा।

मुझे लगता है कि समय लेने वाली हिस्सा एक नया मेमोरी-क्षेत्र में बड़े स्ट्रिंग की वास्तविक नकल यदि आप एक चार आपके कंप्यूटर के लिए एक कठिन कार्य है कि जोड़ने हर बार है।

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

यदि आपने शुरुआत से उचित आकार के साथ एक चार-सरणी परिभाषित की होगी, तो शायद यह तेजी से चमक रहा होगा, क्योंकि तब इसे बार-बार कॉपी करने की आवश्यकता नहीं होगी।

Answer 2

(लगभग) 5 स्ट्रिंग्स (परिणाम थोड़ा भिन्न हो सकते हैं) को संगत करने के लिए StringBuilder का उपयोग करें। इसके अलावा, स्ट्रिंगबिल्डर के कन्स्ट्रक्टर को अपेक्षित अधिकतम आकार पर संकेत दें।

[अपडेट]: केवल प्रश्न में आपके संपादन पर टिप्पणी करें। तुम भी StringBuilder के प्रदर्शन को बढ़ा सकते हैं अगर आप श्रेणीबद्ध तार के अंतिम आकार की एक अनुमानित (या सटीक) पता नहीं है, क्योंकि इस यह प्रदर्शन करने के लिए है स्मृति आवंटन की संख्या कम हो जाएगा:

// e.g. Initialise to 10MB 
StringBuilder fraction = new StringBuilder(10000000); 

Answer 3

इसके अलावा, एक संबंधित विषय पर, मैंने सुना है कि यह स्ट्रिंग के पक्ष में स्ट्रिंग के साथ + ऑपरेटर का कभी भी उपयोग नहीं करना चाहिए। फोर्मैट(), क्या यह सच है?

नहीं, सभी पूर्ण बयानों की तरह यह बकवास है। हालांकि, यह है कि Format का उपयोग करके आम तौर पर स्वरूपण कोड अधिक पठनीय बनाता है और यह अक्सर संयोजन से थोड़ा तेज़ होता है - लेकिन गति यहां निर्णायक कारक नहीं है।

आपके कोड के लिए ... इसके परिणामस्वरूप छोटे तारों को कॉपी किया जा रहा है (अर्थात्, tmp) संगतता में। बेशक, fraction += tmp में आप एक बड़ी स्ट्रिंग की प्रतिलिपि बनाते हैं लेकिन यह अक्सर कम होता है।

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

हम्म, मैंने अभी देखा है कि आपके बाहरी लूप दोनों मामलों में एक ही आकार का है। यह तब तेज नहीं होना चाहिए।

Answer 4

अब मैं परीक्षण नहीं कर सकता, लेकिन स्ट्रिंगबिल्डर का उपयोग करने का प्रयास करें।

int i = 1; 
    StringBuilder fraction = new StringBuilder(); 
    while (fraction.Length < 1000000) 
    { 
     fraction.Append(i); 
     i++; 
    } 
return sb.ToString(); 

Answer 5

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

using System; 
using System.Diagnostics; 
using System.Text; 

public class Test 
{ 
    const int Limit = 4000000; 

    static void Main() 
    { 
     Time(Concatenation, "Concat"); 
     Time(SimpleStringBuilder, "StringBuilder as in post"); 
     Time(SimpleStringBuilderNoToString, "StringBuilder calling Append(i)"); 
     Time(CapacityStringBuilder, "StringBuilder with appropriate capacity"); 
    } 

    static void Time(Action action, string name) 
    { 
     Stopwatch sw = Stopwatch.StartNew(); 
     action(); 
     sw.Stop(); 
     Console.WriteLine("{0}: {1}ms", name, sw.ElapsedMilliseconds); 
     GC.Collect(); 
     GC.WaitForPendingFinalizers(); 
    } 

    static void Concatenation() 
    { 
     int i = 1; 
     string fraction = ""; 
     while (fraction.Length < Limit) 
     { 
      // concatenating strings is much faster for small strings 
      string tmp = ""; 
      for (int j = 0; j < 1000; j++) 
      { 
       tmp += i.ToString(); 
       i++; 
      } 
      fraction += tmp;    
     } 
    } 

    static void SimpleStringBuilder() 
    { 
     int i = 1; 
     StringBuilder fraction = new StringBuilder(); 
     while (fraction.Length < Limit) 
     { 
      fraction.Append(i.ToString()); 
      i++; 
     } 
    } 

    static void SimpleStringBuilderNoToString() 
    { 
     int i = 1; 
     StringBuilder fraction = new StringBuilder(); 
     while (fraction.Length < Limit) 
     { 
      fraction.Append(i); 
      i++; 
     } 
    } 

    static void CapacityStringBuilder() 
    { 
     int i = 1; 
     StringBuilder fraction = new StringBuilder(Limit + 10); 
     while (fraction.Length < Limit) 
     { 
      fraction.Append(i); 
      i++; 
     } 
    } 
} 

और परिणाम:

Concat: 5879ms 
StringBuilder as in post: 206ms 
StringBuilder calling Append(i): 196ms 
StringBuilder with appropriate capacity: 184ms 

कारण अपने संयोजन पहले ही समाधान की तुलना में तेजी सरल हालांकि जाता है - आप कई "सस्ते" concatenations कर रहे हैं (जहां अपेक्षाकृत कम डेटा की प्रतिलिपि की जा रही है प्रत्येक बार) और अपेक्षाकृत कुछ "बड़े" concatenations (अब तक पूरी स्ट्रिंग का)। मूल में, प्रत्येक चरण अब तक प्राप्त सभी डेटा की प्रतिलिपि बनायेगा, जो स्पष्ट रूप से अधिक महंगा है।

मैं जो गैर यकीन नहीं है:

Answer 6

संशोधित queston ("क्यों इस अस्पष्ट अनुकूलन काम इतनी अच्छी तरह से करता है" और "यह सच आप तारों पर + ऑपरेटर उपयोग नहीं करना चाहिए है") का जवाब - आप जिस ऑप्टिमाइज़ेशन के बारे में बात कर रहे हैं। लेकिन दूसरे सवाल का जवाब, मुझे लगता है, सभी अड्डों को शामिल करता है।

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

स्ट्रिंगबिल्डर एक मेमोरी बफर का उपयोग करके काम करते हैं जो निश्चित रूप से निश्चित लंबाई के तारों से आवंटित किया जाता है, और इस प्रकार अधिकांश स्थितियों में काफी बेहतर प्रदर्शन करता है। मैं आंतरिक रूप से स्ट्रिंगबिल्डर के विवरण पर निश्चित नहीं हूं, इसलिए आपको इसके लिए एक नया प्रश्न पूछना होगा। मैं यह अटकलें कर सकते हैं या तो स्ट्रिंग के पुराने भागों को पुनः निर्दिष्ट नहीं करता है (बजाय आंतरिक रूप से एक लिंक्ड सूची बनाने और केवल वास्तव में अंतिम आउटपुट जब ToString द्वारा आवश्यक आवंटन) या इसे घातीय वृद्धि के साथ पुनर (जब यह स्मृति से बाहर चलाता है, यह आवंटित अगली बार दोगुनी बार, इस प्रकार 2 जीबी स्ट्रिंग के लिए इसे केवल 30 बार फिर से आवंटित करने की आवश्यकता होगी)।

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

Answer 7

एक स्ट्रिंग के लिए एक चरित्र को जोड़ने से दो परिणाम हो सकते हैं:

• क्या अब भी कोई चरित्र यह सिर्फ अंत में जोड़ा जाता है के लिए जगह है, (जैसा कि एक टिप्पणीकार ने देखा, यह सी # तारों के साथ नहीं हो सकता है, क्योंकि आप अपरिवर्तनीय हैं)।
• यदि अंत में कोई स्थान नहीं है तो नई स्ट्रिंग के लिए स्मृति का एक नया ब्लॉक आवंटित किया जाता है, पुरानी स्ट्रिंग की सामग्री वहां कॉपी की जाती है और चरित्र जोड़ा जाता है।

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

फिर ऐसी स्थिति में जहां कोई अतिरिक्त स्थान आरक्षित नहीं है, पहले उदाहरण को 100 *0000 आवंटन और प्रतियां 0.5 * 1000000 अक्षरों के औसत से करना है। दूसरे को 1000 आवंटन और औसत 0.5 * 1000000 वर्णों की प्रतियां, और 1000000 आवंटन और 0.5 * 1000 वर्णों की प्रतियां करना है। यदि प्रतिलिपि प्रतिलिपि के आकार और आवंटन के आकार के साथ लाइनर है, तो पहली स्थिति समय की 500 000 000 000 इकाइयों और दूसरी 500 000 000 + 500 000 000 इकाइयों को लेती है।