الدمج المستقر للسجلات: حفظ ترتيب التعادل في التصاعد والتنازل

معنى ثبات ترتيب المتساويات

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

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

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

[1]

أربعة سجلات بهويات لا ترتيب أبجدي

الإدخال الأصلي يتكون من q3 بمفتاح 2، ثم q1 بمفتاح 1، ثم q2 بمفتاح 2، ثم q4 بمفتاح 1. هذه الأسماء معرفات فقط؛ لا نقرأ الرقم في q3 بوصفه موضع الإدخال أو قيمة مفتاح المقارنة. q3 هو أول ظهور في قائمتنا رغم أن اسمه يحوي ثلاثة، وq1 هو الثاني رغم أن اسمه يحوي واحدًا.

في التصاعد بحسب المفتاح وحده، يجب أن تسبق سجلات المفتاح 1 سجلات المفتاح 2. وبين صاحبي المفتاح 1 يبقى q1 قبل q4 لأنه كان قبله في الأصل. وبين صاحبي المفتاح 2 يبقى q3 قبل q2. النتيجة المستقرة إذن q1 ثم q4 ثم q3 ثم q2، مع انتقال كل مفتاح بجانب هويته الصحيحة.

الرسم الرئيسي يعرض المدخل والاتجاهين، كي نرى أن الاستقرار علاقة بين هويات وليس شكل صف أعداد فقط. يمكن لنتيجة q1 ثم q4 ثم q2 ثم q3 أن تحمل مفاتيح تصاعدية صحيحة، لكنها عكست صاحبي المفتاح 2 بالنسبة للأصل. صحة اتجاه المفاتيح شرط، وحفظ ترتيب التعادل شرط آخر نفحصه على السجلات نفسها.

الفرز حسب المفتاح فقط

نختار الحقل العددي الثاني مفتاحًا وحيدًا للفرز. لذلك لا تقارن دالتنا أسماء q3 وq2 لتقرر من يأتي أولًا حين يحملان 2. إذا دخلت الهوية في المقارنة كمفتاح ثانوي، فقد يتقدم q2 أبجديًا على q3، لكن هذا سيكون فرزًا بعقد مختلف. لا نسمي التغيير خطأ في حساب الأبجدية؛ نسميه إضافة معيار لم يكن في هدفنا الأصلي.

وجود هويتين مختلفتين بمفتاح واحد لا يجعل السجلين سجلًا واحدًا. لن تحذف دالتنا واحدًا منهما أو تدمج قيمتيهما؛ الناتج يحفظ كل ظهور ويغير ترتيب عرضه فقط. إذا احتاج المستخدم إزالة تكرار، فهذه عملية مستقلة يجب أن تعرف ما الذي يعد تكرارًا: الهوية أو المفتاح أو السجل الكامل. مساواة المفتاح وحدها لا تحدد هذا القرار.

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

مراحل عرض واحد ثم اثنين ثم أربعة

ينظر تنفيذنا في البداية إلى كل عنصر منفرد بوصفه جزءًا مرتبًا طوله واحد. يدمج أول زوج من الأجزاء، ثم الزوج التالي، حتى يبني أجزاء أكبر. في مثالنا يدمج q3 بمفتاح 2 مع q1 بمفتاح 1، فتكون نتيجة هذا الزوج q1 ثم q3. ويدمج q2 مع q4، فتكون النتيجة q4 ثم q2.

بعد مرور العرض واحد، صار لدينا جزآن مرتبان بطول اثنين: اليسار q1 ثم q3، واليمين q4 ثم q2. يضاعف الكود العرض إلى اثنين ويدمجهما. حين ينتهي هذا الدمج، يصير طول الجزء المرتب أربعة ويغطي القائمة كلها، فلا نحتاج مرورًا أكبر في هذه الحالة الصغيرة.

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

اختيار اليسار عند تعادل مفتاح الدمج

في الدمج الأخير للمثال، نقارن q1 بالمفتاح 1 في اليسار مع q4 بالمفتاح 1 في اليمين. عند المساواة نختار اليسار، فيخرج q1 أولًا. نقارن بعده q3 بالمفتاح 2 مع q4 بالمفتاح 1، فنختار q4. ثم يتعادل q3 وq2 بالمفتاح 2، فنختار اليسار مرة أخرى فيخرج q3 قبل q2.

إذا بدلنا شرط التصاعد من أصغر أو مساوٍ إلى أصغر فقط، صار التعادل يدفع الكود إلى اختيار اليمين. في هذه الحالة يتقدم q4 على q1، وقد يتقدم q2 على q3. تبقى المفاتيح مرتبة، لكن نتيجة التعادل تخالف أصلنا. هذا مثال دقيق يبين أن تغيير رمز مساواة في شرط الدمج قد يغير ضمانًا لا يظهر في صف الأعداد.

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

لماذا يحفظ دمج مستقر ترتيب الأصل؟

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

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

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

التنازل المستقر يختلف من عكس التصاعد

في الاتجاه التنازلي نريد المفتاح 2 قبل 1، مع بقاء q3 قبل q2 داخل المفتاح 2، وq1 قبل q4 داخل المفتاح 1. لذلك النتيجة المستقرة هي q3 ثم q2 ثم q1 ثم q4. نغير جهة مقارنة المفاتيح، لكننا نبقي اختيار اليسار عند المساواة، لأن الأصل الذي نقيس به ترتيب المتعادلات لم يتغير.

أما عكس قائمة التصاعد السابقة q1 ثم q4 ثم q3 ثم q2 فيعطي q2 ثم q3 ثم q4 ثم q1. مفاتيحها تنازلية بالفعل، لكنها عكست ترتيب التعادل في المجموعتين. لهذا لا نستعمل عملية عكس واحدة بديلًا تلقائيًا من تنازل مستقر، ولا نستنتج نجاح الاستقرار من رؤية المفتاح 2 في مقدمة الناتج فقط.

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

عرض الرسم بالحجم الكامل

الكود الأصلي وعقد المدخل

الدالة التالية تقبل تتابعًا من سجلات ذات حقلين: هوية نصية ومفتاح من نوع int العادي. ترفض مفتاحًا عشريًا أو نصيًا أو bool بدل تحويله إلى رقم ضمنيًا. كما تتوقع اتجاهًا منطقيًا صحيحًا في descending. هذه حدود اخترناها للتنفيذ التعليمي، ولا تعني أن كل خوارزمية فرز يجب أن تحصر أنواع المفاتيح في الأعداد الصحيحة.

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

ترجع الدالة tuple من السجلات المرتبة، ولا تستعمل sorted داخلها لإخفاء الدمج. نستخدم sorted المستقرة بوصفها مرجعًا مستقلًا في الفحوص، وليس تنفيذًا داخليًا للدالة المعروضة. كما أن هذا الكود ليس نسخة من خوارزمية الفرز التي تنفذها Python في أدواتها؛ هو بناء أصلي صغير يوضح قرارات الدمج على سجلات بسيطة معلومة.

def stable_merge_records(records, descending=False):
    if type(descending) is not bool:
        raise TypeError("boolean direction required")
    work = list(records)
    for identity, value in work:
        if not isinstance(identity, str) or type(value) is not int:
            raise TypeError("text identity and integer key required")
    width = 1
    while width < len(work):
        output = []
        for start in range(0, len(work), 2 * width):
            left = work[start:start + width]
            right = work[start + width:start + 2 * width]
            i = j = 0
            while i < len(left) and j < len(right):
                a, b = left[i][1], right[j][1]
                take_left = a >= b if descending else a <= b
                if take_left:
                    output.append(left[i])
                    i += 1
                else:
                    output.append(right[j])
                    j += 1
            output.extend(left[i:])
            output.extend(right[j:])
        work = output
        width *= 2
    return tuple(work)

مفتاح مركب يغير معنى التعادل

نعود إلى السجلين q3 وq2 اللذين يحملان المفتاح 2. إذا اخترنا المفتاح مركبًا من العدد ثم الهوية، فإن المفتاحين الكاملين لم يعودا متساويين: أحدهما يحمل q3 والآخر q2 في جزئه الثاني. عندئذ يمكن أن يأتي q2 قبل q3 وفق مقارنة ذلك الجزء، ولا يكون ذلك مثالًا على كسر الاستقرار بين مفتاحين كاملين متساويين.

لهذا نكتب ما الذي يدخل في المفتاح قبل تقييم النتيجة. في كودنا يدخل العدد وحده، فتظل علاقة q3 قبل q2 جزءًا من العقد. وفي جدول آخر يمكن أن تدخل أولوية أو وقت وصول موثق، فتكون المقارنة مختلفة. لا نخلط حقلًا محفوظًا داخل السجل بحقل يستخدمه الفرز؛ وجود الهوية في الناتج لا يعني أنها حسمت ترتيبًا أبجديًا.

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

القيم والهويات تنتقل معًا

ينقل الدمج السجل نفسه إلى الناتج، لا العدد منفصلًا عن الهوية. لذلك يظل q1 حاملًا للمفتاح 1 وq3 حاملًا للمفتاح 2 بعد الترتيب. لو رتبنا الأعداد في عمود ثم أبقينا عمود الأسماء كما كان، فقد ننسب قيمة إلى سجل آخر. هذا خطأ في نقل العلاقات، حتى لو كانت قائمة الأعداد الجديدة مصفوفة تصاعديًا بصورة صحيحة.

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

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

نسخة خارجية لا تنسخ السجل بعمق

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

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

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

الحالات الفارغة والمفردة والأطوال الفردية

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

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

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

فحوص مستقلة على الاتجاهين

ننشئ قوائم صغيرة بمفاتيح من سالب 1 وصفر و2، وبأطوال من صفر إلى سبعة. لكل ظهور هوية تميزه من غيره، ثم نقارن ناتج دمجنا بـsorted مع مفتاح العدد وحده في كلا الاتجاهين. لا يكفي مقارنة قائمة المفاتيح؛ نطابق السجلات كاملة حتى يظهر أي قلب غير مقصود بين المتعادلات.

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

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

حدود كلفة الفرز وبطاقة النتيجة

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

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

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