2011-10-30 30 views
18

का प्रतिनिधित्व करने का प्रभावी तरीका मैं सी/सी ++ प्रोग्राम में अपने डेटा पर काम कर रहा हूं, जो 2 आयामी है। यहां मेरा मान युग्मित के लिए गणना की जाती है और यहां मान foo[i][j] और foo[j][i] के लिए समान होंगे।निचले/ऊपरी त्रिभुज मैट्रिक्स

इस प्रकार यदि मैं इसे एक साधारण 2 आयामी सरणी का उपयोग करके कार्यान्वित करता हूं, तो मेरी जगह का आधा बर्बाद हो जाएगा। तो इस निचले/ऊपरी त्रिकोणीय मैट्रिक्स का प्रतिनिधित्व करने के लिए सबसे अच्छी डेटा संरचना क्या होगी।

सादर,

+0

यहां आपके पास सी ++ में लागू लोअर त्रिकोणीय मैट्रिक्स का एक उदाहरण है https://github.com/fylux/TriangularMatrix – Fylux

उत्तर

11

सच में, तुम सिर्फ एक नियमित रूप से दो आयामी मैट्रिक्स का उपयोग कर बंद सबसे अच्छा कर रहे हैं। राम बहुत सस्ता है। यदि आप वास्तव में ऐसा नहीं करना चाहते हैं, तो आप तत्वों की सही संख्या के साथ एक-आयामी सरणी बना सकते हैं और फिर प्रत्येक तत्व को कैसे एक्सेस करें। उदाहरण के लिए, यदि सरणी इस तरह संरचित है:

j 
    1234 
i 1 A 
    2 BC 
    3 DEF 
    4 GHIJ 

और आप इसे एक एक आयामी सरणी के रूप में जमा है, सही करने के लिए छोड़ दिया है, आप array[3] साथ तत्व C(2, 2) का उपयोग होगा। आप [i][j] से [n] पर जाने के लिए एक फ़ंक्शन काम कर सकते हैं लेकिन मैं आपका मजा खराब नहीं करूंगा। लेकिन आपको ऐसा करने की ज़रूरत नहीं है जब तक कि प्रश्न में त्रिकोणीय सरणी वास्तव में बड़ी नहीं है या आप अंतरिक्ष के बारे में बहुत चिंतित हैं।

3

एक दांतेदार सरणी का उपयोग करें:

int N; 
// populate N with size 

int **Array = new Array[N]; 
for(int i = 0; i < N; i++) 
{ 
    Array[i] = new Array[N - i]; 
} 

यह पैदा करेगा सरणी

0 1 2 3 4 5 
0 [   ] 
1 [   ] 
2 [  ] 
3 [  ] 
4 [ ] 
5 [ ] 
+9

यह व्यक्तिगत सरणी स्वतंत्र रूप से आवंटित करेगा, जो कैश व्यवहार और स्मृति विखंडन के लिए बुरा हो सकता है। यह ठीक हो सकता है यदि आप प्रदर्शन के बारे में ज्यादा परवाह नहीं करते हैं, लेकिन उस स्थिति में आपको शायद एक एकल एनएक्सएन सरणी का उपयोग करना चाहिए। यदि आप यह तय करते हैं कि आप किसी भी प्रकार के पॉइंटर्स का उपयोग करना चाहते हैं, तो एक ही सरणी में N * (N + 1)/2 तत्व आवंटित करें और उस सरणी में ऑफसेट के रूप में पंक्ति पॉइंटर्स बनाएं। –

+0

@ErikP। : मुझे पता है कि निरंतर सरणी और एक्सेस विधियों के साथ एक वर्ग बनाना जो ऑफसेट की गणना करना बेहतर है, लेकिन यह एक बहुत आसान तरीका है। – Dani

11

की तरह आप मुख्य विकर्ण के बिना तो एन आइटम नहीं हैं एक कम त्रिकोणीय सरणी होगा (एन - 1) * मुख्य विकर्ण के साथ एन/2 तत्व, या (एन + 1) * एन/2 तत्व। मुख्य विकर्ण के बिना, (मैं, जे) (मैं, जे ∈ 0..एन -1, आई> जे) ⇒ (आई * (आई -1)/2 + जे)। मुख्य विकर्ण के साथ, (मैं, जे ∈ 0..एन -1, मैं ≥ जे) ⇒ ((आई + 1) * आई/2 + जे)।

(और हाँ, जब आप एक 2.5 गीगाबाइट मशीन पर 4 गीगाबाइट का आवंटन कर रहे हैं, यह काटने आधे से एक बड़ा फर्क है।)

2

अद्वितीय तत्व, मी, जरूरत की संख्या एक में प्रतिनिधित्व करने सममित मैट्रिक्स के लिए

मुख्य विकर्ण

m = (n*(n + 1))/2

विकर्ण के बिना साथ

(के रूप में ओ पी का वर्णन करता है, मुख्य: n सममित मैट्रिक्स द्वारा n विकर्ण की आवश्यकता है, लेकिन केवल अच्छे उपाय के लिए ...)

m = (n*(n - 1))/2

2 तक विभाजित नहीं होने तक अंतिम ऑपरेशन महत्वपूर्ण है यदि पूर्णांक के साथ पूर्णांक अंकगणित का उपयोग किया जाता है।

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

i = (y*(2*n - y - 1))/2 + (x - y -1) 

एक के लिए विकर्ण

i = (y*(2*n - y + 1))/2 + (x - y - 1) 

साथ

:

आबंटित स्मृति में सूचकांक, मैं, की पंक्ति एक्स और ऊपरी विकर्ण मैट्रिक्स में स्तंभ y समीकरणों में निचले विकर्ण मैट्रिक्स फ्लिप एक्स और वाई। एक सममित मैट्रिक्स के लिए बस x> = y या y> = x को आंतरिक रूप से चुनें और आवश्यकतानुसार सदस्य फ़ंक्शन फ़्लिप करें।

+0

यह बिल्कुल सही नहीं लगता है - आपके "विकर्ण" उपज -1 में प्लगिंग (0,0)। – MattWallace

0

दानी के जवाब पर riffing ...

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

const int side = ...; 
T *backing_data = new T[side * (side + 1)/2]; // watch for overflow 
T **table = new T*[side]; 
auto p = backing_data; 
for (int row = 0; row < side; ++row) { 
    table[row] = p; 
    p += side - row; 
} 

अब के रूप में डैनी के जवाब में दिखाया गया है आप table उपयोग कर सकते हैं जैसे कि यह एक दांतेदार सरणी था:

table[row][col] = foo; 

लेकिन सभी डेटा एक खंड है, जो इसे अन्यथा के आधार पर नहीं किया जा सकता है आपकी आवंटक की रणनीति।

पंक्ति पॉइंटर्स की तालिका का उपयोग करके प्रेक्सोलिटिक के सूत्र का उपयोग करके ऑफसेट की गणना करने से तेज़ हो सकता है या नहीं।

1

एड्रियन मैककार्थी के जवाब में, एक कम त्रिकोणीय मैट्रिक्स के बजाय एक ऊपरी एक के लिए

p += row + 1; 

साथ

p += side - row; 

बदलें।

1

दान और प्रेक्सोलिटिक ने विकर्ण के साथ निम्न त्रिकोणीय मैट्रिक्स के लिए प्रस्तावित किया लेकिन सही संक्रमण नियम के साथ।

मैट्रिक्स एन के लिए आपको सर (n+1)*n/2 लंबाई और संक्रमण नियम Matrix[i][j] = Array[i*(i+1)/2+j] की आवश्यकता है।

#include<iostream> 
#include<cstring> 

struct lowerMatrix { 
    double* matArray; 
    int sizeArray; 
    int matDim; 

    lowerMatrix(int matDim) { 
    this->matDim = matDim; 
    sizeArray = (matDim + 1)*matDim/2; 
    matArray = new double[sizeArray]; 
    memset(matArray, .0, sizeArray*sizeof(double)); 
    }; 

    double &operator()(int i, int j) { 
    int position = i*(i+1)/2+j; 
    return matArray[position]; 
    }; 
}; 

मैं double साथ यह किया है, लेकिन आप template के रूप में यह कर सकते हैं। यह केवल मूल कंकाल है इसलिए विनाशक को लागू करना न भूलें।

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