فرز eigenvectors بواسطة القيم الذاتية الخاصة بهم (الفرز المرتبط)

Question

لدي ناقل غير موضح من القيم الذاتية ومصفوفة ذات صلة من eigenvectors. أرغب في فرز أعمدة المصفوفة فيما يتعلق بالمجموعة المصنفة من القيم الذاتية. (على سبيل المثال ، إذا انتقلت قيمة eigenvalue [3] إلى القيمة الذاتية [2] ، فأنا أريد العمود 3 من مصفوفة eigenvector أن ينتقل إلى العمود 2.)

أعلم أنه يمكنني فرز القيم الذاتية في O(N log N) عبر std::sort. بدون تدحرج خوارزمية الفرز الخاصة بي ، كيف أتأكد من أن أعمدة المصفوفة (المتجهات المصنفة المرتبطة بها) تتبع مع قيمها الذاتية حيث يتم فرز الأخير؟

Answer 1

عادةً ما تكون مجرد إنشاء بنية شيء من هذا القبيل:

struct eigen { 
    int value;
    double *vector;

    bool operator<(eigen const &other) const { 
        return value < other.value;
    }
};

بدلاً من ذلك ، فقط ضع القيمة الذاتية/eigenvector في std::pair - على الرغم من أنني أفضل eigen.value و eigen.vector خلال something.first و something.second.

Answer 2

لقد فعلت هذا عدة مرات في مواقف مختلفة. بدلاً من فرز الصفيف ، فقط قم بإنشاء صفيف جديد يحتوي على المؤشرات المصنفة فيه.

على سبيل المثال ، لديك EVALS ARRAY (متجه) الطول ، ومصفوفات NXN ثنائية الأبعاد. قم بإنشاء فهرس صفيف جديد يحتوي على القيم [0 ، N-1].

ثم بدلاً من الوصول إلى evals كـ evals [i] ، يمكنك الوصول إليها كـ evals [index [i]] وبدلاً من evects [i] [j] ، يمكنك الوصول إليها [index [i]] [j].

الآن تكتب روتينك الفرز لفرز صفيف الفهرس بدلاً من صفيف EVALS ، لذا بدلاً من أن يبدو الفهرس مثل {0 ، 1 ، 2 ، ... ، N-1} ، ستكون القيمة في صفيف الفهرس بترتيب متزايد من القيم في صفيف evals.

لذلك بعد الفرز ، إذا قمت بذلك:

for (int i=0;i<n;++i)
{
  cout << evals[index[i]] << endl;
}

ستحصل على قائمة مصنفة من evals.

وبهذه الطريقة ، يمكنك فرز أي شيء مرتبط بمجموعة Evals دون تحريك الذاكرة بالفعل. هذا أمر مهم عندما تصبح N كبيرة ، فأنت لا تريد أن تتحرك حول أعمدة مصفوفة EVECTS.

في الأساس ، سيتم تحديد أصغر تقييم في الفهرس [i] وهذا يتوافق مع الفهرس [i] th evect.

تم تحريره لإضافة. إليك وظيفة فرز كتبتها للعمل مع STD :: Sort لفعل ما قلته للتو:

template <class DataType, class IndexType>
class SortIndicesInc
{
protected:
    DataType* mData;
public:
    SortIndicesInc(DataType* Data) : mData(Data) {}
    Bool operator()(const IndexType& i, const IndexType& j) const
    {
        return mData[i]<mData[j];
    }
};

Answer 3

يعتمد الحل بحتة على طريقة تخزين مصفوفة eigenvector الخاصة بك.

سيتم تحقيق أفضل أداء أثناء الفرز إذا كنت تستطيع التنفيذ swap(evector1, evector2) بحيث يتم إعادة تنفيذ المؤشرات فقط ويتم ترك البيانات الحقيقية دون تغيير.

يمكن القيام بذلك باستخدام شيء مثل double* أو ربما شيء أكثر تعقيدًا ، يعتمد على تنفيذ المصفوفة.

إذا تم القيام به بهذه الطريقة ، swap(...) لن يؤثر على أداء عملية الفرز.

Answer 4

من المحتمل أن تكون فكرة التكتل المتجه الخاص بك ومصفوفة أفضل طريقة للقيام بذلك في C ++. أفكر في كيفية القيام بذلك في R ومعرفة ما إذا كان يمكن ترجمة ذلك إلى C ++. في R ، من السهل جدًا ، ببساطة evec <-evec [، Order (eval)]. لسوء الحظ ، لا أعرف أي طريقة مدمجة لأداء عملية Order () في C ++. ربما يفعل شخص آخر ، وفي هذه الحالة يمكن القيام بذلك بطريقة مماثلة.