एक इष्टतम 2 डी डेटा संरचना

Question

मैंने इसे बहुत सोचा है लेकिन वास्तव में कुछ के साथ आने में सक्षम नहीं है।

मान लीजिए कि मैं एक्स (एन * एन) के तहत किसी भी कॉलम और किसी भी पंक्ति द्वारा क्रमबद्ध तत्वों का एक्स एन संग्रह चाहता हूं, और ओ (एम + एन) या उससे कम में एक पंक्ति डालने या हटाने की क्षमता भी चाहता हूं .. । क्या यह संभव है?

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

उदाहरण:

1 100 25 34 
2 20 15 16 
3 165 1 27 

3 पंक्ति द्वारा क्रमबद्ध किया गया:

25 1 34 100 
15 2 16 20 
1 3 27 165 

छंटाई कि 1 कॉलम के आधार पर:

1 3 27 165 
15 2 16 20 
25 1 34 100 

Answer 1

मैं दो इंडेक्स एरे, कॉलम के लिए एक और पंक्तियों के लिए एक बनाऊंगा। अपने डेटा

1 100 25 34 
2 20 15 16 
3 165 1 27 

के लिए तो आप दो सरणियों बनाने के लिए:

• cols = [0, 1, 2, 3]
• rows = [0, 1, 2]

फिर जब आप 3 पंक्ति से मैट्रिक्स क्रमबद्ध करना चाहते हैं, तो आप मूल रखना मैट्रिक्स बरकरार है, लेकिन तदनुसार इंडेक्स सरणी को बदलें:

• cols = [2, 0, 3, 1]
• rows = [0, 1, 2]

चाल अब एक अविवेक के साथ अपने मैट्रिक्स का उपयोग करने की है। तो m[x][y] के साथ इसे एक्सेस करने के बजाय आप इसे m[cols[x]][rows[y]] तक एक्सेस कर सकते हैं। जब आप पंक्तियों/कोल्स सरणी के पुनर्वितरण करते हैं तो आपको एम [कोल्स [x]] [पंक्तियों [y]] का भी उपयोग करना होगा।

इस तरह सॉर्टिंग O(n*log(n)) है, और पहुंच O(1) है।

+-+ 
|0| -> [0 1 2 3 4] 
|1| -> [0 1 2 3 4] 
|2| -> [0 1 2 3 4] 
+-+ 

एक पंक्ति सम्मिलित करने के लिए, बस अंतिम स्थान पर डालने और उसके अनुसार rows सूचकांक सरणी अद्यतन करते हैं, के साथ:

डेटा संरचना के लिए, मैं एक और सरणी के लिंक के साथ एक सरणी का प्रयोग करेंगे सही स्थान। जैसे जब rows[0, 1, 2] था और आप इसे सामने डालना चाहते हैं, तो पंक्तियां [3, 0, 1, 2] बन जाएंगी। इस तरह एक पंक्ति का सम्मिलन O(n) है।

कॉलम डालने के लिए, आप इसे अंतिम तत्व के रूप में भी जोड़ते हैं, और तदनुसार कोल्स अपडेट करते हैं। कॉलम डालने O(m) है, पंक्ति O(n) है।

हटाना O(n) या O(m) है, यहां आप केवल उस कॉलम/पंक्ति को प्रतिस्थापित करते हैं जिसे आप अंतिम के साथ हटाना चाहते हैं, और उसके बाद अनुक्रमणिका सरणी से अनुक्रमणिका हटा दें।

Answer 2

आप एक हैश तालिका का उपयोग करें और सम्मिलित कर सकते हैं (i , जे) -> नोड जहां (i, j) एक 2-टुपल होता है जिसमें 2 पूर्णांक होते हैं। आप अपनी खुद की कस्टम क्लास लिख सकते हैं जो इसके लिए बराबर विधि और गेटहाश() विधि को परिभाषित करता है ... या पायथन आपको मुफ्त में देता है।

अब ... आपका क्या मतलब है - एक पंक्ति या स्तंभ द्वारा क्रमबद्ध? कृपया मूल्यों के साथ एक उदाहरण दें!

Answer 3

शायद इसके लिए एक छोटा डेटाबेस बनाकर?

एल्गोरिदम सॉर्ट करने वाले डेटाबेस शायद पहिया को पुनर्निर्मित करने से बेहतर हैं। MySQL करेंगे। प्रदर्शन प्राप्त करने के लिए, तालिका मेमोरी में बनाई जा सकती है। फिर आप सामान्य टेबल के रूप में कॉलम पर इंडेक्स कर सकते हैं, और डेटाबेस इंजन को गंदी नौकरी (ऑर्डरिंग और ऐसा) करने दें। और फिर आप केवल परिणाम फसल।

Answer 4

अगर मुझे यह समस्या सौंपी गई, तो मैं पंक्ति और कॉलम रीमेपिंग वैक्टर बनाउंगा। E.G. पंक्तियों को क्रमबद्ध करने के लिए, मैं पंक्ति के क्रम को सामान्य के रूप में निर्धारित करता हूं, लेकिन पंक्तियों की प्रतिलिपि बनाने के बजाय, मैं केवल पंक्ति remapping वेक्टर बदलना होगा।

वह कुछ इस तरह दिखेगा:

// These need to be set up elsewhere. 
size_t nRows, nCols; 
std::vector<T> data; 

// Remapping vectors. Initially a straight-through mapping. 
std::vector<size_t> rowMapping(nRows), colMapping(nCols); 
for(size_t y = 0; y < nRows; ++y) 
    rowMapping[y] = y; 
for(size_t x = 0; x < nCols; ++x) 
    colMapping[x] = x; 

// Then you read data(row, col) with 
T value = data[rowMapping[row] * nCols + colMapping[col]]; 

पी.एस. इंडेक्स के बजाय rowMapping में पॉइंटर्स स्टोर करना एक छोटा सा अनुकूलन होगा। यह आपको T value = rowMapping[row][colMapping[col]]; करने देगा, हालांकि, आपको हर बार पॉइंटर्स को फिर से समझना होगा कि data परिवर्तनों के आयाम, जो त्रुटि-प्रवण हो सकते हैं।

Answer 5

सिर्फ मार्टिनस और माइक के उत्तरों में जोड़ने के लिए: आपको जो चाहिए, संक्षेप में, पिवोटिंग, जो वे सुझाव देते हैं और एक बहुत अच्छी तरह से ज्ञात तकनीक है जो मैट्रिस से जुड़े किसी भी संख्यात्मक एल्गोरिदम में उपयोग की जाती है। उदाहरण के लिए, आप "आंशिक पिवोटिंग के साथ LU decomposition" और "पूर्ण pivoting के साथ LU decomposition" के लिए त्वरित खोज चला सकते हैं। क्रमशः स्टोर करने वाले अतिरिक्त वैक्टर को "पिवट" कहा जाता है।