2012-01-04 13 views
6

स्मृति में संग्रहीत 2 डी सरणी कैसे है?मेमोरी में एक गतिशील 2 डी सरणी कैसे संग्रहीत की जाती है?

मैंने निम्नलिखित दृष्टिकोण के बारे में सोचा, जहां पंक्तियों को स्मृति के जटिल ब्लॉक के रूप में संग्रहीत किया जाता है।

| _ __ _ __ _ __ || _ __ _ __ _ __ | __ _ __ _ __ |_ __ _ __ _ _ | ... | _ __ _ __ _ __ |

तत्वों को (i, j) -> n * i + j जैसे accesed हैं, जहां n मैट्रिक्स का आयाम है (मान लीजिए कि यह nxn है)।

लेकिन अगर मैं इसमें एक नया कॉलम जोड़ना चाहता हूं तो क्या होगा? मुझे प्रत्येक पंक्ति में प्रत्येक (एन + 1) वें तत्व को अपडेट करना होगा और उन्हें सही पर भी स्थानांतरित करना होगा, लेकिन यह बहुत कम्प्यूटेशनल रूप से महंगा है।

एक और विकल्प मैट्रिक्स को नए स्थान पर कॉपी करना होगा और फ्लाई पर नए कॉलम के तत्वों के साथ पंक्तियों को अपडेट करना होगा। लेकिन सरणी बड़ी है तो यह भी बहुत कुशल नहीं है।

और आखिरकार तीसरा विकल्प मैंने सोचा कि प्रत्येक पंक्ति के लिए एक निश्चित मात्रा में स्मृति आवंटित करना है और जब मैं एक नया कॉलम जोड़ता हूं तो मुझे पंक्तियों को दाएं स्थानांतरित करने की आवश्यकता नहीं होती है।

मुझे स्मृति में अंतराल नहीं हो सकता है, इसलिए सभी ब्लॉक अव्यवस्थित होना चाहिए।

मैं एक सी कार्यान्वयन संकेत और वास्तविक रैम स्मृति का उपयोग के लिए नहीं पूछ रहा हूँ, मैं स्मृति में एक गतिशील 2d सरणी भंडारण का एक सैद्धांतिक दृष्टिकोण के बारे में बस उत्सुक हूँ तो के रूप में यह नई पंक्तियां जोड़ी के लिए आसान है या इसे कॉलम

क्या अन्य और अधिक कुशल दृष्टिकोण हैं?

+0

आप किस आकार के साथ काम कर रहे हैं? क्या हम 1.000.000 तत्वों के 10 तत्वों की बात कर रहे हैं? –

+0

मिलियन की तरह अधिक। – flowerpower

उत्तर

4

यदि आप जानते हैं कि आप एक 2 डी सरणी बना रहे हैं जिसे आप विस्तारित करेंगे, तो एक दृष्टिकोण प्रत्येक आयाम में अधिक आकार आवंटित करना होगा।

  • डबल आवंटन
  • करने के लिए पुराने सरणी से सभी डेटा की प्रतिलिपि का आकार: वास्तविक आकार और आवंटित आकार पर नज़र रखें, और जब वास्तविक आकार से बड़ा क्या आवंटित किया जाता है, निम्न कार्य करें नया एक
  • मुक्त वर्ष सरणी

इस गतिशील -1 डी सरणियों के आवंटन के लिए एक आम तकनीक के एक 2 डी विस्तार होगा।

+0

अच्छा विचार है, लेकिन मुझे आश्चर्य है कि क्या यह उसकी आवश्यकता को तोड़ देता है कि स्मृति संगत हो। –

+0

मूल प्रश्न के बाद उस आवश्यकता को जोड़ा गया था। मुझे नहीं पता कि "ब्लॉक" का अर्थ है "एक विशिष्ट पंक्ति" या "संपूर्ण डेटा संरचना"। –

+0

इसके साथ मेरा मतलब था कि मुझे स्मृति में अंतराल नहीं हो सकता है। मान लीजिए कि मैं इसे बाइनरी फाइल में स्टोर करना चाहता हूं, मुझे लगता है कि यह मेरी मेमोरी परिदृश्य में फिट होगा। – flowerpower

1

यदि आपको मेमोरी में विस्तार करने और संगत होने के लिए सरणी की आवश्यकता है, तो इसे प्राप्त करने का एक तरीका केवल 1 डी सरणी और 'नकली' को दूसरे आयाम का उपयोग करना है।

यदि आपके प्रारंभिक 1 डी सरणी में आपके सभी 2 डी सरणी की आवश्यकता से अधिक स्थान है, तो उसे स्मृति में संभावित रूप से आगे बढ़ने की आवश्यकता नहीं होगी (संभावित रूप से अंतराल से परहेज)। हालांकि, इस पर निर्भर करते हुए कि आप इसे कैसे कार्यान्वित करते हैं, एक डालने वाले उप सरणी में से एक को बाद में तत्वों को घुमाने की आवश्यकता हो सकती है (आप अपने सरणी में अंतराल भी प्राप्त कर सकते हैं, लेकिन मेरा मानना ​​है कि यह आपकी कोई अंतराल आवश्यकता का उल्लंघन नहीं करता है)।

यदि आपको वास्तव में 2 आयामों की आवश्यकता है, तो ग्रेग का उत्तर जाने का तरीका है। यदि आप अपने डेटा के आकार को शुरू करने के बारे में जानते हैं, तो यह बहुत आसान बनाता है।

संबंधित मुद्दे