गतिशील आवंटित सरणी के लिए आदर्श विकास दर क्या है?

Question

सी ++ में std :: वेक्टर है और जावा में ऐरेलिस्ट है, और कई अन्य भाषाओं में गतिशील रूप से आवंटित सरणी का अपना रूप है। जब एक गतिशील सरणी अंतरिक्ष से बाहर हो जाती है, तो इसे बड़े क्षेत्र में फिर से स्थानांतरित किया जाता है और पुराने मानों को नई सरणी में कॉपी किया जाता है। इस तरह के एक सरणी के प्रदर्शन के लिए केंद्रीय प्रश्न यह है कि सरणी आकार में कितनी तेज़ी से बढ़ती है। यदि आप हमेशा मौजूदा धक्का फिट करने के लिए पर्याप्त बड़े होते हैं, तो आप हर बार फिर से आवंटित हो जाएंगे। तो यह सरणी आकार को दोगुना करने के लिए समझ में आता है, या 1.5x कहकर गुणा करें।

क्या कोई आदर्श विकास कारक है? 2x? 1.5x? आदर्श से मेरा मतलब है गणितीय रूप से उचित, सर्वोत्तम संतुलन प्रदर्शन और बर्बाद स्मृति। मुझे एहसास है कि सैद्धांतिक रूप से, यह देखते हुए कि आपके आवेदन में धक्का देने का कोई संभावित वितरण हो सकता है कि यह कुछ हद तक आवेदन निर्भर है। लेकिन मुझे यह जानकर उत्सुकता है कि क्या कोई ऐसा मूल्य है जो "आमतौर पर" सर्वोत्तम होता है, या कुछ कठोर बाधाओं में सर्वश्रेष्ठ माना जाता है।

मैंने सुना है कि इस पर एक पेपर है, लेकिन मैं इसे खोजने में असमर्थ हूं।

Answer 1

यह पूरी तरह से उपयोग के मामले पर निर्भर करेगा। क्या आप समय बर्बाद करने वाले समय (और सरणी को फिर से आवंटित करने) या अतिरिक्त मेमोरी के बारे में अधिक ख्याल रखते हैं? सरणी कब तक चल रही है? यदि यह लंबे समय तक नहीं होने वाला है, तो एक बड़ा बफर का उपयोग करना एक अच्छा विचार हो सकता है - जुर्माना अल्पकालिक रहता है। यदि यह चारों ओर लटकाएगा (उदाहरण के लिए जावा में, पुरानी और पुरानी पीढ़ियों में जा रहा है) जो स्पष्ट रूप से जुर्माना से अधिक है।

"आदर्श विकास कारक" जैसी कोई चीज़ नहीं है। यह सिर्फ सैद्धांतिक रूप से एप्लिकेशन निर्भर नहीं है, यह निश्चित रूप से एप्लिकेशन निर्भर है।

2 एक बहुत ही सामान्य विकास कारक है - मुझे पूरा यकीन है कि ArrayList और List<T> .NET उपयोगों में है। जावा में ArrayList<T> 1.5 का उपयोग करता है।

संपादित करें: जैसा कि एरिच बताता है, Dictionary<,> .NET में "आकार को दोगुना करें, फिर अगले प्राइम नंबर तक बढ़ाएं" ताकि हैश मान बाल्टी के बीच उचित रूप से वितरित किए जा सकें। (मुझे यकीन है कि मैंने हाल ही में दस्तावेज देखा है कि प्राइम्स वास्तव में हैश बाल्टी वितरित करने के लिए बहुत अच्छा नहीं है, लेकिन यह किसी अन्य उत्तर के लिए एक तर्क है।)

Answer 2

मैं जॉन स्कीट से सहमत हूं, यहां तक ​​कि मेरे सिद्धांतक्रेटर मित्र भी जोर देते हैं कि कारक को 2x पर सेट करते समय यह ओ (1) साबित हो सकता है।

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

Answer 3

मुझे कई साल पहले पढ़ना याद है कि क्यों कम से कम 1.5 से अधिक पसंद किया जाता है, कम से कम सी ++ पर लागू होता है (यह शायद प्रबंधित भाषाओं पर लागू नहीं होता है, जहां रनटाइम सिस्टम इच्छाओं पर वस्तुओं को स्थानांतरित कर सकता है)।

तर्क यह है:

1. आप एक 16-बाइट आवंटन के साथ शुरू कहो।
2. जब आपको और आवश्यकता है, तो आप 32 बाइट आवंटित करते हैं, फिर 16 बाइट्स को मुक्त करते हैं। यह स्मृति में 16-बाइट छेद छोड़ देता है।
3. जब आपको और आवश्यकता है, तो आप 32 बाइट्स को मुक्त करने के लिए 64 बाइट आवंटित करते हैं। यह एक 48-बाइट छेद छोड़ देता है (यदि 16 और 32 निकट थे)।
4. जब आपको और आवश्यकता है, तो आप 64 बाइट्स को मुक्त करते हुए 128 बाइट आवंटित करते हैं। यह एक 112-बाइट छेद छोड़ देता है (माना जाता है कि सभी पिछले आवंटन निकट हैं)।
5. और इतने और आगे।

विचार यह है कि, एक 2x विस्तार के साथ, वहाँ समय का कोई मतलब नहीं है कि जिसके परिणामस्वरूप छेद कभी इतना बड़ा अगले आवंटन के लिए पुन: उपयोग करने होने जा रहा है है। 1.5x आवंटन का उपयोग करके, हमारे पास इसके बजाय यह है:

1. 16 बाइट्स से शुरू करें।
2. जब आपको और अधिक चाहिए, तो 24 बाइट आवंटित करें, फिर 16-बाइट छेद छोड़कर 16 को मुक्त करें।
3. जब आपको और अधिक चाहिए, तो 36 बाइट आवंटित करें, फिर 24-बाइट छेद छोड़कर 24 को मुक्त करें।
4. जब आपको और अधिक चाहिए, तो 54 बाइट आवंटित करें, फिर 76-बाइट छेद छोड़कर 36 को मुक्त करें।
5. जब आपको और अधिक चाहिए, तो 81 बाइट आवंटित करें, फिर 130-बाइट छेद छोड़कर 54 को मुक्त करें।
6. जब आपको और आवश्यकता हो, तो 130-बाइट छेद से 122 बाइट्स (गोलाकार) का उपयोग करें।

Answer 4

यह वास्तव में निर्भर करता है। कुछ लोग इष्टतम संख्या खोजने के लिए आम उपयोग के मामलों का विश्लेषण करते हैं।

मैंने 1.5x 2.0x फाई एक्स देखा है, और 2 की शक्ति पहले उपयोग की गई है।

Answer 5

इस तरह के प्रश्नों का उत्तर देने पर एक दृष्टिकोण सिर्फ "धोखाधड़ी" करना है और यह मानना ​​है कि व्यापक पुस्तकालय क्या है, कम से कम, कुछ भयानक काम नहीं कर रहा है।

तो बस बहुत जल्दी जांच कर रहे हैं, रूबी (1.9.1-पी 12 9) एक सरणी में संलग्न होने पर 1.5x का उपयोग करने लगता है, और पायथन (2.6.2) 1.125x प्लस स्थिर का उपयोग करता है: (ऑब्जेक्ट्स/listobject.c में):

/* This over-allocates proportional to the list size, making room 
* for additional growth. The over-allocation is mild, but is 
* enough to give linear-time amortized behavior over a long 
* sequence of appends() in the presence of a poorly-performing 
* system realloc(). 
* The growth pattern is: 0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ... 
*/ 
new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6); 

/* check for integer overflow */ 
if (new_allocated > PY_SIZE_MAX - newsize) { 
    PyErr_NoMemory(); 
    return -1; 
} else { 
    new_allocated += newsize; 
} 

newsize ऊपर सरणी में तत्वों की संख्या है। ध्यान दें कि newsizenew_allocated में जोड़ा गया है, इसलिए बिट्सफ़िफ्ट और टर्नरी ऑपरेटर के साथ अभिव्यक्ति वास्तव में अधिक आवंटन की गणना कर रही है।

Answer 6

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

सरल निरंतर एकाधिक का उपयोग करने का कारण स्पष्ट रूप से है कि प्रत्येक परिशिष्ट निरंतर समय को कम कर देता है। लेकिन इसका मतलब यह नहीं है कि आप छोटे आकारों के लिए एक अलग (बड़े) अनुपात का उपयोग नहीं कर सकते हैं।

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

मुझे किसी भी दोगुना (या 1.5 * आईएनजी) एरे के बारे में पता नहीं है जो वास्तव में स्मृति त्रुटियों से बाहर निकलता है और उस मामले में कम हो जाता है। ऐसा लगता है कि यदि आपके पास एक विशाल एकल सरणी थी, तो आप ऐसा करना चाहते हैं।

मैं आगे जोड़ता हूं कि यदि आप लंबे समय तक आकार बदलने योग्य सरणी रखते हैं, और आप समय के साथ अंतरिक्ष का पक्ष लेते हैं, तो यह नाटकीय रूप से समग्र रूप से (ज्यादातर मामलों के लिए) को समझने का अर्थ हो सकता है और फिर सही आकार पर फिर से आवंटित कर सकता है जब आपका हो जाए।

Answer 7

मान लें कि आप x द्वारा सरणी आकार बढ़ाते हैं। तो मान लें कि आप आकार T के साथ शुरू करते हैं। अगली बार जब आप सरणी बढ़ाएंगे तो इसका आकार T*x होगा। फिर यह T*x^2 और इसी तरह होगा।

यदि आपका लक्ष्य पहले बनाई गई मेमोरी का पुन: उपयोग करने में सक्षम होना है, तो आप यह सुनिश्चित करना चाहते हैं कि आपके द्वारा आवंटित नई मेमोरी आपके द्वारा छोड़ी गई पिछली मेमोरी के योग से कम है। इसलिए, हमारे पास यह असमानता है:

T*x^n <= T + T*x + T*x^2 + ... + T*x^(n-2) 

हम दोनों तरफ से टी को हटा सकते हैं। इसलिए हम इस मिल:

x^n <= 1 + x + x^2 + ... + x^(n-2) 

अनौपचारिक रूप से, क्या हम कहते हैं कि nth आवंटन पर, हम अपने सभी पहले से पुनः आवंटित की जाती स्मृति से बड़ा या ताकि हम पुनः उपयोग कर सकते वें आवंटन पर स्मृति की जरूरत के बराबर होना चाहते है पहले स्मृति आवंटित।

उदाहरण के लिए

, अगर हम 3 कदम (यानी, n=3), तो हमारे पास है पर ऐसा करने में सक्षम होना चाहते

x^3 <= 1 + x 

यह समीकरण सभी एक्स ऐसी है कि 0 < x <= 1.3 (मोटे तौर पर)

के लिए सच है

देखें क्या x हम अलग अलग के लिए मिल n नीचे दिया गया है:

n maximum-x (roughly) 

3 1.3 

4 1.4 

5 1.53 

6 1.57 

7 1.59 

22 1.61 

ध्यान दें कि बढ़ रही कारक कम से कम 2 पाप हो गया है सीई x^n > x^(n-2) + ... + x^2 + x + 1 for all x>=2।

Answer 8

आदर्श रूप में, it's the golden ratio (के रूप में n → ∞ सीमा में): φ = 1.618 ...

अभ्यास में, आप कुछ करीब है, 1.5 की तरह चाहते हैं।

कारण ऊपर के लिंक से समझाया गया है - यह समीकरण एक्स^{n सुलझाने शामिल है - 1} = एक्स^{n + 1} - एक्सⁿ, जिसका सकारात्मक समाधान है x = φ।

Answer 9

मुझे पता है कि यह एक पुराना सवाल है, लेकिन ऐसी कई चीजें हैं जो हर कोई गायब होने लगती है। आकार < < 1. यह वह जगह है कुछ भी 1 और 2 के बीच से गुणा: पूर्णांक (नाव (आकार) * x), x संख्या है, * तैर रहा है बिंदु

पहले, इस 2 से गुणा है गणित, और प्रोसेसर को फ्लोट और int के बीच कास्टिंग के लिए अतिरिक्त निर्देश चलाने पड़ते हैं। दूसरे शब्दों में, मशीन स्तर पर, दोगुना नया आकार खोजने के लिए एक एकल, बहुत तेज़ निर्देश लेता है। 1 और 2 के बीच कुछ गुणा करने के लिए कम से कम एक फ्लोट पर आकार कास्ट करने के लिए एक निर्देश, गुणा करने के लिए एक निर्देश (जो फ्लोट गुणा है, इसलिए शायद यह कम से कम दो चक्र लेता है, अगर 4 या 8 गुना नहीं कई), और int को वापस करने के लिए एक निर्देश, और यह मानता है कि आपका प्लेटफार्म सामान्य रजिस्ट्रारों के उपयोग की आवश्यकता के बजाय, सामान्य उद्देश्य रजिस्टरों पर फ्लोट गणित कर सकता है। संक्षेप में, आपको प्रत्येक आवंटन के लिए गणित की अपेक्षा की जानी चाहिए कि एक साधारण बाएं शिफ्ट के रूप में कम से कम 10 गुना लें।यदि आप पुनर्वितरण के दौरान बहुत सारे डेटा की प्रतिलिपि बना रहे हैं, तो इससे कोई फर्क नहीं पड़ता है।

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

प्रश्न का मेरा जवाब? नहीं, कोई आदर्श संख्या नहीं है। यह इतना विशिष्ट है कि कोई भी वास्तव में कोशिश करता है। यदि आपका लक्ष्य आदर्श स्मृति उपयोग है, तो आप भाग्य से बहुत अधिक हैं। प्रदर्शन के लिए, कम आवंटन आवंटन बेहतर होते हैं, लेकिन अगर हम इसके साथ जाते हैं, तो हम 4 या 8 तक गुणा कर सकते हैं! बेशक, जब फ़ायरफ़ॉक्स एक शॉट में 1 जीबी से 8 जीबी का उपयोग करने से कूदता है, तो लोग शिकायत करने जा रहे हैं, इसलिए यह भी समझ में नहीं आता है। अंगूठे के कुछ नियम यहां दिए गए हैं:

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

इसे ओवरथिंक न करें। यदि आपने अभी कुछ ऐसा करने का प्रयास करने के लिए 4 घंटे बिताए हैं जो पहले से ही किया जा चुका है, तो आपने अपना समय बर्बाद कर दिया है। पूरी तरह से ईमानदारी से, यदि * 2 से बेहतर विकल्प था, तो यह दशकों पहले सी ++ वेक्टर वर्ग (और कई अन्य स्थानों) में किया गया होता।

आखिरकार, यदि आप वास्तव में अनुकूलित करना चाहते हैं, तो छोटी चीजें पसीना न करें। अब दिन, कोई भी 4KB स्मृति बर्बाद होने की परवाह नहीं करता है, जब तक कि वे एम्बेडेड सिस्टम पर काम नहीं कर रहे हों। जब आप 1 जीबी ऑब्जेक्ट्स प्राप्त करते हैं जो प्रत्येक 1 एमबी और 10 एमबी के बीच होते हैं, तो दोगुना संभवतः बहुत अधिक होता है (मेरा मतलब है, यह 100 से 1,000 वस्तुओं के बीच है)। यदि आप अपेक्षित विस्तार दर का आकलन कर सकते हैं, तो आप इसे एक निश्चित बिंदु पर रैखिक विकास दर तक ले जा सकते हैं। यदि आप प्रति मिनट लगभग 10 ऑब्जेक्ट्स की अपेक्षा करते हैं, तो प्रति चरण 5 से 10 ऑब्जेक्ट आकारों में बढ़ रहे हैं (एक बार हर 30 सेकंड में एक मिनट में) शायद ठीक है।

यह सब कुछ नीचे आता है, इसे सोचने पर विचार न करें, आप जो कर सकते हैं उसे अनुकूलित करें और अपने आवेदन (और मंच) को अनुकूलित करें यदि आपको चाहिए।

Answer 10

एक और दो सेंट

• अधिकांश कंप्यूटर आभासी स्मृति है! भौतिक स्मृति में आपके पास हर जगह यादृच्छिक पृष्ठ हो सकते हैं जो आपके प्रोग्राम की वर्चुअल मेमोरी में एक ही संगत स्थान के रूप में प्रदर्शित होते हैं। संकेतन का समाधान हार्डवेयर द्वारा किया जाता है। वर्चुअल मेमोरी थकावट 32 बिट सिस्टम पर एक समस्या थी, लेकिन यह वास्तव में अब कोई समस्या नहीं है। तो छेद भरना अब चिंता नहीं है (विशेष वातावरण को छोड़कर)। चूंकि विंडोज 7 भी माइक्रोसॉफ्ट अतिरिक्त प्रयास किए बिना 64 बिट का समर्थन करता है। @ 2011
• ओ (1) किसी भी आर> 1 कारक के साथ पहुंचा है। वही गणितीय सबूत न केवल पैरामीटर के रूप में 2 के लिए काम करता है।
• आर = 1.5 की गणना old*3/2 के साथ की जा सकती है इसलिए फ़्लोटिंग पॉइंट ऑपरेशंस की कोई आवश्यकता नहीं है। (मैं /2 कहना क्योंकि compilers सा उत्पन्न विधानसभा कोड में स्थानांतरण अगर वे मनचाहे ढंग से प्रतिस्थापित कर देगा।)
• MSVC आर = 1.5 के लिए चला गया है, तो कम से कम एक प्रमुख संकलक कि अनुपात के रूप में 2 का उपयोग नहीं करता है ।

जैसा कि किसी ने बताया है 2 से 8 बेहतर लगता है और 2 भी 1.1 से बेहतर महसूस करता है।

मेरी भावना यह है कि 1.5 एक अच्छा डिफ़ॉल्ट है। इसके अलावा यह विशिष्ट मामले पर निर्भर करता है।