रीलॉक बनाम लिंक्ड लिस्ट स्कैनिंग

Question

मुझे किसी फ़ाइल से अज्ञात संख्या में एक पंक्ति से पढ़ना है और उन्हें एक संरचना में सहेजना है (मैं तत्वों की कुल संख्या को गिनने के लिए एक प्रीकोसिंग से बचना चाहता हूं)। पढ़ने के चरण के बाद मुझे इन पंक्तियों के प्रत्येक तत्व पर कुछ गणना करना है।

1. उपयोग realloc हर बार मैं एक पंक्ति पढ़ते हैं:

   मैं दो तरीकों से पता लगा। इस तरह आवंटन चरण धीमा है लेकिन गणना चरण सूचकांक पहुंच के लिए आसान है।

2. प्रत्येक बार जब मैं पंक्ति पढ़ता हूं तो एक लिंक्ड सूची का उपयोग करें। इस तरह आवंटन चरण तेज है लेकिन गणना चरण धीमा है।

जटिलता बिंदु से बेहतर क्या है?

Answer 1

आप कितनी बार लिंक की गई सूची को पार करेंगे? यदि यह केवल एक बार लिंक-सूची के लिए जाता है। कुछ और चीजें: विला में बहुत सारे आवंटन होंगे? चलो कुछ छोटे बफर बना सकते हैं चलो 10 लाइनें कहें और उन लोगों को लिंक करें। लेकिन यह प्रोफाइलिंग का एक सवाल है।

मैं सबसे सरल चीज पहले करता हूं और देखता हूं कि यह केवल मेरी ज़रूरतों को फिट करता है तो मैं अनुकूलित करने के बारे में सोचूंगा।

कभी-कभी एक इष्टतम के बारे में सोचने में बहुत अधिक समय बर्बाद करता है, भले ही दूसरा सबसे अच्छा समाधान पूरी तरह से आवश्यकताओं को फिट करता है।

Answer 2

आप जानकारी का उपयोग करने के तरीके के बारे में अधिक जानकारी के बिना, जटिलता पर टिप्पणी करना थोड़ा मुश्किल है। हालांकि, यहां कुछ विचार हैं:

• यदि आप रीयलोक का उपयोग करते हैं, तो संभवतः "कुछ" और आइटम (प्रत्येक बार एक बार) जोड़ने के लिए पुनर्विक्रय करना बेहतर होगा। आमतौर पर, एक अच्छा एल्गोरिदम प्रत्येक बार आकार को दोगुना करना है।
• यदि आप एक लिंक्ड सूची का उपयोग करते हैं, तो आप एक साधारण पोस्ट-प्रोसेसिंग चरण में पहुंच को तेज कर सकते हैं। आइटम में पॉइंटर्स की एक सरणी आवंटित करें और सूची में प्रत्येक आइटम में सरणी तत्वों को सेट करने के बाद सूची को पार करें।
• यदि आइटम फ़ाइल में एक निश्चित आकार के हैं, तो आप फ़ाइल के अंत तक, आकार निर्धारित करने, आइटम आकार से विभाजित करके और परिणाम प्राप्त करके आकार को पूर्व-गणना कर सकते हैं। यहां तक ​​कि यदि यह एक निश्चित आकार नहीं है, तो संभवतः आप इसे आवश्यक आकार में "बंद" करने के लिए अनुमान के रूप में उपयोग कर सकते हैं और आवश्यक पुनर्विक्रय की संख्या को कम कर सकते हैं।

Answer 3

के रूप में अन्य उपयोगकर्ताओं को पहले से ही कहा है:

समय से पहले अनुकूलन की जड़ सब बुराई

डोनाल्ड नुथ

है मैं realloc का उपयोग कर एक अलग प्रस्ताव है: में सी ++ एसटीएल std::vector कंटेनर हर बार जब कोई ऑब्जेक्ट डाला जाता है और पर्याप्त स्थान उपलब्ध नहीं होता है। बढ़ने का आकार वर्तमान पूर्व-आवंटित आकार पर निर्भर करता है लेकिन कार्यान्वयन विशिष्ट है। उदाहरण के लिए, आप पूर्ववर्ती वस्तुओं की वास्तविक संख्या को बचा सकते हैं। यदि आकार समाप्त हो जाता है, तो आप वर्तमान में आवंटित स्थान की डबल राशि के साथ reallocate पर कॉल करते हैं। मुझे उम्मीद है कि यह कुछ हद तक समझ में आया था!

गुफा निश्चित रूप से है, कि आप वास्तव में उपभोग और आवश्यकता के मुकाबले अधिक जगह आवंटित करेंगे।