स्ट्रिंगबिल्डर-जैसे सी मॉड्यूल में बफर कैसे बढ़ाना है?

Question

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

जाहिर है, बर्बाद जगह और अत्यधिक रीयलोक कॉल के बीच एक व्यापार बंद किया जा सकता है (जिससे अत्यधिक प्रतिलिपि हो सकती है)। मैंने कुछ ट्यूटोरियल/आलेख देखे हैं जो दोगुना करने का सुझाव देते हैं। ऐसा लगता है कि उपयोगकर्ता एक अच्छा प्रारंभिक अनुमान प्रदान करने का प्रबंधन करता है। क्या प्लेटफार्म पर संरेखण आकार के दो या एक से अधिक की कुछ शक्तियों को गोल करने की कोशिश करना उचित है?

क्या कोई जानता है कि जावा या सी # हुड के नीचे क्या करता है?

Answer 1

सी # में स्ट्रिंगबिल्डर द्वारा उपयोग किए जाने वाले आंतरिक बफर को विकसित करने के लिए उपयोग की जाने वाली रणनीति समय के साथ बदल गई है।

इस समस्या को हल करने के लिए तीन मूलभूत रणनीतियां हैं, और उनके पास विभिन्न प्रदर्शन विशेषताएं हैं।

पहले बुनियादी रणनीति है:

• , वर्ण
• आप कमरे समाप्त हो जाता है की एक सरणी बनाने कश्मीर अधिक अक्षर के साथ एक नई सरणी, कुछ निरंतर कश्मीर के लिए पैदा करते हैं।
• पुरानी सरणी को नई सरणी में कॉपी करें, और पुरानी सरणी अनाथ करें।

इस रणनीति यदि स्ट्रिंग निर्माण किया जा रहा बहुत बड़ी है समय में समस्याओं, जिनमें से सबसे स्पष्ट के एक नंबर यह हे है कि (एन) है। मान लें कि के हजारों वर्ण हैं और अंतिम स्ट्रिंग दस लाख वर्ण हैं। आप स्ट्रिंग को 1000, 2000, 3000, 4000, ... पर प्रतिलिपि बनाते हैं और इसलिए 1000 + 2000 + 3000 + 4000 + ... + 999000 वर्णों की प्रतिलिपि बनाते हैं, जो 500 बिलियन वर्णों की प्रतिलिपि के क्रम में बताते हैं!

इस रणनीति में अच्छी संपत्ति है कि "बर्बाद" स्मृति की मात्रा के द्वारा बाध्य है।

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

दूसरी बुनियादी रणनीति

• आप कमरे समाप्त हो जाता है एक सरणी
• बनाओ, कश्मीर% अधिक अक्षर के साथ एक नई सरणी, कुछ निरंतर कश्मीर के लिए पैदा करते हैं।
• पुरानी सरणी को नई सरणी में कॉपी करें, और पुरानी सरणी अनाथ करें।

के% आमतौर पर 100% है; यदि ऐसा है तो इसे "डबल पूर्ण" रणनीति कहा जाता है।

इस रणनीति में अच्छी संपत्ति है कि इसकी amortized लागत ओ (एन) है। मान लीजिए कि अंतिम स्ट्रिंग दस लाख वर्ण है और आप हजारों से शुरू करते हैं। आप 1000, 2000, 4000, 8000, पर प्रतियां बनाते हैं ... और 1000 + 2000 + 4000 + 8000 ... + 512000 वर्णों की प्रतिलिपि बनाते हैं, जो लगभग दस लाख वर्णों की प्रतिलिपि बनाते हैं; काफी बेहतर।

रणनीति में संपत्ति है कि अमूर्त लागत रैखिक कोई फर्क नहीं पड़ता कि आप किस प्रतिशत का चयन करते हैं।

इस रणनीति नकारात्मक पक्ष यह है कि कभी कभी एक प्रति आपरेशन बेहद महंगे है की एक संख्या है, और आप अप्रयुक्त स्मृति में अंतिम स्ट्रिंग की लंबाई की% k अप करने के लिए बर्बाद कर जा सकता है।

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

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

.NET ढांचे में स्ट्रिंग बिल्डर एक डबल-पूर्ण-पूर्ण रणनीति का उपयोग करने के लिए उपयोग किया जाता है; अब यह एक लिंक-सूची-ऑफ-ब्लॉक रणनीति का उपयोग करता है।

Answer 2

यह कार्यान्वयन-विशिष्ट है, the documentation के अनुसार, लेकिन 16 के साथ शुरू होता:

इस कार्यान्वयन के लिए डिफ़ॉल्ट क्षमता 16 है, और डिफ़ॉल्ट अधिकतम क्षमता Int32.MaxValue है।

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

आवंटित स्मृति की मात्रा कार्यान्वयन-विशिष्ट है, और यदि आवश्यक स्मृति की मात्रा अधिकतम क्षमता से अधिक है एक अपवाद (या तो ArgumentOutOfRangeException या OutOfMemoryException) फेंक दिया है।

कुछ अन्य .NET ढांचे की चीजों के आधार पर, मैं वर्तमान क्षमता तक पहुंचने पर प्रत्येक बार इसे 1.1 गुणा करने का सुझाव दूंगा। यदि अतिरिक्त स्थान की आवश्यकता है, तो बस EnsureCapacity के बराबर है जो इसे आवश्यक आकार में मैन्युअल रूप से विस्तारित करेगा।

Answer 3

बफर का विस्तार और अनुबंध करने के साथ काम करते समय, आप जिस महत्वपूर्ण संपत्ति को चाहते हैं वह आपके आकार के एक से अधिक बढ़ने या घटने के लिए है, निरंतर अंतर नहीं।

उस मामले पर विचार करें जहां आपके पास 16 बाइट सरणी है, 128 बाइट्स द्वारा इसका आकार बढ़ाना अधिक है; हालांकि, अगर इसके बजाय आपके पास 40 9 6 बाइट सरणी थी और इसे केवल 128 बाइट्स तक बढ़ा दिया गया था, तो आप बहुत अधिक प्रतिलिपि बना देंगे।

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

Answer 4

सी

को यह अनुवाद मैं शायद एक List<List<string>> सूची maitain होगा।

class StringBuilder 
{ 
    private List<List<string>> list; 

    public Append(List<string> listOfCharsToAppend) 
    { 

     list.Add(listOfCharsToAppend); 
    } 

} 

इस तरह से आप बस सूचियाँ की एक सूची बनाए रखने और अच्छी तरह से आगे मांग बजाय आवंटन स्मृति पर स्मृति का आवंटन कर रहे हैं।

Answer 5

आप आमतौर पर विकास कारक को सुनहरे माध्य (~ 1.6) से थोड़ा छोटा रखना चाहते हैं। जब यह सुनहरा मतलब से छोटा होता है, तो छोड़े गए खंड बाद में अनुरोध को पूरा करने के लिए काफी बड़े होंगे, जब तक कि वे एक-दूसरे के समीप हों। यदि आपका विकास कारक सुनहरा मतलब से बड़ा है, तो ऐसा नहीं हो सकता है।

मैंने पाया कि 1.5 कारक को कम करने के लिए अभी भी काफी अच्छी तरह से काम करता है, और पूर्णांक गणित (size = (size + (size << 1))>>1; में लागू करने के लिए आसान होने का लाभ दिया है - एक सभ्य संकलक के साथ आपको लगता है कि के रूप में (size * 3)/2 लिख सकते हैं, और यह अभी भी चाहिए तेज़ कोड के लिए संकलित)।

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

Answer 6

क्या कोई जानता है कि जावा या सी # हुड के नीचे क्या करता है?

नीचे दिए गए लिंक पर एक नज़र देखने के लिए कि यह कैसे, JDK7 से जावा के StringBuilder में किया है, विशेष रूप से expandCapacity विधि है। http://hg.openjdk.java.net/build-infra/jdk7/jdk/file/0f8da27a3ea3/src/share/classes/java/lang/AbstractStringBuilder.java

Answer 7

.NET ढांचे में सूचीबद्ध इस एल्गोरिदम का उपयोग करता है: यदि प्रारंभिक क्षमता निर्दिष्ट है, तो यह इस आकार का बफर बनाता है, अन्यथा पहले आइटम (आइटम) जोड़े जाने तक कोई बफर आवंटित नहीं किया जाता है, जो आइटम की संख्या के बराबर स्थान आवंटित करता है) जोड़ा गया, लेकिन 4 से कम नहीं। जब अधिक जगह की आवश्यकता होती है, तो यह 2x पिछली क्षमता के साथ नए बफर आवंटित करता है और सभी वस्तुओं को पुराने बफर से नए बफर में कॉपी करता है। इससे पहले स्ट्रिंगबिल्डर ने समान एल्गोरिदम का उपयोग किया था।

.NET 4 में, स्ट्रिंगबिल्डर निर्माता में निर्दिष्ट आकार के प्रारंभिक बफर आवंटित करता है (डिफ़ॉल्ट आकार 16 वर्ण है)। जब आवंटित बफर बहुत छोटा होता है, तो कोई प्रतिलिपि नहीं बनाई जाती है। इसके बजाए यह रिम पर वर्तमान बफर भरता है, फिर स्ट्रिंगबिल्डर का नया उदाहरण बनाता है, जो आकार * MAX (length_of_remaining_data_to_add, MIN (length_of_all_previous_buffers, 8000)) के बफर आवंटित करता है * इसलिए कम से कम शेष शेष डेटा नए बफर और सभी बफर के कुल आकार में फिट बैठता है कम से कम दोगुना है। न्यू स्ट्रिंगबिल्डर पुराने स्ट्रिंगबिल्डर के संदर्भ में रहता है और इसलिए व्यक्तिगत उदाहरण बफर की लिंक्ड सूची बनाता है।