मैट्रिक्स गुणन एल्गोरिथम का अनुकूलन

Dec 28 2020

मैंने एल्गोरिथ्म के अपने स्वयं के संस्करण को दो मैट्रिसेस को एक साथ गुणा करने के लिए लागू किया है और मुझे किसी ऐसे व्यक्ति की आवश्यकता है जो यह जानता हो कि वे क्या कर रहे हैं यदि ऐसा कुछ है जो अधिक इष्टतम तरीके से किया जा सकता है। मैं यह समझने के लिए भी उत्सुक हूं कि मैं इसे कैसे मजबूत बना सकता हूं कि यह तब दुर्घटनाग्रस्त न हो जब गैर-आयताकार मैट्रेस को तर्क के रूप में पारित किया जाता है अर्थात मैट्रिक्स जिसमें विभिन्न तत्वों की असमान संख्या होती है Vd।

मुझे matrixDotकोड बलो में फ़ंक्शन में विशेष रूप से दिलचस्पी है , बाकी सब केवल यह दिखाने के लिए है कि मैं अपने प्रोजेक्ट में इसका उपयोग कैसे कर रहा हूं)।

#include "iostream"
#include <vector>

#define LOG(m) std::cout << m << std::endl

struct Vd
{
    std::vector<double> v;
};

struct Md
{
    std::vector<Vd> m;

    //fill matrix with num
    void fill(unsigned const int rows, unsigned const int cols, const double num)
    {
        m.clear();
        for (unsigned int i = 0; i < rows; i++)
        {
            Vd tempVec;
            for (unsigned int j = 0; j < cols; j++)
            {
                tempVec.v.push_back(num);
            }
            m.push_back(tempVec);
        }
    }

    friend std::ostream& operator << (std::ostream& out, const Md& mat)
    {
        out << "[" << std::endl << std::endl;
        for (unsigned int i = 0; i < mat.m.size(); i++)
        {
            out << "[";
            for (unsigned int j = 0; j < mat.m[i].v.size(); j++)
            {
                if (j % mat.m[i].v.size() == mat.m[i].v.size() - 1)
                    out << mat.m[i].v[j] << "]" << std::endl << std::endl;
                else
                    out << mat.m[i].v[j] << ", ";
            }
        }
        out << "]" << std::endl;
        return out;
    }
};

inline void matrixDot(const Md& m1, const Md& m2, Md& outm)
{
    if (m1.m[0].v.size() && m2.m.size())
        if (m1.m[0].v.size() != m2.m.size())
        {
            LOG("Shape mismatch: " << "matrix1 columns: " << m1.m[0].v.size() << ", " << "matrix2 rows: " << m2.m.size());
            throw std::exception();
        }

    unsigned int m1x = 0; unsigned int m1y = 0; unsigned int m2y = 0; //m2x = m1y

    while (outm.m.size() < m1.m.size())
    {
        Vd tempv;
        while (tempv.v.size() < m2.m[0].v.size())
        {
            double total = 0.0;
            while (m1x < m1.m[0].v.size())
            {
                total += m1.m[m1y].v[m1x] * m2.m[m1x].v[m2y];
                m1x++;
            }
            tempv.v.push_back(total);
            m1x = 0;
            m2y < m2.m[0].v.size() - 1 ? m2y++ : m2y = 0;
        }
        m1y < m1.m.size() - 1 ? m1y++ : m1y = 0;
        outm.m.push_back(tempv);
    }
}

int main()
{
    Md mat1;
    mat1.fill(5, 2, 1.0);
    Md mat2;
    mat2.fill(2, 6, 2.0);
    Md mat3;
    matrixDot(mat1, mat2, mat3);
    std::cout << mat3;
}

जवाब

1 Edward Dec 30 2020 at 04:55

मुझे कुछ चीजें दिखाई देती हैं जिनका उपयोग आप अपने कोड को बेहतर बनाने के लिए कर सकते हैं।

`using`जहाँ उचित हो उपयोग करें

वर्तमान में कोड में यह शामिल है:

struct Vd
{
    std::vector<double> v;
};

इसकी जगह शायद इस तरह से बेहतर व्यक्त किया गया है:

using Vd = std::vector<double>;

तो अब, यह लिखने के बजाय:

out << mat.m[i].v[j] << ", ";

हम इस क्लीनर सिंटैक्स का उपयोग कर सकते हैं:

out << mat.m[i][j] << ", ";

हेडर को समझें पथ शामिल हैं

के बीच एक सूक्ष्म अंतर है #include "iostream"और #include <iostream>। यद्यपि यह कार्यान्वयन परिभाषित है, अधिकांश संकलक कार्यान्वयन यह है कि उद्धरण चिह्न फ़ॉर्म पहले स्थानीय रूप से खोज करता है (उदाहरण के लिए वर्तमान निर्देशिका) और फिर खोज प्रणाली में निर्देशिका शामिल होती है यदि वह विफल हो जाती है। आमतौर पर सिस्टम में खोज करने वाले कोण ब्रैकेट फॉर्म में निर्देशिकाएं शामिल होती हैं। इस प्रश्न को और देखें । इस कारण से, इस कोड का उपयोग करना चाहिए #include <iostream>।

`std::endl`यदि आपको वास्तव में इसकी आवश्यकता नहीं है तो उपयोग न करें

यह अंतर विश्वासघात है std::endlऔर '\n'वह यह है कि '\n'सिर्फ एक नई std::endlरेखा चरित्र का उत्सर्जन करती है, जबकि वास्तव में धारा प्रवाहित होती है। यह बहुत सारे I / O के साथ एक कार्यक्रम में समय लेने वाला हो सकता है और वास्तव में इसकी आवश्यकता शायद ही हो। यह केवलstd::endl तब उपयोग करना सबसे अच्छा है जब आपके पास स्ट्रीम को फ्लश करने के लिए कुछ अच्छा कारण है और इसे इस तरह के सरल कार्यक्रमों के लिए बहुत बार आवश्यक नहीं है। std::endlजब आप '\n'करेंगे तब उपयोग की आदत से बचना भविष्य में लाभांश का भुगतान करेगा क्योंकि आप अधिक I / O के साथ अधिक जटिल कार्यक्रम लिखते हैं और जहां प्रदर्शन को अधिकतम करने की आवश्यकता होती है।

जहाँ उपयुक्त हो, मानक कार्यों का उपयोग करें

ostream& operator<<आपके पास जैसा है उसे लिखने के बजाय , एक स्वच्छ विकल्प का उपयोग करना std::copyऔर std::experimental::ostream_joinerइस तरह करना होगा:

friend std::ostream& operator << (std::ostream& out, const Md& mat)
{
    out << "[\n";
    for (const auto& row : mat.m) {
        out << "\t[";
        std::copy(row.begin(), row.end(), std::experimental::make_ostream_joiner(out, ", "));
        out << "]\n";
    }
    return out << "]\n";
}

आउटपुट मानों के लिए रिटर्न मानों को प्राथमिकता दें

matrixDotआउटपुट पैरामीटर के रूप में तीसरे पैरामीटर का उपयोग करने के बजाय नए मैट्रिक्स को वापस लौटना अधिक तर्कसंगत लगता है । अधिक जानकारी के लिए F.20 देखें ।

एक वैकल्पिक प्रतिनिधित्व पर विचार करें

यह कोड दोनों में कुछ नाजुक है Mdऔर सभी सदस्यों के साथ सार्वजनिक Vdरूप से लागू किया जाता है struct। इससे भी बदतर, यह है कि हम एक दांतेदार सरणी हो सकते हैं जिसमें प्रत्येक पंक्ति में समान आइटम नहीं होते हैं। यह शायद कुछ भी अच्छा परिणाम नहीं जा रहा है। उन दोनों कारणों के लिए, मैं सभी वस्तुओं को रखने के लिए classएक का उपयोग करके और एक का उपयोग करने का सुझाव vectorदूंगा। इस सवाल को कुछ विचारों और सलाह के लिए देखें कि यह कैसे करना है। आप std::valarrayएक अंतर्निहित प्रकार के रूप में भी देख सकते हैं ।

एक पूर्ण वर्ग कार्यान्वयन प्रदान करें

एक निर्माणकर्ता के std::initializer_listतर्क के अलावा , मैं कुछ अन्य ऑपरेटरों जैसे कि operator==इस वर्ग के लिए भी सुझाव दूंगा।

3 Bhaskar Dec 28 2020 at 09:20

मुझे स्वीकार करना होगा कि मैं थोड़ा भ्रमित हूं, आपने कठिन भागों को किया है और आसान भागों पर एक प्रश्न है? मैं आपके प्रश्न को गलत समझ सकता हूं।

मैं यह समझने के लिए भी उत्सुक हूं कि मैं इसे कैसे मजबूत बना सकता हूं कि यह दुर्घटनाग्रस्त न हो जब गैर-आयताकार मैट्रिक्स को तर्क के रूप में पारित किया जाता है अर्थात मैट्रिक्स जिसमें असमान संख्या में विभिन्न तत्वों की संख्या होती है।

आप यह सत्यापित कर सकते हैं कि आपके पास एक अच्छी तरह से बनाई गई मैट्रिक्स है

inline bool isValid(const Md& mat)
{
    if (mat.m.size())
    {
        int size = mat.m[0].v.size();
        for (int i = 1; i < mat.m.size(); i++) {
            if (size != mat.m[i].v.size())
            {
                return false;
            }
        }    
    }
    
    return true;
}

और इसे matrixDotसत्यापन के लिए फ़ंक्शन में शामिल करना, आपके पास अभी जो आकार सत्यापन है, उसके समान सत्यापन के लिए

    if (m1.m[0].v.size() && m2.m.size())
        if (m1.m[0].v.size() != m2.m.size())
        {
            LOG("Shape mismatch: " << "matrix1 columns: " << m1.m[0].v.size() << ", " << "matrix2 rows: " << m2.m.size());
            throw std::exception();
        }
        
    if (!isValid(m1))
    {
        LOG("Invalid matrix :: " << std::endl);
        std::cout << m1;
        throw std::exception();
    }
    
    if (!isValid(m2))
    {
        LOG("Invalid matrix :: " << std::endl);
        std::cout << m2;
        throw std::exception();
    }

कोई भी अनुकूलन जिनके बारे में मैं सोच सकता हूं कि आप उपयोग std::arrayकरने के बजाय std::vectorपंक्ति और स्तंभ की लंबाई के बारे में जानते हैं।

3 GarryR Dec 29 2020 at 16:57

व्यक्तिगत रूप से मैं Md संरचना (वर्ग) का विस्तार करूंगा ताकि यह मैट्रिक्स को पूरी तरह से एन्क्रिप्ट कर दे। यह होता है:

-> सदस्य चर:

    The number of rows and columns.   
    Vector to hold the data.  (Consider one dimensional array here).

-> कंस्ट्रक्टर जो सही आकार के मैट्रिक्स को बनाने की अनुमति देगा (पंक्तियाँ, कॉल)।

    This would allow you to use vector resize and reserve which will give you 
    a more performant implementation, especially if the matrices are re-used.
    So avoid using push_back and instead set values directly.

-> पंक्तियों / स्तंभों की संख्या प्राप्त करने के लिए कार्य करें

-> मैट्रिक्स डेटा मूल्यों को प्राप्त / सेट करने के लिए फ़ंक्शन प्राप्त / सेट करें।

    Get/Set functions implement bounds checking.

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

फिर जैसा कि पहले वाले पोस्टर ने सुझाव दिया था कि यह अमान्य है या कैन्टुल्टीली फ़ंक्शन समाधान को और अधिक मजबूत बनाने में मदद करेगा।