एरे का उपयोग कर मैट्रिक्स निर्माण को कार्यान्वित करते समय, जो अधिक कुशल होगा? एक 1 डी सरणी, या सरणी (2 डी) का एक सरणी का उपयोग कर?मैट्रिक्स को कार्यान्वित करना, जो अधिक कुशल है - Arrays (2D) या 1 डी सरणी का उपयोग करके?
मुझे लगता है कि 2 डी अधिक कुशल है क्योंकि आपके पास पहले से ही एक्स और वाई समन्वय तत्व हैं, जहां 1 डी कार्यान्वयन में आपको इंडेक्स की गणना करना है।
संपादित करें: यह जावा
का उपयोग कर कार्यान्वित किया जा रहा है "कुशल" नहीं कैच-ऑल शब्द है।
भंडारण के मामले में एक सरणी-सरणी समाधान अधिक कुशल है, जहां सरणी स्पैस हो सकती है (यानी, आप सभी शून्यों की मैट्रिक्स लाइन का प्रतिनिधित्व करने के लिए शून्य सूचक का उपयोग कर सकते हैं)। यह (सी में) होगा:
int *x[9];
जहां प्रत्येक "int *" अलग से आवंटित किये जायेंगे।
ए 2 डी सरणी (जो आवश्यक रूप से सरणी की सरणी नहीं है) आमतौर पर गतिशील (गति के संदर्भ में कुशल) होगी क्योंकि यह गणित के साथ मेमोरी स्थानों को काम करता है, मेमोरी स्थानों को संदर्भित किए बिना। मैं निर्माण की बात कर रहा हूँ:
int x[9][9];
एक -1 डी सरणी:
int x[81];
किसी भी बराबर 2 डी संस्करण की तुलना में तेजी होने की संभावना नहीं है, क्योंकि आप अभी भी कुछ पर गणना करने के लिए है सही सेल खोजने के लिए इंगित करें (संकलक को ऐसा करने के बजाए मैन्युअल रूप से आपके कोड में)।
संपादित करने के बाद जहां जावा एक आवश्यकता के रूप में जोड़ा गया है:
मेरा मानना है कि जावा 2 डी सरणियों सरणियों किस्म की सरणी (जो के रूप में एक 1 डी सरणी के लिए आवश्यक एक करने का विरोध दो स्मृति तक पहुँचता है की आवश्यकता होगी) के हैं इसलिए मैन्युअल इंडेक्स गणना के साथ 1 डी सरणी तेजी से हो सकती है। तो, बजाय घोषित करने और उपयोग करने का:
int x[width][height];
x[a][b] = 2;
आप के साथ और अधिक गति प्राप्त कर सकते हैं:
int x[width*height];
x[a*height+b] = 2;
तुम बस ध्यान रहे कि आप सूत्र कहीं भी मिश्रित (यानी, डॉन नहीं मिलता है करने की आवश्यकता है अनजाने में 4 और 7 स्वैप नहीं करें)।
यह गति अंतर इस बात पर आधारित है कि मुझे लगता है कि जावा को कवर के तहत कोड किया गया है, इसलिए मैं गलत हो सकता हूं (लेकिन मुझे शक है :-)। मेरी सलाह है, हमेशा अनुकूलन प्रश्नों के लिए, माप, अनुमान मत लगाओ!
भाषा के आधार पर, कोई अंतर नहीं होगा। असली सवाल यह है कि कैसे 2 डी मैट्रिक्स आवंटित किया जाता है। क्या यह एक्स * वाई बाइट्स का एक एकल संगत स्थान है, या इसे एक्स आकार के वाई स्वतंत्र सरणी के रूप में आवंटित किया गया है। उत्तरार्द्ध आमतौर पर स्पैर मैट्रिस बनाते समय किया जाता है।
इसे जावा – barfoon
मैं तारीख के उत्तर के साथ रैंक तोड़ने जा रहा हूं और निम्नलिखित कारण बताता हूं कि 1 डी सरणी काफी संभव है।
ए 2 डी सरणी में 2 मेमोरी एक्सेस शामिल हैं। उदाहरण के लिए एक [x] [y] पहले ए [x] को देखना चाहिए, और उसके बाद उस सरणी का एक और लुकअप करें [y]।
पारंपरिक रूप से एक 1 डी कार्यान्वयन ए [एक्स + (चौड़ाई * वाई)] होगा। जब चौड़ाई रजिस्टरों (या एक शाब्दिक) में होती है, तो इसका अर्थ है 2 लुकअप के बजाय 2 गणित ऑप्स और 1 लुकअप। लुकअप गणित सेशन की तुलना में धीमी गति के आदेश हैं, इसलिए यदि चौड़ाई भी थोड़ी देर के लिए रजिस्टर में है, या एक शाब्दिक है, तो यह तेज़ होगा।
बेशक मानक चेतावनी लागू होती है। हमेशा प्रोफ़ाइल, और समयपूर्व अनुकूलन से बचें।
में कार्यान्वित किया जा रहा है 2 डी सरणी का कार्यान्वयन भाषा पर निर्भर करता है, यह आवश्यक रूप से सरणी की सरणी नहीं है। एक्स [9] [9] एक्स [81] कवर के तहत हो सकता है जो x [81] घोषित करने से अलग नहीं होगा। अंतर यह है कि आपका कोड या कंपाइलर गणित को सेल ढूंढने के लिए करता है या नहीं। – paxdiablo
दरअसल, सोचा कि मैं बेहतर परीक्षण करूँगा। जीसीसी के तहत, "int x [9] [9]; x [5] [4] = 7;" स्टैक फ्रेम में एक निश्चित स्थान "$ 7, -148 (% ebp)" को संकलित करता है। तो यह कम से कम दो स्मृति संदर्भ नहीं करता है। फिर, यह भाषा और संकलक पर निर्भर करता है। – paxdiablo
सहमत है, यह अत्यधिक भाषा/कंपाइलर निर्भर है। मैं मान रहा हूं कि ये मैट्रिक्स गतिशील रूप से आवंटित किए जाएंगे, इसलिए आपका परीक्षण वह नहीं है जो मैं कल्पना करता हूं कि ओपी के मन में क्या था। – patros
मुझे नहीं लगता कि इस प्रश्न का उत्तर पर वास्तव में नमूना कोड लिखने और परिणामों का परीक्षण किए बिना का उत्तर दिया जा सकता है। उदाहरण के लिए this question निम्नलिखित परिणाम मिले।
sum(double[], int): 2738 ms (100%)
sum(double[,]): 5019 ms (183%)
sum(double[][]): 2540 ms (93%)
जालीदार सरणी सबसे तेज़ होने के बाद, 1 आयामी सरणी के बाद, बहुआयामी सरणी के बाद। जालीदार सरणी सबसे तेज़ होने की संभावना है जो लोग भविष्यवाणी नहीं करेंगे। ये परिणाम शायद जावा के लिए बेकार हैं क्योंकि जावा के अलग-अलग अनुकूलन (और जावा में कोई बहुआयामी सरणी नहीं है)।
मैं धारणाओं को लेकर बहुत सावधान रहूंगा। उदाहरण के लिए, यदि आप 2 डी सरणी की पंक्ति पर लूप कर रहे हैं, तो जावा इंडेक्स लुकअप को अनुकूलित कर सकता है या सीमाओं की जांच करने वाले सीमाओं से बाहर हो सकता है, यदि आप इनलाइन इंडेक्स गणनाओं के साथ 1 डी सरणी का उपयोग कर रहे हैं तो यह संभव नहीं हो सकता है।
मैं वांछित मंच पर गति का परीक्षण करने के लिए एक सरल कार्यक्रम लिखने का सुझाव देता हूं।
वाणिज्यिक परिमित तत्व पैकेज जो मैंने अपने कैरियर के दौरान एक यांत्रिक अभियंता के रूप में 1 डी सरणी का उपयोग करके अपने रैखिक बीजगणित गणना के आधार के रूप में उपयोग किया था। परिमित तत्व विधियों का परिणाम मैट्रिक में होता है जो बड़े, स्पैस और बैंडेड होते हैं। बैंड के बाहर उन सभी शून्य तत्वों को संग्रहीत करना कोई समझ नहीं आया।
एकमात्र बार आप 2 डी सरणी का उपयोग करेंगे, छोटे, अकादमिक समस्याओं या जो स्पैस नहीं हैं (उदाहरण के लिए, सीमा तत्व विधियां)।
सामान्य मामले में, किसी भी एल्गोरिदम के लिए सबसे प्रभावी कार्यान्वयन वह है जिसमें कम से कम कोड होता है। यह कई कारणों से है:
यह भी एक्सेस पैटर्न पर बहुत निर्भर करता है। क्या आप हमेशा पूरे मैट्रिक्स पर चलते हैं? क्या यह विचित्र है? क्या आप पंक्तियों या स्तंभों को संसाधित करना पसंद करते हैं?
चरम मामले में (केवल 10 कोशिकाओं के साथ एक अरब पंक्तियों और स्तंभों के साथ मैट्रिक्स), HashMap किसी भी सरणी कार्यान्वयन से अधिक कुशल हो सकता है।अन्य समस्याओं के लिए, समस्या के आधार पर दृष्टिकोण को मिश्रण करने के लिए और अधिक कुशल हो सकता है (उदाहरण के लिए, मिनी-मैट्रिस के सरणी के HashMap जब कोशिकाएं एक विशाल खाली जगह में "टक्कर" करती हैं)।
यदि आपकी समस्याएं पंक्ति/कॉलम का पता लगाने के लिए कहती हैं और फिर उन मानों को संसाधित करती हैं, तो 2 डी दृष्टिकोण का उपयोग करने के लिए यह अधिक कुशल हो सकता है, इसलिए पहली पहुंच एक सरणी लौटाती है जिसे आप सीमाओं के बारे में परेशान किए बिना प्रक्रिया कर सकते हैं, एक- ऑफ-एरर इत्यादि।
+1 "कुशल नहीं है-सभी वाक्यांश" याद रखें कि .NET में जंजीर सरणी के लिए ऑप्टिमाइज़ेशन हैं जो उदाहरण के लिए बहुआयामी लोगों के लिए काम नहीं करते हैं। – Jimmy
जावा में 1 डी सरणी शायद तेज़ है, क्योंकि 2 डी-ऐरे को कम से कम दो मेमोरी पढ़ने की आवश्यकता होती है (कोई गणना नहीं, हालांकि)। –
मैं धारणा बनाने से सावधान रहूंगा। उदाहरण के लिए, यदि आप 2 डी सरणी की एक पंक्ति पर लूप कर रहे हैं, तो जावा इंडेक्स लुकअप व्हीयर को अनुकूलित कर सकता है, यदि आप 1 डी सरणी के साथ इंडेक्स में गणना कर रहे हैं तो शायद नहीं। –