जावा में ऊपरी त्रिभुज मैट्रिक्स का प्रतिनिधित्व करने के लिए सबसे अच्छी डेटा संरचना क्या है?

Question

मान लीजिए कि पूर्णांक के ऊपरी त्रिभुज मैट्रिक्स दिए जाते हैं। जावा में इसे संग्रहीत करने का सबसे अच्छा तरीका क्या है? बेवकूफ 2 डी int सरणी स्पष्ट रूप से कुशल नहीं है। जिस समाधान के साथ मैं आया था उसे उत्तर अनुभाग में ले जाया गया था।

Answer 1

मुझे लगता है कि मुझे समाधान मिला है। यहाँ मेरी समाधान है: मान लीजिए आप एक 4X4 ऊपरी त्रिकोणीय मैट्रिक्स एम

1 2 3 4 
0 6 7 1 
0 0 8 9 
0 0 0 5 

है आप एक 1d सरणी में एम के हर तत्व मैप कर सकते हैं, कि सबसे अच्छा समाधान है। आपको यह जानने की जरूरत है कि मैट्रिक्स का कौन सा [पंक्ति, कॉल] आपके 1 डी सरणी के तत्व से मेल खाता है।

start_index=((col_index-1)+1)+((col_index-2)+1)+...+1 
end_index=start_index + col_index 

उदाहरण के लिए:: यहाँ आप कैसे जादू है अगर मैं कहाँ मैट्रिक्स के 3 स्तंभ पर तत्व हैं खोजना चाहते हैं, सरणी में:

start_index=((3-1)+1)+((3-2)+1)+((3-3)+1)=6 
end_index=6+3=9 

तो, सब मैं करने की ज़रूरत है मेरी सरणी के इंडेक्स 6 पर शुरू करना, और इंडेक्स 9 (9वीं तत्व सहित) तक सभी तत्वों को पढ़ना है। इस प्रक्रिया के बाद, आप एनएक्सएन मैट्रिक्स की सभी कोशिकाओं को संग्रहित और पुनर्प्राप्त कर सकते हैं (एन + एन^2)/2 स्पेस।

Answer 2

मैट्रिक्स हमेशा विकर्ण है, तो मैं प्रयोग करेंगे:

List<List<Integer>> matrix = ... 

यदि यह एक विरल मैट्रिक्स है, मैं नक्शे का प्रयोग करेंगे:

Map<Map<Integer>> = ... 

इस दूसरे मामले में, आप की आवश्यकता हो सकती नए पंक्तियों और स्तंभों तक पहुंच प्रबंधित करने के लिए मानचित्र को एक कक्षा में लपेटें और संचालन सेट करें।

यह सब आपकी आवश्यकताओं, आपकी स्मृति सीमाओं और मैट्रिक्स आकार पर निर्भर करता है।

Answer 3

गुवा के Table के बारे में क्या? इसे हैशमैप्स या ट्रीमैप्स (साथ ही यदि आवश्यक हो तो 2 डी सरणी) का उपयोग करके कार्यान्वित किया जाता है, लेकिन यह Map<Integer, Map<Integer, V>> को परिभाषित करने से बहुत अच्छा एपीआई प्रदान करता है।

Answer 4

यदि आप स्मृति को सहेजना चाहते हैं, तो आपका समाधान शानदार दिखता है - इसे packed storage matrix कहा जाता है। स्तंभ, ऊपर से नीचे से कॉलम, अपने सरणी इस प्रकार दिखाई देगा: 1 2 6 3 7 8 4 1 9 5

मैं योग सूत्र (n² + n)/2 (पंक्ति और स्तंभ है शून्य आधारित) के आधार पर, अपने सूचकांक का एक सरल गणना सुझाव है।

list_index = (column^2 + column)/2 + row; 

कार्यान्वयन निम्नलिखित दिखाई देगा:

public class TriangularMatrix { 
    private final int[] list; 

    public TriangularMatrix(int size) { 
     list = new int[sumFormula(size)]; 
    } 

    public int set(int row, int column, int value) { 
     validateArguments(row, column); 

     int listIndex = getListIndex(row, column); 
     int oldValue = list[listIndex]; 
     list[listIndex] = value; 

     return oldValue; 
    } 

    public int get(int row, int column) { 
     validateArguments(row, column); 

     return list[getListIndex(row, column)]; 
    } 

    private void validateArguments(int row, int column) { 
     if (row > column) { 
      throw new IllegalArgumentException("Row (" + row + " given) has to be smaller or equal than column (" + column + " given)!"); 
     } 
    } 

    private int getListIndex(int row, int column) { 
     return sumFormula(column) + row; 
    } 

    private int sumFormula(int i) { 
     return (i*i + i)/2; 
    } 
} 

वहाँ, another question on SO (नकारात्मक) प्रदर्शन प्रभाव पर चर्चा है, हालांकि यह फोरट्रान बारे में है।