नए, मॉलोक इत्यादि का उपयोग कर गतिशील स्मृति आवंटन की समय जटिलता क्या है? मुझे स्मृति आवंटन कैसे कार्यान्वित किया जाता है, इस बारे में बहुत कम पता है, लेकिन मुझे लगता है कि जवाब यह है कि यह कार्यान्वयन पर निर्भर करता है। इसलिए, कृपया कुछ अधिक आम मामलों/कार्यान्वयन के लिए उत्तर दें।स्मृति आवंटन की समय जटिलता
संपादित करें: मुझे अस्पष्टता से याद रखना याद है कि ढेर आवंटन सबसे खराब मामले में असंबद्ध है, लेकिन मुझे औसत/सामान्य मामले में वास्तव में रूचि है।
ओ नोटेशन से निपटने के दौरान आपको जो कुछ पता होना है, वह यह है कि यह समझना अक्सर महत्वपूर्ण होता है कि n क्या है। यदि n कुछ ऐसी चीज़ से संबंधित है जिसे आप नियंत्रित कर सकते हैं (उदाहरण: उस सूची में तत्वों की संख्या जिसे आप सॉर्ट करना चाहते हैं) तो इसे समझना समझ में आता है।
अधिकांश ढेर कार्यान्वयन में, आपके n प्रबंधक की हैंडलिंग की स्मृति के संगत भाग की संख्या है। यह निश्चित रूप से ग्राहक नियंत्रण के तहत कुछ नहीं है। केवल n क्लाइंट का वास्तव में नियंत्रण है जो वह चाहता है उसकी स्मृति के आकार का आकार है। अक्सर यह आवंटक लेने की अवधि के साथ कोई संबंध नहीं है। एक बड़ी n के रूप में जल्दी के रूप में एक छोटे से n आवंटित किया जा सकता है, या यह बहुत अधिक समय लग सकता है, या यह भी unservicable हो सकता है। यह सब एन के लिए बदल सकता है, इस पर निर्भर करता है कि अन्य ग्राहकों के पिछले आवंटन और विध्वंस कैसे आते हैं। इसलिए वास्तव में, जब तक आप एक ढेर को लागू नहीं कर लेते हैं, तो उचित उत्तर यह है कि यह गैर-निर्धारक है।
यही कारण है कि कठिन वास्तविक समय प्रोग्रामर गतिशील आवंटन (स्टार्टअप के बाद) से बचने के लिए प्रयास करें।
मुझे लगता है कि यह आमतौर पर ओ (एन) होगा जहां n उपलब्ध स्मृति ब्लॉक की संख्या है (क्योंकि आपको उपयुक्त मेमोरी ब्लॉक को स्कैन करना होगा)।
यह कहकर, मैंने ऑप्टिमाइज़ेशन देखा है जो विशेष रूप से उपलब्ध आकारों के आधार पर उपलब्ध ब्लॉकों की कई सूचियों को बनाए रख सकता है (इसलिए 1k से कम ब्लॉक एक सूची में हैं, 1k से 10k तक के ब्लॉक दूसरे में हैं सूची और इतने पर)।
यह अभी भी ओ (एन) है, हालांकि, केवल एक छोटे एन के साथ।
मुझे आपके स्रोत को देखने में दिलचस्पी होगी कि एक ढेर आवंटन है जो असंबद्ध है (यदि, इसका मतलब है, तो इसका मतलब है कि यह हमेशा के लिए ले सकता है)।
हो सकती है एक बहुत * malloc की बुरी * कार्यान्वयन जो बातें चारों ओर ले जाने और एक इष्टतम स्मृति ब्लॉक आवंटित जब ढेर लगभग पूर्ण (एक एन पी-सम्पूर्ण कार्य) है की कोशिश की। सीमित स्मृति में हालांकि इसे अभी भी समाप्त करना चाहिए। –
एक ढेर आवंटक के लिए समय जटिलता विभिन्न प्रणालियों पर अलग हो सकती है, जो कि वे अनुकूलित कर सकते हैं।
डेस्कटॉप सिस्टम पर, ढेर आवंटक शायद आवंटन समय को कम करने की कोशिश करने के लिए हाल ही में आवंटन, सामान्य आवंटन आकारों के लिए लुकसाइड सूचियों, कुछ आकार विशेषताओं के साथ मेमोरी हिस्सों के डिब्बे सहित विभिन्न रणनीतियों के मिश्रण का उपयोग करता है, लेकिन यह भी विखंडन प्रबंधनीय रखें। उपयोग की जाने वाली विभिन्न तकनीकों के एक सिंहावलोकन के लिए डौग ली के मॉलोक कार्यान्वयन के लिए नोट्स देखें: http://g.oswego.edu/dl/html/malloc.html
सरल सिस्टम के लिए, पहले फिट या सर्वोत्तम फिट की रणनीति का उपयोग किया जा सकता है, एक लिंक की गई सूची पर संग्रहीत मुक्त ब्लॉक (जो ओ (एन) समय एन को मुफ्त ब्लॉक की संख्या के साथ देगा)। लेकिन एक अधिक परिष्कृत भंडारण प्रणाली जैसे कि एवीएल पेड़ का उपयोग ओ (लॉग एन) समय (http://www.oocities.org/wkaras/heapmm/heapmm.html) में नि: शुल्क ब्लॉक का पता लगाने में सक्षम होने के लिए किया जा सकता है।
एक वास्तविक समय प्रणाली TLSF की तरह एक ढेर संभाजक (दो स्तर अलग फ़िट), जो एक हे है का उपयोग (1) आवंटन लागत सकता है: http://www.gii.upv.es/tlsf/
कितना ठेठ allocators काम की जाँच करें।
एक टक्कर-सूचक संभाजक हे (1) में काम करता है, और यह है कि कम से एक छोटा सा '' है।
एक अलग भंडारण संभाजक के लिए, कश्मीर बाइट्स के आवंटन का मतलब है जहां सूची (n) n बाइट्स के ब्लॉक की सूची है जहां n> = K "सूची (n) से पहले खंड लौटने"।यह कि सूची पर मिले (n), रिक्त है ताकि अगली सूची में से एक ब्लॉक (सूची (2n)) सूची पर डाल दिया जा रहा है n बाइट्स की दोनों परिणामस्वरूप ब्लॉक के साथ विभाजित करना होगा (n), और सभी availlable आकार के माध्यम से इस आशय पराक्रम लहर, की एक जटिलता के लिए कर रही है ओ (एनएस) जहां एनएस विभिन्न आकारों की संख्या availlable है, और एनएस = लॉग (एन) जहां एन सबसे बड़ा ब्लॉक आकार का आकार उपलब्ध है, तो यह भी छोटा होगा। ज्यादातर मामलों में, विशेष रूप से कई ब्लॉक आवंटित किए जाने और हटाए जाने के बाद, जटिलता ओ (1) है।
सिर्फ दो टिप्पणी:
TLSF है हे (1) भावना है कि है एक एकल पाश नहीं है; और 2 जीबी तक प्रबंधन करता है। हालांकि यह विश्वास करना वाकई मुश्किल है, बस कोड जांचें।
यह सच नहीं है कि "सर्वोत्तम फिट" नीति (तंग ब्लॉक ढूंढें) के लिए सबसे उपयुक्त है छोटे विखंडन प्राप्त करें। यह दावा करने के लिए तुच्छ से बहुत दूर है, वास्तव में यह औपचारिक रूप से साबित नहीं हुआ है लेकिन उस दिशा में बहुत से प्रमाण हैं। (अच्छा शोध विषय)।
काफी। यह हमेशा मुझे लगता है कि सबसे अच्छी नीति सबसे खराब नीति है, और सबसे अच्छी नीति सबसे खराब है। – EJP
डायनामिक मेमोरी आमतौर पर तब आवश्यक होती है जब संसाधित किए जाने वाले डेटा की मात्रा रन टाइम से पहले निर्धारित नहीं की जा सकती है। आवंटित स्मृति आम तौर पर प्रसंस्करण समय में अनुवाद करती है। तो, यह आवंटन के रन टाइम के बारे में इतना कुछ नहीं है, लेकिन पहले स्थान पर हीप मेमोरी की आवश्यकता नहीं होती है। – doppelfish
ठीक है, यह केवल वास्तव में जरूरी है जब ** राशि की ऊपरी सीमा ** रनटाइम से पहले उचित रूप से निर्धारित नहीं की जा सकती है।यदि आप संकलन समय पर राशि को सीमित कर सकते हैं, और आपके पास पर्याप्त रैम है, तो आप अधिकतम को प्रीलोकेट कर सकते हैं। –
आपका मतलब है "उचित उत्तर यह है कि यह अच्छी तरह परिभाषित नहीं है"। "गैर-निर्धारिती" का अर्थ कुछ अलग है। Http://en.wikipedia.org/wiki/Nondeterministic_algorithm –