मैट्रिक्स तुलना एल्गोरिदम

Question

यदि आपके पास आयामों के 2 मैट्रिक्स एन * एम हैं। अंतर सुधार पाने का सबसे अच्छा तरीका क्या है?

उदाहरण:

2 3 2 3 2 3 2 3      2 3 2 3 2 3 2 3 
2 3 2 3 2 3 2 3      2 3 2 3 2 3 2 3 
2 3 4 5 4 3 2 3  <--->   2 3 2 3 2 3 2 3 
2 3 4 5 2 3 2 3      2 3 2 3 2 3 2 3 
2 3 2 3 2 3 2 3      2 3 2 3 2 3 2 3 

         | 
         | 
        \/
      Rect([2,2] , [3,4]) 
        4 5 4 
        4 5 2-> A (2 x 3 Matrix) 

सबसे अच्छा मैं ऊपरी-बाईं ओर से बिंदु है जहां अंतर नहीं है हिट स्कैन करने के लिए है के बारे में सोच सकता है

। फिर नीचे दाएं से स्कैन करें और उस बिंदु पर हिट करें जहां कोई अंतर है।

लेकिन सबसे खराब स्थिति में, यह ओ (एन * एम) है। क्या एक बेहतर कुशल एल्गोरिदम है? या क्या मैं ऐसा कुछ कर सकता हूं जिसके साथ मैं उनका प्रतिनिधित्व करता हूं, ताकि आप एक अधिक कुशल एल्गोरिदम लागू कर सकें? और आपको याद है, यह मैट्रिक्स बहुत बड़ा हो सकता है।

Answer 1

नहीं, कोई अधिक कुशल एल्गोरिदम नहीं है। समान मैट्रिक्स के लिए, आपको सभी तत्वों को स्कैन करना होगा, इसलिए एल्गोरिदम आवश्यक है O(n*m)।

Answer 2

"लेकिन सबसे बुरी स्थिति में, यह ओ (एन एम) है। क्या कोई बेहतर कुशल एल्गोरिदम है?" शायद ओ (एन एम) डेटा के आयाम के कारण नहीं। इस तरह के कई मैट्रिक्स ऑपरेशंस एम एन हैं क्योंकि सबसे बुरे मामले में एम एन तत्व हैं जिन्हें मैट्रिस बराबर के मामले में सभी को चेक करने की आवश्यकता होगी।

औसत मामले को देखना अधिक दिलचस्प है, यदि अंतर बॉक्स पूरे मैट्रिक्स के भीतर एक आयताकार है तो मुझे संदेह है कि आप औसतन सभी तत्वों से कम स्कैनिंग से दूर हो सकते हैं।

यहां एक त्वरित हालांकि मैं था है: ऊपरी बाएं कोने में इस XY

1. प्रारंभ वर्तमान तत्व का ट्रैक रखने, फोन तो XY अब शीर्ष कोने है

2. चेक कि तत्वों XY दोनों में बराबर हैं, यदि बराबर नहीं है तो 3 0 पर जाएं 4

3. यदि तत्व नहीं हैं तो आपके पास अंतर मैट्रिक्स का तत्व है। इस तत्व को रिकॉर्ड करें, फिर अन्य तत्वों के लिए उस पंक्ति और कॉलम को खोजें (शायद बाइनरी खोज की तरह कुछ सबसे तेज़ है)। एक बार पंक्ति/कॉलम की खोज हो जाने के बाद आपके पास किनारों के निर्देशांक होते हैं। तत्वों 4.

4. अगला कदम कदम XY तिरछे एक नीचे तत्व और एक तत्व के लिए नहीं बराबर कदम रखते हैं ठीक है, तो 2 पर जाने के लिए फिर से

5. एक बार एक विकर्ण तो कवर किया जाता है आप के साथ परीक्षण करने के लिए की आवश्यकता होगी अगले विकर्ण (मुझे संदेह है कि वर्तमान विकर्ण से सबसे दूर दूर एक नया विकर्ण चुनना सबसे अच्छा होगा, हालांकि मेरे पास कोई सबूत नहीं है कि यह सबसे अच्छा विकल्प है) जब तक सभी तत्व शामिल नहीं होते हैं। सबसे खराब मामला यह अभी भी ओ (एन * एम) है लेकिन यह औसत मामले में तेज़ हो सकता है।

अनिवार्य रूप से आपको जल्दी से जल्दी के रूप में एक अलग तत्व करने की कोशिश कर रहे हैं, ताकि उद्देश्य पहले अलग तत्व को खोजने के लिए खोजों की संख्या की उम्मीद मूल्य कम करने के लिए इस तरह से पहले तत्व का चयन किया गया है।

Answer 3

दूसरों की तरह इंगित किया गया है, ओ (एन * एम) इष्टतम है।

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

बेशक, यह मानता है कि प्रश्न में अंतर वास्तव में आयताकार के रूप में है। यदि यह कुछ अन्य आकार है, और आप बाध्य आयताकार चाहते हैं, तो आपको पंक्तियों और स्तंभों को स्कैन करना होगा, इससे कोई फर्क नहीं पड़ता।

Answer 4

मुझे लगता है कि प्रस्तावित एल्गोरिदम एक इष्टतम है। हालांकि मैं आपको BLAS लाइब्रेरी का प्रयास करने का सुझाव देता हूं जो बहुत ही कुशल है, और प्रदर्शन की तुलना करें। Boost uBlas लाइब्रेरी भी है जो सी ++ इंटरफेस और methods for Matrix expressions प्रदान करती है।