दिलचस्प पोस्ट
एंड्रॉइड कैमरा इन्टेंट सेविंग इमेज लैंडस्केप जब ले लिया पोर्ट्रेट सामान्य मानचित्रण गलत तरीके से चले गए पीजी अपरिभाषित त्रुटि संबंध उपयोगकर्ता मौजूद नहीं है कैसे सी # में एक धागा समाप्त करने के लिए? नोडजेएस और एक्सप्रेस के साथ एन्जेलरजेएस एचटीआर 5 मेोड का उपयोग करना पोर्टेबल कोड को सी ++ में कैसे लिखें? बैश बैकल्टी के बैच समकक्ष एक तेज चलती छवि स्लाइड शो बनाने के लिए जावास्क्रिप्ट? स्पष्ट कैश के साथ window.location.reload कैसे WebLogic पर JNDI संसाधनों को देखने के लिए? यूटीसी डेटटाइम्स को विश्व स्तर पर स्थानीय डेटटाइम्स निर्दिष्ट करने के लिए परिवर्तित करें एक सामान्य पैरामीटर के रूप में संभव है? जावास्क्रिप्ट / जेक्यू पेज पुनः लोड होने तक काम नहीं कर रहा है WPF में डमी डिजाइन समय डेटा के लिए कौन से दृष्टिकोण उपलब्ध हैं? परम्परागत रूप से "System.Collections.Generic.IEnumerable" टाइप कर सकते हैं, नहीं करने के लिए: System.Collections.Generic.List <string>

स्मृति आवंटन की समय की जटिलता

नई, मॉलोक इत्यादि का उपयोग करके गतिशील स्मृति आवंटन की समय की जटिलता क्या है? मुझे पता है कि मेमोरी आवर्तक कैसे कार्यान्वित किए जाते हैं, इसके बारे में मैं बहुत कम जानता हूं, लेकिन मेरा मान है कि यह कार्यान्वयन पर निर्भर करता है। इसलिए, कृपया कुछ सामान्य मामलों / कार्यान्वयन के लिए उत्तर दें।

संपादित करें: मैं थोड़ा सुनवाई याद रखता हूं कि ढेर आवंटन सबसे खराब स्थिति में असीम है, लेकिन मैं वास्तव में सामान्य / सामान्य मामले में दिलचस्पी रहा हूँ।

Solutions Collecting From Web of "स्मृति आवंटन की समय की जटिलता"

ओ नोटेशन से निपटने के दौरान आपको यह पता चलना चाहिए कि एन क्या है, यह समझना अक्सर बहुत महत्वपूर्ण होता है। यदि n कुछ ऐसी चीज़ से संबंधित है जिसे आप नियंत्रित कर सकते हैं (जैसे: एक सूची में तत्वों की संख्या जिसे आप सॉर्ट करना चाहते हैं) तो यह उस पर कड़ी मेहनत करने के लिए समझ में आता है।

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

यही कारण है कि कठिन वास्तविक समय प्रोग्रामर गतिशील आवंटन (स्टार्टअप के बाद) से बचने की कोशिश करते हैं।

एक ढेर आवंटक के लिए समय की जटिलता अलग-अलग प्रणालियों पर अलग-अलग हो सकती है, इस बात पर निर्भर करता है कि वे किसके लिए अनुकूलित कर सकते हैं।

डेस्कटॉप सिस्टम पर, ढेर आवंटक शायद अलग-अलग रणनीतियों के मिश्रण का उपयोग करता है जिसमें हालिया आवंटन, सामान्य आवंटन आकार के लिए लुकसाइड सूचियां, निश्चित आकार विशेषताओं के साथ मेमोरी खंड की डिब्बे आदि का उपयोग होता है। आवंटन का समय कम रखने की कोशिश करने के लिए, उपयोग की जाने वाली विभिन्न तकनीकों के अवलोकन के लिए डग ली के मॉलोक कार्यान्वयन के नोट्स देखें: http://g.oswego.edu/dl/html/malloc.html

सरल प्रणालियों के लिए, पहली फिट या सर्वोत्तम फिट की एक रणनीति का उपयोग किया जा सकता है, एक लिंक्ड सूची में संग्रहित मुक्त ब्लाकों के साथ (जो कि एन को मुफ्त ब्लॉकों की संख्या के साथ ओ (एन) का समय देगा)। लेकिन ओ (लॉग एन) समय ( http://www.oocities.org/wkaras/heapmm/heapmm.html ) में मुफ्त ब्लॉकों का पता लगाने में सक्षम होने के लिए एवीएल ट्री जैसे एक अधिक परिष्कृत भंडारण प्रणाली का उपयोग किया जा सकता है।

एक रीयलटाइम सिस्टम टीएएलएसएफ (दो स्तरीय पृथक फ़िट) जैसे एक ढेर आवंटक का उपयोग कर सकता है, जिसमें ओ (1) आवंटन लागत है: http://www.gii.upv.es/tlsf/

मुझे लगता है कि यह आम तौर पर ओ (एन) होगा जहां n उपलब्ध स्मृति ब्लॉकों की संख्या है (क्योंकि आपको उपयुक्त मेमोरी ब्लॉकों को उपयुक्त खोजने के लिए स्कैन करना है)।

मैंने कहा कि मैंने अनुकूलन देखा है जो इसे तेजी से बना सकते हैं, विशेष रूप से उनके आकार के स्तर के आधार पर उपलब्ध ब्लॉकों की कई सूचियों को बनाए रखते हुए (1k से कम ब्लॉक एक सूची में हैं, 1k से 10k तक ब्लॉक दूसरे सूची में हैं और इसी तरह )।

यह अभी भी ओ (एन) है, बस एक छोटे एन के साथ।

मुझे अपने स्रोत को देखने में दिलचस्पी होगी कि एक ढेर आवंटन है जो असीम है (यदि, इसका मतलब है, यह हमेशा के लिए ले सकता है)

बस देखें कि सामान्य आवर्तक कैसे कार्य करते हैं

एक टक्कर-द-पॉइंटर ऑलोकेटर ओ (1) में काम करता है, और यह उस पर एक छोटा ' 1 ' है

एक अलग-स्टोरेज ऑलोकेटर के लिए, के बाइट्स के आवंटन का मतलब है "सूची ( एन ) से पहले ब्लॉक लौटें" जहां सूची ( एन ) एन बाइट्स के ब्लॉक की सूची है जहां n> = k यह सूची ( एन ) खाली है, ताकि अगली सूची (लिस्ट ( 2n )) के ब्लॉक को सूची ( एन ) पर रखा जा रहा एन बाइट्स के परिणामस्वरूप ब्लॉकों के साथ विभाजित करना पड़ेगा, और यह प्रभाव लहर सकता है सभी अबायनीय आकारों के माध्यम से, ओ (एनएस) की एक जटिलता के लिए, जहां एनएस अलग-अलग आकारों की संख्या है, और एनएस = लॉग (एन) जहां एन सबसे बड़ा ब्लॉक आकार का आकार है, इसलिए भी यह छोटा होगा ज्यादातर मामलों में, विशेषकर कई ब्लाकों को आवंटित और वितरित किए जाने के बाद, जटिलता हे (1) है

बस दो टिप्पणी:

  • टीएलएसएफ ओ (1) उस अर्थ में है जिसमें एक भी लूप नहीं है; और 2 जीबी तक का प्रबंधन करता है हालांकि यह वास्तव में विश्वास करना कठिन है, बस कोड की जांच करें

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