lexsort: أي مفتاح له الأولوية؟

ضع الأساسي أخيرًا

تعيد lexsort فهارس فرز مستقر بمفاتيح متعددة؛ المفتاح الأخير أساسي والسابق يكسر تعادله. [1]

نؤلف خمسة صفوف، مرقمة من صفر إلى أربعة. قيم المفتاح a هي [2,1,2,1,2]، وقيم b هي [8,5,3,5,3]. كل موضع في القائمتين يخص الصف نفسه؛ الأعداد بلا وحدة وليست درجات نموذج.

نريد المقارنة أولًا بحسب a، ثم بحسب b إذا تساوت قيمتا a. لذلك نكتب ترتيب المدخلين (b,a). نميز هذا الترتيب من الزوج (a[i],b[i]) الذي سنقرأه لوصف الصف؛ اسم الأولوية لا يتبع أول عنصر في قائمة المدخلين.

تابع ترتيب الصفوف

نقرأ الأزواج الأصلية عند المواضع 0 إلى 4: (2,8)، ثم (1,5)، ثم (2,3)، ثم (1,5)، ثم (2,3). قيم a الأصغر أولًا هي 1، فتأتي المواضع 1 و3 قبل صفوف a=2.

داخل مجموعة a=1، قيم b متساوية عند 5. يحتفظ نموذجنا بموضع 1 قبل 3 كما كانا في المصدر. داخل مجموعة a=2، تأتي قيمة b=3 قبل 8، فتسبق المواضع 2 و4 الموضع 0.

الموضعان 2 و4 يحملان الزوج (2,3) نفسه؛ يبقى 2 قبل 4. قائمة الفهارس إذن [1,3,2,4,0]. نقرأ بها المصدر فنحصل على [(1,5),(1,5),(2,3),(2,3),(2,8)].

لو أعطينا الصفوف تسميات A وB وC وD وE، ينتقل ترتيبها إلى B وD وC وE وA. نحمل المفتاحين والتسمية معًا؛ لا نرتب a ثم نترك b في ترتيبها السابق، لأن ذلك ينشئ أزواجًا غير التي بدأنا منها.

يمكن فحص النتيجة على مستويين: قيم a تصاعدية، وداخل كل مجموعة متساوية من a تكون b تصاعدية. وبعد تساوي المفتاحين معًا نراجع ترتيب المواضع الأصلية، لا مجرد تساوي الأرقام في الجدول.

عدد الصفوف بقي خمسة. تكرر (1,5) مرتين و(2,3) مرتين، لكن لكل ظهور موضعه الأصلي. الفرز الذي اخترناه لا يجعل التساوي عملية حذف أو دمج لهذه الصفوف.

قارن تبديل المفتاحين وجمعهما

نبدل ترتيب المدخلين فقط إلى (a,b). في نموذجنا تصبح الأولوية لـb: قيمها 3 ثم 5 ثم 8. مجموعة 3 تضم الموضعين 2 و4، ومجموعة 5 تضم 1 و3، وأخيرًا يأتي الموضع 0.

داخل كل مجموعة في هذا المثال، المفتاح الآخر متساوٍ أيضًا، فنحفظ الترتيب الأصلي. النتيجة [2,4,1,3,0]، مختلفة عن [1,3,2,4,0]. لم نعدل عددًا في المصدر؛ عدلنا قاعدة المقارنة بين الصفوف.

ليست المقارنة جمعًا للمفتاحين. نؤلف صفين جديدين: الصف 0 يحمل (1,100)، والصف 1 يحمل (2,0). عند جعل المركبة الأولى أساسية، 1 أقل من 2، فيسبق الصف 0 دون أن نحتاج للمركبة الثانية.

أما جمع المركبتين فيعطي 101 للصف 0 و2 للصف 1. الترتيب التصاعدي للمجموع يقدم الصف 1، فيعكس القرار. هذا مثال مضاد لاختصار يجمع الأعداد دون الاحتفاظ بأولوية المفتاح الأساسي.

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

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

راجع التعادل ونطاق الفحص

في نموذج المقارنة المستقلة نرتب الصف بحسب ثلاثية: قيمة الأساسي، ثم قيمة الثانوي، ثم رقم موضعه الأصلي. المركبة الثالثة أداة تحقق من حفظ ترتيب التعادل الكامل، وليست مفتاح بيانات جديدًا أدخلناه إلى lexsort.

بنينا نموذجًا آخر بإدراج كل موضع في قائمة مرتبة. نقارن زوجيه بالمواضع السابقة، وندرج الموضع الجديد بعد المتساويات. قارنا هذا البناء بترتيب الثلاثيات المستقل، مع حفظ المصدر.

فحصنا أطوالًا من 1 إلى 4، وكل قيمة في كل مفتاح من 0 إلى 2. لأطوال المفاتيح أعداد حالات 9 و81 و729 و6561؛ مجموعها 7380. لكل حالة فحصنا ترتيبَي الأولوية، فأصبح عدد الطلبات 14760.

لكل طلب ستة فحوص: اتفاق النموذجين، وشمول جميع الفهارس مرة واحدة، وتصاعد أزواج المقارنة، وحفظ ترتيب التعادل الكامل، وتصاعد المفتاح الأساسي، وبقاء المدخلين. مع ثمانية فحوص مباشرة أصبح الإجمالي 14760×6+8=88568، وجميعها مرت.

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

حفظ ترتيب الصفوف المتعادلة لا يقرر جدارة سجل أو جودته. في أمثلتنا الصفوف مؤلفة ولا تحمل معنى تطبيقيًا؛ الحساب يوضح الأولوية وهويات المواضع فقط.