دمج الفرز

📅 آخر تحديث: ٢٤ يوليو ٢٠٢٦
✍️ نُشر في: ٢٤ يوليو ٢٠٢٦
📷 يحتوي على 8 صور
الموسوعة الحرة

إن عملية الربط بالفرز والدمج (المعروفة أيضًا باسم الربط بالدمج) هي خوارزمية ربط وتستخدم في تنفيذ نظام إدارة قواعد البيانات العلائقية .

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

عمليًا، يُعدّ ترتيب مدخلات الخوارزمية لتقديمها بترتيب مُرتب الجزء الأكثر تكلفة في عملية دمج الفرز. يُمكن تحقيق ذلك عبر عملية فرز صريحة (غالبًا فرز خارجي )، أو بالاستفادة من ترتيب مُسبق في إحدى علاقتي الدمج أو كلتيهما. [ 1 ] يُمكن أن يحدث هذا الأخير، المُسمى بالترتيب المُثير للاهتمام، لأن أحد مُدخلات الدمج قد ينتج عن مسح فهرس قائم على شجرة، أو دمج دمج آخر، أو مُعامل تخطيط آخر يُنتج مُخرجات مُرتبة حسب مفتاح مُناسب. لا يشترط أن يكون الترتيب المُثير للاهتمام مُصادفة: فقد يبحث المُحسِّن عن هذه الإمكانية ويختار خطة غير مثالية لعملية سابقة مُحددة إذا أسفرت عن ترتيب مُثير للاهتمام يُمكن لعقدة أو أكثر من العقد اللاحقة استغلاله.

تعقيد

يتركR{\displaystyle R}وS{\displaystyle S} كن علاقات حيث|R|<|S|{\displaystyle |R|<|S|}.R{\displaystyle R}يناسبPر{\displaystyle P_{r}}صفحات الذاكرة وS{\displaystyle S}يناسبPs{\displaystyle P_{s}}ذاكرة الصفحات. في أسوأ الأحوال، سيتم تشغيل عملية دمج الفرز فييا(Pر+Ps){\displaystyle O(P_{r}+P_{s})}عمليات الإدخال/الإخراج. في حالة أنR{\displaystyle R}وS{\displaystyle S}لا يتم ترتيبها، وستتضمن تكلفة الوقت في أسوأ الحالات شروطًا إضافية تتعلق بوقت الفرز:يا(Pر+Ps+Pرسجل⁡(Pر)+Psسجل⁡(Ps)){\displaystyle O(P_{r}+P_{s}+P_{r}\log(P_{r})+P_{s}\log(P_{s}))}، وهو ما يساوييا(Pرسجل⁡(Pر)+Psسجل⁡(Ps)){\displaystyle O(P_{r}\log(P_{r})+P_{s}\log(P_{s}))}(بما أن الحدود الخطية اللاخطية تفوق الحدود الخطية، انظر ترميز Big O - رتب الدوال المشتركة ).

الشفرة الزائفة

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

دالة فرز - دمج ( اليسار : علاقة ، اليمين : علاقة ، المُقارِن : مُقارِن ) { النتيجة = علاقة جديدة () // التأكد من وجود عنصر واحد على الأقل إذا ( ! اليسار.يوجد_تالي () || ! اليمين.يوجد_تالي ()) { إرجاع النتيجة } // فرز العلاقة اليسرى واليمنى باستخدام المُقارِن اليسار.فرز ( المُقارِن ) اليمين.فرز ( المُقارِن ) // بدء خوارزمية دمج الصف الأيسر = اليسار.التالي ( ) الصف الأيمن = اليمين.التالي ( ) حلقة لا نهائية خارجية : بينما ( صحيح ) { بينما ( المُقارِن.مقارنة ( الصف الأيسر ، الصف الأيمن ) != 0 ) { إذا ( المُقارِن.مقارنة ( الصف الأيسر ، الصف الأيمن ) < 0 ) { // الصف الأيسر أصغر من الصف الأيمن إذا ( اليسار.يوجد_تالي ( ) ) { // الانتقال إلى الصف الأيسر التالي الصف الأيسر = اليسار . next () } else { break outerForeverLoop } } else { // الصف الأيسر أكبر من الصف الأيمن if ( right . hasNext ()) { // الانتقال إلى الصف الأيمن التالي rightRow = right . next () } else { break outerForeverLoop } } } // تحديد موضع الصف الأيسر والاحتفاظ بنسخة من الصف الأيسر الحالي left . mark () markedLeftRow = leftRow while ( true ) { while (comparator.compare ( leftRow , rightRow ) == 0 ) { // الصف الأيسر والصف الأيمن متساويان // أضف الصفين إلى النتيجة result = add ( leftRow , rightRow ) // انتقل إلى الصف الأيسر التالي leftRow = left.next ( ) // تحقق مما إذا كان الصف الأيسر موجودًا if ( ! leftRow ) { // تابع مع حلقة التكرار الداخلية break } } if ( right.hasNext ( )) { // انتقل إلى الصف الأيمن التالي rightRow = right.next ( ) } else { break outerForeverLoop } if ( comparator.compare ( markedLeftRow , rightRow ) == 0 ) { // أعد الصف الأيسر إلى العلامة المخزنة left.restoreMark () leftRow = markedLeftRow } else { // تحقق مما إذا كان الصف الأيسر موجودًا if ( ! leftRow ) { break outerForeverLoop } else { // تابع مع حلقة التكرار الخارجية break } } } } return result }

بما أن منطق المقارنة ليس الجانب الأساسي في هذه الخوارزمية، فهو مخفي خلف دالة مقارنة عامة، ويمكن أن يتضمن عدة معايير للمقارنة (مثل أعمدة متعددة). يجب أن تُرجع دالة المقارنة ما إذا كان صف ما أصغر من (-1) ، أو يساوي (0)، أو أكبر من (1) صفًا آخر.

دالة المقارنة ( الصف الأيسر : صف العلاقة ، الصف الأيمن : صف العلاقة ) : عدد { // تُرجع -1 إذا كان الصف الأيسر أصغر من الصف الأيمن // تُرجع 0 إذا كان الصف الأيسر مساويًا للصف الأيمن // تُرجع 1 إذا كان الصف الأيسر أكبر من الصف الأيمن }

لاحظ أن العلاقة من حيث هذه الشفرة الزائفة تدعم بعض العمليات الأساسية:

واجهة العلاقة { // تُرجع القيمة true إذا كانت العلاقة تحتوي على صف تالٍ (وإلا false) hasNext () : boolean // تُرجع الصف التالي من العلاقة (إن وُجد) next () : RelationRow // تُرتّب العلاقة باستخدام المُقارِن المُعطى sort ( comparator : Comparator ) : void // تُعلّم فهرس الصف الحالي mark () : void // تُعيد فهرس الصف الحالي إلى فهرس الصف المُعلّم restoreMark () : void }

تطبيق بسيط بلغة C#

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

public class MergeJoin { // نفترض أن left و right مُرتبتان بالفعل public static Relation Merge ( Relation left , Relation right ) { Relation output = new Relation (); while ( ! left . IsPastEnd && ! right . IsPastEnd ) { if ( left . Key == right . Key ) { output . Add ( left . Key ); left . Advance (); right . Advance (); } else if ( left . Key < right . Key ) left . Advance (); else // if (left.Key > right.Key) right . Advance (); } return output ; } } public class Relation { private const int ENDPOS = - 1 ; private List < int > list ; private int position = 0 ;public Relation () { this . list = new List < int > (); }public Relation ( List < int > list ) { this . list = list ; }public int Position => position ;public int Key => list [ position ];public bool IsPastEnd => position == ENDPOS ;public bool Advance () { if ( position == list . Count - 1 || position == ENDPOS ) { position = ENDPOS ; return false ; } position ++ ; return true ; }public void Add ( int key ) { list . Add ( key ); }public void Print () { foreach ( int key in list ) Console . WriteLine ( key ); } }

انظر أيضاً

مراجع

  1. ↑ "عمليات الربط بالفرز والدمج" . www.dcs.ed.ac.uk. تم الاطلاع عليه بتاريخ 2022-11-02 .

تطبيقات بلغة C# لخوارزميات الربط المختلفة