مضاعفة المصفوفة باستخدام أزواج

Question

أنا أبحث في طرق بديلة للقيام بتكاثر المصفوفة. بدلاً من تخزين المصفوفة الخاصة بي كصفيف ثنائي الأبعاد ، أستخدم متجهًا مثل

vector<pair<pair<int,int >,int > > 

لتخزين المصفوفة الخاصة بي. يخزن الزوج داخل زوجي (زوج) مؤشراتي (I ، J) والآخر يخزن القيمة لزوج (I ، J). اعتقدت أنني قد يكون لدي حظ في تنفيذ صفيفتي المتفرقة بهذه الطريقة.

المشكلة هي عندما أحاول مضاعفة هذه المصفوفة مع نفسها.

إذا كان هذا تطبيق صفيف ثنائي الأبعاد ، كنت سأضرب المصفوفة على النحو التالي:

   for(i=0; i<row1; i++)
    {
        for(j=0; j<col1; j++)
        {
          C[i][j] = 0;
         for(k=0; k<col2; k++) 
           C[i][j] += A[i][j] * A[j][k];
      }
    }

هل يمكن لأي شخص أن يشير إلى طريقة لتحقيق نفس النتيجة باستخدام متجه "زوج الأزواج"؟

شكرًا

Answer 1

حتى الآن يمكنك تخزين قيمة واحدة في مكان واحد. إذا كنت ترغب في تخزين العديد من الإدخالات غير صفرية في المصفوفة ، فستحتاج إلى المزيد من الأزواج في هيكل أكبر.

map<pair<int, int>, int> ستكون الخطوة المنطقية التالية. الآن يمكنك التكرار فوق الصفوف لأن first التنسيق أكثر أهمية في mapأمر الفرز.

للتكرار على الأعمدة ، عكس تلك الأسبقية:

typedef pair<int, int> mx_coord;
struct reverse_compare {
    bool operator() (mx_coord const &l, mx_coord const &r) const
        { return l.second < r.second? true :
                 r.second < l.second? false : l.first < r.first; }
};

typedef map< mx_coord, int > matrix;
typedef map< mx_coord, int, reverse_compare > matrix_transpose;

لتضرب A بواسطة B ، عبر B ، وتكرار وتكرار على A و B ، وضرب أي عناصر تتطابق إحداثيات أقل أهمية ، حيث يتيح لك الطلب بشكل طبيعي الذهاب إلى خط تلو الآخر.

لتنقل ب:

matrix_transpose b_t( b.begin(), b.end() ); // complexity: n log n