बड़ी मात्रा में डेटा के साथ काम करने के लिए वेक्टर कंटेनर में सुधार

लेख "लाइट" पढ़ने की प्रक्रिया में , वेक्टर कंटेनर के कार्यान्वयन ने वेक्टर से निपटने में मेरे अनुभव को याद किया। वास्तव में, मैं इस अनुभव को साझा करना चाहूंगा।



हां, 10,000 तत्वों के एक सरणी आयाम के साथ, तत्व कार्यान्वयन में एक अतिरिक्त सूचक मूर्त असुविधा लाएगा, लेकिन वेक्टर का उपयोग करते समय वास्तविक मेमोरी समस्या पूरी तरह से थोड़ा अलग तरीके से प्रकट होती है।



दरअसल, समस्या नए तत्वों के लिए मेमोरी आवंटित करने में होती है।



हाल के दिनों में, मैंने एक ऐसी परियोजना पर काम किया जिसमें मुझे बड़ी मात्रा में डेटा (लगभग 20-30 हजार तत्व प्रति सरणी, ~ 24 बाइट्स ऑफ़ स्टेटिक प्रति तत्व) संसाधित करना पड़ा। इस वेक्टर के लिए उपयोग करना बहुत सुविधाजनक था। तुरंत एक आरक्षण करें कि परियोजना में, प्रदर्शन एक अड़चन नहीं था।



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



परीक्षण ने हमें पुश_बैक () में ले गया।

परीक्षण के दौरान, मैंने सीखा (एक अधिक समझदार सहकर्मी से) कि वेक्टर में स्मृति को लघुगणकीय रूप से आवंटित किया गया है, अर्थात्:

- यदि इसमें कोई तत्व जोड़ते समय कोई आरक्षित मेमोरी नहीं है, तो आकार * K की मेमोरी आरक्षित है, जहां आकार वेक्टर का वर्तमान आकार है, और K वेक्टर के कार्यान्वयन के आधार पर गुणांक है और आमतौर पर 2 (अधिक विवरण के लिए, उदाहरण के लिए , Alena Sagalaeva देखें)।



इस प्रकार, हम निम्नलिखित प्राप्त करते हैं:

मान लें कि हमारे पास वेक्टर में पहले से ही 1024 तत्व हैं। जब पुश_बैक () कहा जाता है, तो वेक्टर का आकार 2048 तक बढ़ा दिया जाएगा (के = 2 के लिए, सादगी के लिए हम मान लेंगे कि यह हमेशा मामला है), लेकिन वास्तव में केवल 1025 तत्व वहां संग्रहीत किए जाएंगे। बेशक, अतिरिक्त आरक्षित मेमोरी को मुक्त किया जा सकता है, उदाहरण के लिए स्वैप ट्रिक का उपयोग करना, लेकिन यह अधिक सही लगता है कि अतिरिक्त को आवंटित न करें, अर्थात। रिजर्व का उपयोग करें।



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



अंत में, होने के अर्थ के बारे में लंबे विचार-विमर्श के बाद, वेक्टर के सिद्धांतों और स्मृति आवंटन प्रणाली, न्याय की जीत हुई।



आइए अपने वेक्टर पर वापस जाएं, जिसमें पहले से ही 1024 तत्व हैं।

स्पष्टता के लिए, मान लीजिए कि एक तत्व का आकार 16 बाइट्स है।

तब इस तरह के एक वेक्टर द्वारा कब्जा की गई मेमोरी की मात्रा (वेक्टर के ओवरहेड को छोड़कर और तत्वों के गतिशील भाग) 16 किलोबाइट होगी।

चूंकि वेक्टर हमेशा निरंतर स्मृति में स्थित होता है, जब आप दुर्भाग्यपूर्ण 1025 वें तत्व को इसमें जोड़ने की कोशिश करते हैं, तो निम्न होते हैं:

• आकार का एक नया मेमोरी ब्लॉक * K आवंटित किया गया है, अर्थात 32 किलोबाइट
• वेक्टर की सामग्री को इस नए ब्लॉक में कॉपी किया जाता है
• पुराना ब्लॉक नष्ट हो गया है
• हमारा 1025 वां तत्व भौतिक रूप से वेक्टर में जोड़ा जाता है

तो समस्या यह है कि किसी समय में मेमोरी की मात्रा आकार + आकार के बराबर होती है * K व्यस्त है, अर्थात। और पुराने ब्लॉक और नए एक - 48 किलोबाइट हमारे मामले में।

छोटी सूचियों पर यह कोई फर्क नहीं पड़ता है, लेकिन हजारों तत्वों के कई दसियों की सूची के साथ एक समान संचालन की कल्पना करें। रिज़र्व का उपयोग करने से स्थिति नहीं बचती है क्योंकि चित्र लगभग समान है - पुराना ब्लॉक + नया, पुराने वाले की तुलना में थोड़ा बड़ा, कॉपी करना, हटाना - 32 किलोबाइट।

यह भी पता चला कि यह भी "फ्रीज" का कारण था - डेटा की बाद की नकल के साथ बड़ी मात्रा में स्मृति आवंटित करना उल्लेखनीय प्रयास है।



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



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

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



इस प्रकार, मेमोरी के एक बड़े ब्लॉक के साथ काम को छोटे लोगों के एक सेट (1000 तत्वों के कई वैक्टर) के साथ काम करना संभव था।



दृष्टिकोण आदर्श होने का दावा नहीं करता है, लेकिन यह 100% कार्य के साथ सामना करता है।



युपीडी। वास्तव में, मैं टिप्पणियों में हॉलीवुड के कारण को काफी समझ नहीं पा रहा हूं, इसलिए:

1. परियोजना की बारीकियों ने किसी भी तीसरे पक्ष के उपयोग की अनुमति नहीं दी। सभी आवश्यक ढांचे द्वारा प्रदान किए गए थे। उपयुक्त आवश्यकताओं में केवल एक वेक्टर और एक पत्ता था। वेक्टर अधिक सुविधाजनक था क्योंकि हमने केवल प्रोजेक्ट के अंत तक डेटा के ऐसे संस्करणों के साथ काम करने के बारे में सीखा था। इसी कारण से, पहले तो उन्होंने स्मृति के बारे में नहीं सोचा।

2. के रूप में एक वैक्यूम में गोलाकार घोड़ों और टिप्पणियों में बेवकूफों के लिए, मैंने पहले ही ऊपर लिखा था।