خوارزمية الدمج

الموسوعة الحرة

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

طلب

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

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

  1. قسّم القائمة بشكل متكرر إلى قوائم فرعية متساوية الطول (تقريبًا)، حتى تحتوي كل قائمة فرعية على عنصر واحد فقط، أو في حالة فرز الدمج التكراري (من الأسفل إلى الأعلى)، اعتبر قائمة من n عنصرًا بمثابة n قائمة فرعية بحجم 1. القائمة التي تحتوي على عنصر واحد، بحكم تعريفها، مرتبة.
  2. قم بدمج القوائم الفرعية بشكل متكرر لإنشاء قائمة فرعية مرتبة جديدة حتى تحتوي القائمة الواحدة على جميع العناصر. القائمة الواحدة هي القائمة المرتبة.

تُستخدم خوارزمية الدمج بشكل متكرر في خوارزمية فرز الدمج.

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

دمج قائمتين

يمكن دمج قائمتين مُرتبتين في قائمة واحدة في وقت خطي ومساحة خطية أو ثابتة (بحسب نموذج الوصول إلى البيانات). يوضح الكود الزائف التالي خوارزمية تدمج قائمتي الإدخال (سواء كانت قوائم مرتبطة أو مصفوفات ) A و B في قائمة جديدة C. [ 1 ] [ 2 ] : 104 تُعيد الدالة head العنصر الأول من القائمة؛ و "حذف" عنصر يعني إزالته من قائمته، عادةً عن طريق زيادة مؤشر أو فهرس.

خوارزمية دمج (A، B) هي مدخلات A، B : قائمة تُرجع قائمة C := قائمة فارغة جديدة طالما أن A و B ليستا فارغتين ، إذا كان رأس A ≤ رأس B، أضف رأس (أ) إلى ج أسقط رأس أ آخر أضف رأس (ب) إلى ج أسقط رأس ب // الآن، إما A أو B فارغة. يبقى إفراغ قائمة الإدخال الأخرى. طالما أن A ليست فارغة، نفّذ أضف رأس (أ) إلى ج أسقط رأس أ طالما أن B ليست فارغة، نفّذ أضف رأس (ب) إلى ج أسقط رأس ب إرجاع C

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

في خوارزمية فرز الدمج، تُستخدم هذه الدالة الفرعية عادةً لدمج مصفوفتين فرعيتين A[lo..mid] و A[mid+1..hi] من مصفوفة واحدة A. يمكن تحقيق ذلك بنسخ المصفوفتين الفرعيتين إلى مصفوفة مؤقتة، ثم تطبيق خوارزمية الدمج المذكورة أعلاه. [ 1 ] يمكن تجنب تخصيص مصفوفة مؤقتة، ولكن على حساب السرعة وسهولة البرمجة. تم ابتكار العديد من خوارزميات الدمج الموضعي، [ 3 ] والتي تُضحي أحيانًا بالحد الزمني الخطي لإنتاج خوارزمية من رتبة O ( n log n ) ؛ [ 4 ] انظر فرز الدمج § المتغيرات لمزيد من التفاصيل. 

دمج مسارات K

يُعمم دمج k -way دمج البيانات الثنائية ليشمل أي عدد k من قوائم الإدخال المُرتبة. وتظهر تطبيقات دمج k -way في خوارزميات فرز متنوعة، بما في ذلك فرز الصبر [ 5 ] وخوارزمية فرز خارجية تُقسّم مُدخلاتها إلى k = 1 / M − 1 كتلة تتسع في الذاكرة، ثم تُرتّب هذه الكتل واحدة تلو الأخرى، ثم تدمجها . [ 2 ] : 119–120

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

  • المدخلات: قائمة من k قائمة.
  • طالما أن أيًا من القوائم غير فارغة:
    • قم بالمرور على القوائم للعثور على القائمة التي تحتوي على أقل عنصر أول.
    • أخرج العنصر الأدنى واحذفه من قائمته.

في أسوأ الأحوال ، تُجري هذه الخوارزمية ( k − 1)( n − k / 2 ) مقارنة بين العناصر لإنجاز مهمتها إذا كان إجمالي عدد العناصر في القوائم n . [ 6 ] ويمكن تحسينها بتخزين القوائم في طابور أولوية ( كومة دنيا ) مُفهرسة بالعنصر الأول فيها.

  • قم ببناء كومة دنيا h من القوائم k ، باستخدام العنصر الأول كمفتاح.
  • طالما أن أيًا من القوائم غير فارغة:
    • ليكن i = find-min( h ) .
    • أخرج العنصر الأول من القائمة i واحذفه من قائمتها.
    • إعادة ترتيب h .

يمكن الآن البحث عن أصغر عنصر تالٍ لإخراجه (find-min) واستعادة ترتيب الكومة في زمن قدره O(log k) (وبشكل أكثر تحديدًا، 2⌊log k⌋ مقارنة [ 6 ] ) ، ويمكن حل المشكلة كاملةً في زمن قدره O ( n log k ) (حوالي 2n⌊log k⌋ مقارنة ). [ 6 ] [ 2 ] : 119–120

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

  • إذا كانت قيمة k تساوي 1 ، فقم بإخراج قائمة الإدخال الوحيدة.
  • إذا كانت قيمة k تساوي 2 ، فقم بإجراء عملية دمج ثنائية.
  • وإلا، قم بدمج القوائم الأولى ⌊ k /2⌋ والقوائم النهائية ⌈ k /2⌉ بشكل متكرر ، ثم قم بدمجها ثنائيًا.

عندما يتم ترتيب قوائم الإدخال لهذه الخوارزمية حسب الطول، بدءًا من الأقصر، فإنها تتطلب أقل من n ⌈log k ⌉ مقارنة، أي أقل من نصف العدد الذي تستخدمه الخوارزمية القائمة على الكومة؛ عمليًا، قد تكون بنفس سرعة أو بطء الخوارزمية القائمة على الكومة. [ 6 ]

دمج متوازٍ

يمكن أن تُستخدم نسخة متوازية من خوارزمية الدمج الثنائي كعنصر أساسي في خوارزمية فرز الدمج المتوازية . يوضح الكود الزائف التالي هذه الخوارزمية بأسلوب فرق تسد المتوازي (مقتبس من كورمن وآخرون [ 7 ] : 800 ). تعمل الخوارزمية على مصفوفتين مرتبتين A و B ، وتكتب الناتج المرتب في المصفوفة C. يشير الرمز A[i...j] إلى الجزء من A من الفهرس i إلى j ، باستثناء الفهرس j.

خوارزمية الدمج (A[i...j], B[k...ℓ], C[p...q]) هي المدخلات A وB وC: مصفوفة i، j، k، ℓ، p، q: مؤشرات ليكن m = j - i، ن = ℓ - ك إذا كان m < n، فقم بتبديل A و B // تأكد من أن A هي المصفوفة الأكبر: i و j لا يزالان ينتميان إلى A؛ k و ℓ إلى B قم بتبديل m و n إذا كانت قيمة m ≤ 0، فقم بالإرجاع // الحالة الأساسية، لا يوجد شيء للدمجليكن r = ⌊(i + j)/2⌋، وليكن s = binary-search(A[r], B[k...ℓ])، وليكن t = p + (r - i) + (s - k). C[t] = A[r] بالتوازي مع ذلك، قم بما يلي merge(A[i...r], B[k...s], C[p...t]) merge(A[r+1...j], B[s...ℓ], C[t+1...q])

تعمل الخوارزمية بتقسيم المصفوفة A أو B ، أيهما أكبر، إلى نصفين متساويين تقريبًا. ثم تقسم المصفوفة الأخرى إلى جزء بقيم أصغر من منتصف الأول، وجزء بقيم أكبر أو مساوية. ( تعيد روتينية البحث الثنائي الفهرس في B حيث سيكون A [ r ] لو كان موجودًا في B ؛ وهذا دائمًا عدد بين k وℓ ) . أخيرًا، يتم دمج كل زوج من النصفين بشكل متكرر ، وبما أن الاستدعاءات المتكررة مستقلة عن بعضها البعض، فيمكن تنفيذها بالتوازي. وقد أثبت النهج الهجين، حيث تُستخدم الخوارزمية التسلسلية كحالة أساسية للتكرار، أداءً جيدًا عمليًا [ 8 ].

العمل الذي تؤديه الخوارزمية لمصفوفتين تحتويان على n عنصرًا، أي زمن تشغيل نسخة تسلسلية منها، هو O ( n ) . وهذا مثالي لأن n عنصرًا يجب نسخها إلى C. لحساب مدى الخوارزمية، من الضروري اشتقاق علاقة تكرارية . بما أن استدعاءي الدمج التكراريين متوازيان ، فلا يلزم سوى النظر في الاستدعاء الأكثر تكلفة. في أسوأ الحالات، يكون الحد الأقصى لعدد العناصر في أحد الاستدعاءين التكراريين على الأكثر34ن{\textstyle {\frac {3}{4}}n}بما أن المصفوفة التي تحتوي على عناصر أكثر تنقسم إلى نصفين بشكل مثالي. إضافةΘ(سجل⁡(ن)){\displaystyle \Theta \left(\log(n)\right)}من خلال حساب تكلفة البحث الثنائي، نحصل على هذا التكرار كحد أعلى:

تي∞دمج(ن)=تي∞دمج(34ن)+Θ(سجل⁡(ن)){\displaystyle T_{\infty }^{\text{merge}}(n)=T_{\infty }^{\text{merge}}\left({\frac {3}{4}}n\right)+\Theta \left(\log(n)\right)}

الحل هوتي∞دمج(ن)=Θ(سجل⁡(ن)2){\displaystyle T_{\infty }^{\text{merge}}(n)=\Theta \left(\log(n)^{2}\right)}وهذا يعني أن الأمر يستغرق هذا القدر من الوقت على جهاز مثالي ذي عدد غير محدود من المعالجات. [ 7 ] : 801-802

ملاحظة: هذه الخوارزمية غير مستقرة : إذا تم فصل العناصر المتساوية بتقسيم المصفوفة A والمصفوفة B ، فستتداخل هذه العناصر في المصفوفة C ؛ كما أن تبديل المصفوفتين A و B سيؤدي إلى فقدان الترتيب إذا تم توزيع العناصر المتساوية بين المصفوفتين المدخلتين. ونتيجة لذلك، عند استخدام هذه الخوارزمية للفرز، فإنها تُنتج فرزًا غير مستقر.

دمج متوازٍ لقائمتين

توجد أيضاً خوارزميات تُدخل التوازي ضمن عملية دمج واحدة لقائمتين مُرتبتين. ويمكن استخدام هذه الخوارزميات في مصفوفات البوابات المنطقية القابلة للبرمجة الميدانية ( FPGAs )، ودوائر الفرز المتخصصة، وكذلك في المعالجات الحديثة المزودة بتعليمات SIMD ( تعليمات أحادية متعددة البيانات).

تعتمد الخوارزميات المتوازية الحالية على تعديلات في جزء الدمج إما في خوارزمية الفرز الثنائي أو خوارزمية فرز الدمج الزوجي-الفردي . [ 9 ] في عام 2018، قدم سايتو وآخرون خوارزمية MMS [ 10 ] لأجهزة FPGA، والتي ركزت على إزالة مسار بيانات التغذية الراجعة متعدد الدورات الذي كان يعيق كفاءة المعالجة المتوازية في الأجهزة. وفي عام 2018 أيضًا، قدم بابافيليبو وآخرون خوارزمية FLiMS [ 9 ] التي حسّنت من استخدام الأجهزة والأداء من خلال اشتراطها فقطسجل2⁡(P)+1{\displaystyle \log _{2}(P)+1}مراحل خط الأنابيب لوحدات المقارنة والتبديل P/2 للدمج مع توازي P عنصر لكل دورة FPGA.

الدعم اللغوي

توفر بعض لغات البرمجة دعمًا مدمجًا أو دعمًا من المكتبات لدمج المجموعات المصنفة .

لغة سي++

تحتوي مكتبة القوالب القياسية للغة C ++ على الدالة std::merge ، التي تدمج نطاقين مرتبين من عناصر التكرار ، والدالة std::inplace_merge ، التي تدمج نطاقين مرتبين متتاليين في مكانهما . بالإضافة إلى ذلك، تحتوي فئة std::list (القائمة المرتبطة) على دالة دمج خاصة بها ، تدمج قائمة أخرى في نفسها. يجب أن يدعم نوع العناصر المدمجة عامل المقارنة "أصغر من" ( < )، أو يجب توفير دالة مقارنة مخصصة له.

تسمح لغة C++17 بسياسات تنفيذ مختلفة، وهي: التسلسلية، والمتوازية، والمتوازية غير المتسلسلة. [ 11 ]

بايثون

تحتوي المكتبة القياسية للغة بايثون (منذ الإصدار 2.6) أيضًا على دالة دمج في وحدة heapq ، والتي تأخذ عدة عناصر قابلة للتكرار مرتبة، وتدمجها في عنصر واحد قابل للتكرار. [ 12 ]

انظر أيضاً

مراجع

  1. 1 2 سكينا، ستيفن (2010). دليل تصميم الخوارزميات (  الطبعة الثانية). سبرينغر ساينس + بيزنس ميديا . ص  123. ISBN 978-1-849-96720-4.
  2. 1 2 3 كورت ميلهورن ؛ بيتر ساندرز (2008). الخوارزميات وهياكل البيانات: مجموعة الأدوات الأساسية . سبرينغر. ISBN 978-3-540-77978-0.
  3. ^ كاتاجينن، جيركي؛ باسانين، تومي؛ تيوهولا، جوكا (1996). “عملية دمج في المكان”. الشمال J. الحوسبة . 3 (1): 27– 40. سيتيسيركس 10.1.1.22.8523 . 
  4. ↑ كيم، بوك-سون؛ كوتزنر، آرني (2004). دمج الحد الأدنى المستقر للتخزين عن طريق المقارنات المتناظرة . ندوة أوروبية حول الخوارزميات. سلسلة محاضرات في علوم الحاسوب. المجلد 3221. الصفحات 714-723 . CiteSeerX 10.1.1.102.4612 . doi : 10.1007/978-3-540-30140-0_63 . ISBN    978-3-540-23025-0.
  5. ↑ تشاندرا مولي، بادريش؛ غولدشتاين، جوناثان (2014). الصبر فضيلة: إعادة النظر في دمج وفرز البيانات على المعالجات الحديثة . SIGMOD/PODS.
  6. 1 2 3 4 غرين، ويليام أ. (1993). دمج k-way وفرز k-ary (ملف PDF) . وقائع المؤتمر السنوي الحادي والثلاثين لجمعية ACM في جنوب شرق الولايات المتحدة. الصفحات 127-135 . 
  7. 1 2 كورمين، توماس هـ . ليسرسون، تشارلز إي . ريفست، رونالد ل . شتاين، كليفورد (2009) [1990]. مقدمة للخوارزميات ( الطبعة الثالثة). مطبعة معهد ماساتشوستس للتكنولوجيا وماكجرو هيل. رقم ISBN  0-262-03384-4.
  8. ^ فيكتور ج. دوفانينكو (2011)، “الدمج الموازي” ، مجلة دكتور دوب
  9. 1 2 بابافيليبو، فيليبوس؛ لوك، واين؛ بروكس، كريس (2022). "FLiMS: دمج ثنائي الاتجاه سريع وخفيف الوزن للفرز". معاملات IEEE للحواسيب : 1-12 . arXiv : 2112.05607 . doi : 10.1109/TC.2022.3146509 . hdl : 10044/1/95271 . S2CID 245669103 . 
  10. ↑ سايتو، ماكوتو؛ السيد، السيد أ.؛ تشو، ثيم فان؛ ماشيمو، سوسومو؛ كيس، كينجي (أبريل 2018). "جهاز فرز دمج عالي الأداء وفعال من حيث التكلفة بدون مسار بيانات تغذية راجعة". المؤتمر الدولي السنوي السادس والعشرون لمعهد مهندسي الكهرباء والإلكترونيات (IEEE) حول آلات الحوسبة المخصصة القابلة للبرمجة الميدانية (FCCM) . الصفحات 197-204 . doi : 10.1109/FCCM.2018.00038 . ISBN  978-1-5386-5522-1. S2CID 52195866 . 
  11. ↑ "std:merge" . cppreference.com. 2018-01-08 . تم الاطلاع عليه بتاريخ 2018-04-28 .
  12. ↑ "heapq — خوارزمية قائمة الانتظار المكدسة — وثائق بايثون 3.10.1" .

للمزيد من القراءة

  • دونالد كنوث . فن برمجة الحاسوب ، المجلد 3: الفرز والبحث ، الطبعة الثالثة. أديسون-ويسلي، 1997. ISBN 0-201-89685-0الصفحات 158-160 من القسم 5.2.4: الفرز بالدمج. القسم 5.3.2: دمج المقارنة الدنيا، الصفحات  197-207.