فرز الدمج متعدد المراحل

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

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

تُرتّب خوارزمية فرز الدمج "المتوازنة" البياناتَ في أربعة ملفات عمل، حيث تُقسّمها إلى ملفي إدخال وملفي إخراج. تُوزّع البيانات بالتساوي بين ملفي عمل، إما على شكل مجموعات مُرتّبة أو، في أبسط الحالات، على شكل سجلات مفردة، والتي يُمكن اعتبارها مجموعات مُرتّبة بحجم 1. بمجرد نقل جميع البيانات إلى ملفي العمل، يُصبح هذان الملفان هما ملفي الإدخال لأول عملية دمج. في كل عملية دمج، تُدمج المجموعات من ملفي الإدخال، مع تبديل الإخراج المدمج بين ملفي الإخراج، ثم يُوزّع الإخراج المدمج بالتساوي بينهما (حتى عملية الدمج الأخيرة). بعد دمج جميع المجموعات من ملفي الإدخال وإخراجها، يُصبح ملفا الإخراج هما ملفي الإدخال، والعكس صحيح، في عملية الدمج التالية. يقل عدد مرات التشغيل بمقدار النصف في كل تكرار، على سبيل المثال: 64، 32، 16، 8، 4، 2، 1. في تكرار الدمج الأخير، يحتوي كل من ملفي الإدخال على تشغيل مُرتب واحد فقط (نصف مجموعة البيانات)، وتكون نتيجة الدمج عبارة عن تشغيل مُرتب واحد (مجموعة البيانات المُرتبة) في أحد ملفي الإخراج. يُشرح هذا أيضًا في قسم " فرز الدمج" § "  الاستخدام مع محركات الأشرطة" .

إذا كان هناك ثلاثة ملفات عمل فقط، فإن خوارزمية فرز الدمج المتوازن تدمج عمليات التشغيل المُرتبة من ملفي عمل في ملف عمل واحد، ثم توزع عمليات التشغيل بالتساوي بين ملفي الإخراج. تقلل عملية الدمج عدد عمليات التشغيل بمقدار النصف، بينما لا تقلل عملية إعادة التوزيع عدد عمليات التشغيل (المعامل هو 1). يمكن اعتبار كل تكرار أنه يقلل عدد عمليات التشغيل بمعامل متوسط ​​قدره √2 ≈ 1.41. أما إذا كان هناك خمسة ملفات عمل، فإن النمط يتناوب بين دمج ثلاثي ودمج ثنائي، بمعامل متوسط ​​قدره √6 ≈ 2.45.

بشكل عام، بالنسبة لعدد زوجي N من ملفات العمل، فإن كل تكرار لفرز الدمج المتوازن يقلل عدد مرات التشغيل بمعامل N /2، بينما بالنسبة لعدد فردي N من ملفات العمل، فإن كل تكرار يقلل عدد مرات التشغيل بمعامل متوسط ​​√ ( N ² −1)/4 = √ N ² −1 /2.

بالنسبة لعدد ملفات العمل N < 8، يحقق فرز الدمج متعدد المراحل عامل تقليل فعال أعلى لعدد مرات التشغيل من خلال توزيع عمليات التشغيل المصنفة بشكل غير متساوٍ بين N − 1 ملف عمل (موضح في القسم التالي). في كل تكرار، تُدمج عمليات التشغيل من N − 1 ملف عمل في ملف إخراج واحد. عند الوصول إلى نهاية أحد ملفات العمل N − 1، يصبح هو ملف الإخراج الجديد، ويصبح ملف الإخراج السابق أحد ملفات الإدخال N − 1، مما يبدأ تكرارًا جديدًا لفرز الدمج متعدد المراحل. يدمج كل تكرار جزءًا فقط من مجموعة البيانات (من النصف إلى ثلاثة أرباعها تقريبًا)، باستثناء التكرار الأخير الذي يدمج مجموعة البيانات بأكملها في عملية تشغيل مصنفة واحدة. يتم إعداد التوزيع الأولي بحيث يتم إفراغ ملف عمل إدخال واحد فقط في كل مرة، باستثناء تكرار الدمج النهائي الذي يدمج N −1 عمليات تشغيل فردية (بأحجام متفاوتة، وسيتم شرح ذلك لاحقًا) من N −1 ملفات عمل الإدخال إلى ملف الإخراج الفردي، مما ينتج عنه عملية تشغيل واحدة مرتبة، وهي مجموعة البيانات المرتبة.

في كل تكرار متعدد المراحل، يتبع العدد الإجمالي للتكرارات نمطًا مشابهًا لمتتالية أعداد فيبوناتشي المعكوسة ذات الرتبة الأعلى . مع 4 ملفات، ومجموعة بيانات تتكون من 57 تكرارًا، يكون إجمالي عدد التكرارات في كل تكرار كالتالي: 57، 31، 17، 9، 5، 3، 1. ^{[ 1 ] [ 2 ]} لاحظ أنه باستثناء التكرار الأخير، يكون عامل تقليل عدد التكرارات أقل بقليل من 2، أي 57/31، 31/17، 17/9، 9/5، 5/3، 3/1، أي حوالي 1.84 لحالة 4 ملفات، ولكن كل تكرار باستثناء الأخير قلل عدد التكرارات أثناء معالجة حوالي 65% من مجموعة البيانات، لذا فإن عامل تقليل عدد التكرارات لكل مجموعة بيانات تمت معالجتها خلال التكرارات الوسيطة هو حوالي 1.84 / 0.65 = 2.83. بالنسبة لمجموعة بيانات تتكون من 57 عملية تشغيل لكل منها سجل واحد، بعد التوزيع الأولي، يقوم فرز الدمج متعدد المراحل بنقل 232 سجلاً خلال 6 تكرارات يستغرقها فرز مجموعة البيانات، وذلك للحصول على عامل تخفيض إجمالي قدره 2.70 (سيتم شرح هذا بمزيد من التفصيل لاحقًا).

بعد التكرار الأول متعدد المراحل، يحتوي ملف الإخراج على نتائج دمج N -1 عملية تشغيل أصلية، بينما لا تزال ملفات الإدخال المتبقية (N -2) تحتوي على عمليات التشغيل الأصلية المتبقية. لذا، ينتج عن تكرار الدمج الثاني عمليات تشغيل بحجم ( N -1) + ( N -2) = ( 2N -3) عملية تشغيل أصلية. وينتج عن التكرار الثالث عمليات تشغيل بحجم ( 4N -7) عملية تشغيل أصلية. مع 4 ملفات، ينتج عن التكرار الأول عمليات تشغيل بحجم 3 عمليات تشغيل أصلية، وعن التكرار الثاني 5 عمليات تشغيل أصلية، وعن التكرار الثالث 9 عمليات تشغيل أصلية، وهكذا، وفقًا لنمط فيبوناتشي: 1، 3، 5، 9، 17، 31، 57، ...، وبالتالي فإن الزيادة في حجم عملية التشغيل تتبع نفس نمط الانخفاض في عددها، ولكن بالعكس. في المثال المذكور، وهو عبارة عن 4 ملفات و57 عملية تشغيل، كل منها يحتوي على سجل واحد، تدمج التكرارات الأخيرة 3 عمليات تشغيل بأحجام 31 و17 و9 على التوالي، مما ينتج عنه عملية تشغيل واحدة مرتبة بحجم 31 + 17 + 9 = 57 سجلاً، وهي مجموعة البيانات المرتبة. يمكن الاطلاع على مثال لعدد عمليات التشغيل وأحجامها لـ 4 ملفات و31 سجلاً في الجدول 4.3 من المرجع ^{[ 3 ] .}

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

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

الملف 1 (الخارج): <تشغيل واحد> * (الملف المصنف) الملف 2 (في): ... | <تشغيل واحد> * --> ... <تشغيل واحد> | * (مستهلك) الملف 3 (في): | <تشغيل واحد> * <تشغيل واحد> | * (مستهلك) ... عمليات التشغيل المحتملة التي تمت قراءتها بالفعل | يشير إلى مؤشر القراءة للملف * تشير إلى نهاية الملف 

بالعودة إلى التكرار السابق، كنا نقرأ من الملفين 1 و2. يتم دمج عملية واحدة من الملفين 1 و2 قبل أن يصبح الملف 1 فارغًا. لاحظ أن الملف 2 لم يُستهلك بالكامل، إذ تبقى فيه عملية واحدة لمطابقة الدمج النهائي (أعلاه).

الملف 1 (في): ... | <تشغيل واحد> * ... <تشغيل واحد> | * الملف 2 (في): | <تشغيل 2> * --> <تشغيل 1> | <تشغيل 1> * الملف 3 (الخارج): <تشغيل واحد> * 

بالعودة إلى تكرار آخر، يتم دمج عمليتي تشغيل من 1 و 3 قبل أن يصبح الملف 3 فارغًا.

الملف 1 (في): | <تشغيل 3> ... <تشغيل 2> | <تشغيل 1> * الملف 2 (الخارج): --> <تشغيل 2> * الملف 3 (في): ... | <تشغيل 2> * <تشغيل 2> | * 

بالعودة إلى تكرار آخر، يتم دمج 3 عمليات تشغيل من 2 و 3 قبل أن يصبح الملف 2 فارغًا.

الملف 1 (الخارج): <تشغيل 3> * الملف 2 (في): ... | <3 تشغيل> * --> ... <3 تشغيل> | * الملف 3 (في): | <5 تشغيل> * <3 تشغيل> | <2 تشغيل> * 

بالعودة إلى تكرار آخر، يتم دمج 5 عمليات تشغيل من 1 و 2 قبل أن يصبح الملف 1 فارغًا.

الملف 1 (في): ... | <تشغيل 5> * ... <تشغيل 5> | * الملف 2 (في): | <8 تشغيل> * --> <5 تشغيل> | <3 تشغيل> * الملف 3 (الخارج): <5 تشغيل> * 

بالنظر إلى حالة الملفات الثلاثة المثالية، فإن عدد مرات التشغيل عند دمجها بالترتيب العكسي: 1، 1، 2، 3، 5، ... يكشف عن متتالية فيبوناتشي. أما بالنسبة لأكثر من ثلاثة ملفات، فالمتتالية أكثر تعقيدًا؛ فبالنسبة لأربعة ملفات، بدءًا من الحالة النهائية وبالترتيب العكسي، يكون نمط عدد مرات التشغيل كالتالي: {1، 0، 0، 0}، {0، 1، 1، 1}، {1، 0، 2، 2}، {3، 2، 0، 4}، {7، 6، 4، 0}، {0، 13، 11، 7}، {13، 0، 24، 20}، ...

لضمان الأداء الأمثل، يجب أن تتضمن مرحلة الدمج الأخيرة عملية تشغيل واحدة فقط على كل ملف إدخال. في حال احتوى أي ملف إدخال على أكثر من عملية تشغيل، فستكون هناك حاجة إلى مرحلة إضافية. لذا، يجب أن يكون فرز الدمج متعدد المراحل ذكيًا في التوزيع الأولي لعمليات تشغيل بيانات الإدخال على ملفات الإخراج الأولية. على سبيل المثال، سيكتب ملف إدخال يحتوي على 13 عملية تشغيل 5 عمليات تشغيل في الملف 1 و8 عمليات تشغيل في الملف 2.

عمليًا، لن يحتوي ملف الإدخال على العدد الدقيق من عمليات التشغيل اللازمة لتوزيع مثالي. إحدى طرق معالجة هذه المشكلة هي إضافة عمليات تشغيل وهمية إلى التوزيع الفعلي لمحاكاة توزيع مثالي. ^{[ 1 ]} تتصرف عملية التشغيل الوهمية كعملية تشغيل فارغة. دمج عملية تشغيل وهمية واحدة أو أكثر مع عملية تشغيل حقيقية واحدة أو أكثر يؤدي إلى دمج عمليات التشغيل الحقيقية، ودمج عملية تشغيل وهمية واحدة أو أكثر مع بيانات فارغة ينتج عنه عملية تشغيل وهمية واحدة. هناك طريقة أخرى تتمثل في محاكاة عمليات التشغيل الوهمية حسب الحاجة أثناء عمليات الدمج. ^{[ 4 ]}

تتطلب خوارزميات التوزيع "الأمثل" معرفة عدد عمليات التشغيل مسبقًا. أما في الحالة الأكثر شيوعًا حيث لا يُعرف عدد عمليات التشغيل مسبقًا، فتُستخدم خوارزميات التوزيع "شبه المثلى". تتضمن بعض خوارزميات التوزيع إعادة ترتيب عمليات التشغيل. ^{[ 5 ]} إذا كان عدد عمليات التشغيل معروفًا مسبقًا، فلا يلزم سوى توزيع جزئي قبل بدء مراحل الدمج. على سبيل المثال، لنفترض حالة 3 ملفات، بدءًا من n عملية تشغيل في الملف File_1. لنُعرّف F _{_i} = F _{_{i -1}} + F _{_{i -2}} على أنه عدد فيبوناتشي رقم i . إذا كان n = F _{_i} ، فننقل F _{_{i -2}} عملية تشغيل إلى الملف File_2، تاركين F _{_{i - 1}} عملية تشغيل متبقية في الملف File_1، وهو توزيع مثالي لعمليات التشغيل. إذا كان F _i < n < F _{_{i +1}} ، فننقل n - F _{_i} عملية تشغيل إلى الملف File_2 و F _{_{i +1}} - n عملية تشغيل إلى الملف File_3. في عملية الدمج الأولى، يتم دمج n − F _i من الملفين File_1 وFile_2، ثم تُضاف عمليات الدمج n − F _i إلى F _{i +1} − n من عمليات الدمج التي نُقلت مسبقًا إلى الملف File_3. يتبقى في الملف File_1 عدد F _{i − 2} من عمليات الدمج، بينما يُفرغ الملف File_2، ويتبقى في الملف File_3 عدد F _{i − 1} من عمليات الدمج، وهو توزيع مثالي لعمليات الدمج. أما بالنسبة لأربعة ملفات أو أكثر، فإن العمليات الحسابية تصبح أكثر تعقيدًا، لكن المفهوم يبقى نفسه.

بعد التوزيع الأولي، تقوم خوارزمية فرز الدمج المتوازن باستخدام 4 ملفات بفرز 16 سجلًا فرديًا في 4 دورات من مجموعة البيانات الكاملة، ناقلةً ما مجموعه 64 سجلًا لفرز مجموعة البيانات بعد التوزيع الأولي. أما خوارزمية فرز الدمج متعدد المراحل باستخدام 4 ملفات، فتقوم بفرز 17 سجلًا فرديًا في 4 دورات، ولكن نظرًا لأن كل دورة باستثناء الأخيرة تنقل جزءًا فقط من مجموعة البيانات، فإنها تنقل 48 سجلًا فقط لفرز مجموعة البيانات بعد التوزيع الأولي. في هذه الحالة، يكون معامل فرز الدمج المتوازن 2.0، بينما يكون المعامل الإجمالي لخوارزمية فرز الدمج متعدد المراحل ≈2.73.

لتوضيح كيفية ارتباط عامل التخفيض بأداء الفرز، فإن معادلات عامل التخفيض هي:

عامل_التخفيض = exp(عدد_الركضات*log(عدد_الركضات)/عدد_حركات_الركض) عدد مرات تنفيذ الحركة = عدد مرات التنفيذ * لوغاريتم (عدد مرات التنفيذ) / لوغاريتم (عامل التخفيض) عدد مرات تنفيذ الحركة = عدد مرات التنفيذ * عامل التخفيض اللوغاريتمي (عدد مرات التنفيذ)

باستخدام معادلة عدد حركات الجري للأمثلة المذكورة أعلاه:

• فرز الدمج المتوازن →${\displaystyle 16\times \log _{2}(16)=64}$،​
• فرز الدمج متعدد المراحل →${\displaystyle 17\times \log _{2.73}(17)=48}$⁠ .

فيما يلي جدولٌ بمعاملات التخفيض الفعّالة لخوارزميتي فرز الدمج متعدد المراحل والمتوازن، مُصنّفة حسب عدد الملفات، استنادًا إلى عمليات فرز فعلية لملايين السجلات. يتوافق هذا الجدول تقريبًا مع جداول معاملات التخفيض لكل مجموعة بيانات مُنقولة، الموضحة في الشكلين 3 و4 من ملف polyphase merge sort.pdf.

ملفات | متوسط ​​نسبة البيانات لكل تكرار | | عامل تقليل متعدد الأطوار على بيانات ذات حجم مثالي | | | عامل تخفيض متوازن على بيانات ذات حجم مثالي | | | | 3.73 1.94 1.41 (جذر 2) 4.63 2.68 2.00 5.58 3.20 2.45 (جذر 6) 6.56 3.56 3.00 7.55 3.80 3.46 (جذر 12) 8.54 3.95 4.00 9.53 4.07 4.47 (جذر 20) 10.53 4.15 5.00 11.53 4.22 5.48 (جذر 30) 12.53 4.28 6.00 32.53 4.87 16.00 

بشكل عام، يُعدّ فرز الدمج متعدد المراحل أفضل من فرز الدمج المتوازن عندما يكون عدد الملفات أقل من 8، بينما يبدأ فرز الدمج المتوازن في التحسن عند وجود 8 ملفات أو أكثر. ^{[ 6 ] [ 7 ]}

• برادلي، جيمس (1982)، تقنيات الملفات وقواعد البيانات ، هولت، راينهارت ووينستون، رقم ISBN 0-03-058673-9
• رينولدز، صموئيل و. (أغسطس 1961)، "خوارزمية دمج متعددة الأطوار معممة"، اتصالات ACM ، 4 (8)، نيويورك، نيويورك: ACM: 347-349 ، doi : 10.1145/366678.366689 ، S2CID 28416100 
• سيدجويك، روبرت (1983)، الخوارزميات ، أديسون-ويسلي، الصفحات 163-165 ، رقم ISBN  0-201-06672-6