argsort: ابنِ عكس التبديل لاستعادة الترتيب

اقرأ تبديل المواضع

في الحالة الأحادية، تختار فهارس argsort القيم المرتبة. [1]

نؤلف a=[8,−3,8,2,5] ونرقم مواضعها من صفر إلى أربعة. الأعداد بلا وحدة، ولا تمثل درجات نموذج أو سجلات فعلية. نختار p=[1,3,4,0,2] يدويًا: كل موضع يظهر مرة واحدة، وجميع المواضع ممثلة.

القراءة وفق p تعني أخذ a عند 1 ثم 3 ثم 4 ثم صفر ثم 2. نحصل على b=[−3,2,5,8,8]. الفهرس صفر الذي ظهر رابعًا في p يخص أول 8 في المصدر؛ أما الفهرس 2 الذي ظهر أخيرًا فيخص ثمانية أخرى.

نعرّف في نموذج القوائم b[j]=a[p[j]]. الفهرس j يخص الناتج، والقيمة p[j] تخص المصدر. كلاهما رقم موضع، لكنهما يشيران إلى قائمتين مختلفتين. لا نستبدل p[j] بالعدد الموجود هناك.

لم نشغل argsort للحصول على p؛ إنها قائمة فرز صحيحة اخترناها وفحصناها. لا نستنتج منها ترتيبًا يضمنه خيار مكتبة عند تعادل القيم. غرضنا الحالي عكس قائمة الفهارس التي نملكها فعلًا.

ابنِ قائمة العكس

نحتاج لكل موضع أصلي i معرفة مكانه الجديد j. لأن p تضم كل موضع مرة واحدة، يوجد j وحيد يحقق p[j]=i. نسمي هذا المكان q[i]. عمليًا نمر على j ونكتب q[p[j]]=j.

في مثالنا: p[0]=1 فنكتب q[1]=0؛ ثم p[1]=3 فنكتب q[3]=1؛ وبعد p[2]=4 نكتب q[4]=2. وأخيرًا p[3]=0 يعطي q[0]=3، وp[4]=2 يعطي q[2]=4. تصبح q=[3,0,4,1,2].

لنقرأ b وفق q: الموضع 3 يحمل 8، وصفر يحمل −3، و4 يحمل 8، و1 يحمل 2، و2 يحمل 5. هذه a الأصلية بالترتيب. لم نحذف إحدى الثمانيتين أو نفترض أن قيمتها تحدد هويتها وحدها.

البرهان لا يعتمد على الأعداد الخمسة: من تعريف العكس p[q[i]]=i. وبالتعويض في تعريف b نحصل على b[q[i]]=a[p[q[i]]]=a[i]. تتحقق المساواة عند كل موضع، فتعود القائمة كاملة.

أما إعادة استخدام p مع b فتعطي b عند 1 و3 و4 وصفر و2: [2,8,8,−3,5]. لم نحسب عكسًا؛ طبقنا اختيارًا آخر له الأرقام السابقة نفسها. كون p رتبت المصدر أول مرة لا يجعلها صالحة لإلغاء ترتيبها.

متى يكفي تكرار التبديل؟

بعد تطبيق p مرتين، القيمة عند j هي a[p[p[j]]]. لكي تعود هوية كل موضع لأي بيانات نضعها، نحتاج p[p[j]]=j للجميع. هذا شرط كافٍ بالتعويض، ولازم أيضًا إذا ميزنا المواضع بتسميات مختلفة: أي موضع مخالف يحمل تسمية موضع آخر.

مثلًا التبديل [1,0] يبادل موضعين. عند تكراره يرجع كل منهما إلى مكانه: [10,20] تتحول إلى [20,10] ثم [10,20]. هنا p تساوي عكسها؛ لا نعمم الخاصية على جميع التبديلات.

الدورة [1,2,0] مختلفة. التسميات [0,1,2] تصبح [1,2,0] ثم [2,0,1]؛ لم تعد إلى الأصل. لكن القيم [4,4,4] تظل تبدو [4,4,4] بعد الاختيارين. نجاح فحص القيم المتساوية وحده لا يثبت رجوع الهويات.

نعود إلى مثال الثمانيتين ونختار p′=[1,3,4,2,0]. قيم b ما زالت [−3,2,5,8,8]؛ تبدل ترتيب الموضعين الأصليين صفر و2 في نهاية الفرز. عكس هذا الاختيار q′=[4,0,3,1,2]، لا q السابق.

إذا نقلنا التسميات الأصلية [0,1,2,3,4] وفق p′، صارت [1,3,4,2,0]. يعيد q′ هذه التسميات، بينما استخدام q القديم معها يعطي [2,1,0,3,4]. الثمانيتان أخفتا التبديل في القيم، لكن تسميتيهما بقيتا مختلفتين.

إذن نحفظ خريطة الفرز التي استعملناها، لا القيم المرتبة وحدها. أسماء المواضع هنا أدوات مراجعة مؤلفة؛ لا تعني أن عددين متساويين يخصان الشخص أو الحدث نفسه في بيانات حقيقية.

احفظ التبديل ونطاق الفحص

بناء q السابق يفترض أن p تبديل كامل لمواضع من صفر إلى n−1: طولها n، وكل موضع فيها صحيح ومختلف. قائمة فهارس قصيرة أو مكررة لا تحقق هذا الفرض، فلا نسمي الناتج بالطريقة نفسها عكسًا يعيد كل موضع.

نحفظ المصدر وقائمة p والنسخة الناتجة عنها وقائمة q معًا. إذا تغير ترتيب المصدر أو طولُه، نراجع هذه العلاقة قبل القراءة. تفسير الفهارس يتبع نسخة القائمة، ولا يجعل رقم الموضع معرفًا دائمًا بين نسخ مختلفة.

فحصنا كل التبديلات للأطوال صفر إلى ستة: أعدادها 1 و1 و2 و6 و24 و120 و720؛ مجموعها 874. بنينا العكس بوضع كل موضع في خانته، وقارناه ببحث مستقل عن ذلك الموضع داخل p.

لكل تبديل عشرة فحوص: اتفاق العكسين، هويتا تركيب الفهارس، الاستعادة في الاتجاهين، شرط رجوع جميع التسميات عند التكرار، استعادة قيم متكررة، صحة مواضع العكس، عكس العكس وبقاء المدخل. ومع ثمانية فحوص مباشرة أصبح المجموع 8748.

في نموذجنا الفارغ لا يوجد موضع يحتاج إلى نقل، وفي طول واحد يكون التبديل الوحيد هو الهوية. هذه حالات لقوائم مؤلفة، وليست مخرجات تشغيل NumPy. البرهان الخاص بالعكس يشمل كل تبديل كامل، أما الفحص العددي فاقتصر على الأطوال المذكورة.

لم نشغل NumPy أو نختبر خوارزمية فرز أو ضمان استقرارها الافتراضي، ولم نفحص محاور متعددة أو NaN أو الأنواع المركبة أو ترتيبًا تنازليًا أو الذاكرة والزمن. المثال يثبت علاقات المواضع في نموذجنا، ولا يقيس جودة بيانات أصلية أو نموذج تعلم.