شبكة الفرز

الموسوعة الحرة
شبكة فرز بسيطة تتكون من أربعة أسلاك وخمسة موصلات

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

تختلف شبكات الفرز عن خوارزميات الفرز المقارنة العامة في أنها لا تستطيع التعامل مع مدخلات كبيرة الحجم، وفي أن تسلسل المقارنات فيها مُحدد مسبقًا، بغض النظر عن نتائج المقارنات السابقة. ولفرز عدد أكبر من المدخلات، يجب إنشاء شبكات فرز جديدة. يُعد استقلال تسلسل المقارنات هذا مفيدًا للتنفيذ المتوازي وللتطبيق في الأجهزة . على الرغم من بساطة شبكات الفرز، إلا أن نظريتها عميقة ومعقدة بشكلٍ مُدهش. دُرست شبكات الفرز لأول مرة حوالي عام 1954 على يد أرمسترونغ ونيلسون وأوكونور، [ 1 ] الذين حصلوا لاحقًا على براءة اختراع للفكرة. [ 2 ]

يمكن تنفيذ شبكات الفرز إما باستخدام الأجهزة أو البرمجيات . يصف دونالد كنوث كيفية تنفيذ المقارنات للأعداد الصحيحة الثنائية كأجهزة إلكترونية بسيطة ثلاثية الحالات. [ 1 ] اقترح باتشر ، في عام 1968، استخدامها لإنشاء شبكات تبديل لأجهزة الحاسوب، لتحل محل كل من الحافلات ومفاتيح التبديل المتقاطع الأسرع، ولكن الأكثر تكلفة . [ 3 ] منذ بداية الألفية الثانية، يستخدم مجتمع GPGPU شبكات الفرز (وخاصة فرز الدمج الثنائي ) لإنشاء خوارزميات فرز تعمل على وحدات معالجة الرسومات . [ 4 ]

مقدمة

عرض توضيحي للمقارن في شبكة الفرز.

تتكون شبكة الفرز من نوعين من العناصر: المقارنات والأسلاك. تُصوَّر الأسلاك على أنها تمتد من اليسار إلى اليمين، حاملةً قيمًا (قيمة واحدة لكل سلك) تعبر الشبكة في آنٍ واحد. يربط كل مُقارِن سلكين. عندما تصادف قيمتان، تنتقلان عبر سلكين، مُقارِنًا، يقوم المُقارِن بتبديل القيمتين إذا وفقط إذا كانت قيمة السلك العلوي أكبر من أو تساوي قيمة السلك السفلي.

في الصيغة، إذا كان السلك العلوي يحمل x والسلك السفلي يحمل y ، فإن الأسلاك بعد مرورها بجهاز المقارنة تحملx′=مين(x،y){\displaystyle x'=\min(x,y)}وy′=الأعلى(x،y){\displaystyle y'=\max(x,y)}وبالتالي، يتم ترتيب زوج القيم. [ 5 ] : 635 تُسمى شبكة الأسلاك والمقارنات التي تُرتّب جميع المدخلات الممكنة ترتيبًا تصاعديًا شبكة فرز أو محور كروسكال. ومن خلال عكس الشبكة، يُمكن أيضًا ترتيب جميع المدخلات ترتيبًا تنازليًا.

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

العمق والكفاءة

يمكن قياس كفاءة شبكة الفرز بحجمها الإجمالي، أي عدد المقارنات فيها، أو بعمقها ، الذي يُعرَّف (بشكل غير رسمي) بأنه أكبر عدد من المقارنات التي يمكن أن تواجهها أي قيمة مُدخلة أثناء مرورها عبر الشبكة. وبملاحظة أن شبكات الفرز قادرة على إجراء بعض المقارنات بالتوازي (مُمثلة بيانيًا بمقارنات تقع على نفس الخط الرأسي)، وبافتراض أن جميع المقارنات تستغرق وحدة زمنية واحدة، يتضح أن عمق الشبكة يساوي عدد الخطوات الزمنية اللازمة لتنفيذها. [ 5 ] : 636-637

شبكات الإدخال والفقاعات

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

شبكة فرز مبنية بشكل متكرر، تقوم أولاً بإنزال القيمة الأكبر إلى الأسفل ثم فرز الأسلاك المتبقية. تعتمد على خوارزمية فرز الفقاعات.
شبكة فرز مبنية بشكل متكرر، تقوم أولاً بفرز أول n سلك، ثم تُدرج القيمة المتبقية. تعتمد على فرز الإدراج.

تتشابه بنية شبكتي الفرز هاتين تشابهاً كبيراً. ويُظهر بناء المتغيرين المختلفين، اللذين يجمعان المقارنات التي يمكن تنفيذها في وقت واحد، أنهما في الواقع متطابقان. [ 1 ]

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

تتمتع شبكة الإدخال (أو ما يعادلها، شبكة الفقاعات) بعمق 2 ^n - 3 ، [ 1 ] حيث n هو عدد القيم. وهذا أفضل من زمن O ( n log n ) الذي تحتاجه آلات الوصول العشوائي ، ولكن اتضح أن هناك شبكات فرز أكثر كفاءة بعمق O (log 2 n ) فقط ، كما هو موضح أدناه .

مبدأ الصفر والواحد

على الرغم من سهولة إثبات صحة بعض شبكات الفرز (مثل فرز الإدراج/الفقاعات)، إلا أن الأمر ليس بهذه السهولة دائمًا. يوجد n ! تبديلًا للأرقام في شبكة ذات n سلك، واختبارها جميعًا سيستغرق وقتًا طويلًا، خاصةً عندما يكون n كبيرًا. يمكن تقليل عدد حالات الاختبار بشكل كبير، إلى 2^ n ، باستخدام ما يُعرف بمبدأ الصفر والواحد. مع أن هذا العدد لا يزال أُسّيًا، إلا أنه أصغر من n ! لجميع قيم n ≥ 4 ، ويتزايد الفرق بسرعة مع ازدياد n .

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

يمكن إثبات هذا المبدأ بملاحظة الحقيقة التالية المتعلقة بالمقارنات: عند تطبيق دالة متزايدة رتيبة f على المدخلات، أي عند استبدال x و y بـ f ( x ) و f ( y ) ، فإن المقارن ينتج min( f ( x ), f ( y )) = f (min( x , y )) و max( f ( x ), f ( y )) = f (max( x , y )) . وبالاستقراء على عمق الشبكة، يمكن تعميم هذه النتيجة لتصبح لمة تنص على أنه إذا حوّلت الشبكة المتتالية a₁ , ..., an إلى b₁ , ... , bn ، فإنها ستحوّل f ( a₁ ), ..., f ( an ) إلى f ( b₁ ) , ... , f ( bn ) . لنفترض أن أحد المدخلات a₁ , ..., an يحتوي على عنصرين aᵢ < aⱼ ، وأن الشبكة تبدلهما بشكل خاطئ في المخرجات . ثم سيقوم أيضًا بترتيب f ( a1 ) ، ...، f ( an ) بشكل خاطئ للدالة

و(x)={1 لو x>أأنا0 خلاف ذلك.{\displaystyle f(x)={\begin{cases}1\ &{\mbox{if }}x>a_{i}\\0\ &{\mbox{otherwise.}}\end{cases}}}

هذه الدالة رتيبة، لذا لدينا مبدأ الصفر والواحد كعكس إيجابي لها . [ 5 ] : 640-641

بناء شبكات الفرز

توجد خوارزميات متنوعة لإنشاء شبكات فرز بعمق O (log 2 n ) (وبالتالي بحجم O ( n log 2 n ) ) مثل فرز الدمج الزوجي-الفردي الدفعي ، والفرز الثنائي ، وفرز شل ، وشبكة الفرز الزوجي . وتُستخدم هذه الشبكات بكثرة في التطبيقات العملية.

من الممكن أيضًا إنشاء شبكات بعمق O (log n ) (وبالتالي بحجم O ( n log n ) ) باستخدام بنية تُسمى شبكة AKS ، نسبةً إلى مكتشفيها: أيتائي ، وكوملوس ، وسزيميريدي . [ 6 ] على الرغم من أهمية هذا الاكتشاف النظري، إلا أن شبكة AKS لها تطبيقات عملية محدودة للغاية بسبب الثابت الخطي الكبير الذي تُخفيه صيغة Big-O . [ 5 ] : 653 ويعود ذلك جزئيًا إلى بنية الرسم البياني الموسّع .

وصف باترسون نسخة مبسطة من شبكة AKS في عام 1990، وأشار إلى أن "الثوابت التي تم الحصول عليها لحدود العمق لا تزال تمنع أن يكون للبناء قيمة عملية". [ 7 ]

تم اكتشاف بنية أحدث تسمى شبكة الفرز المتعرجة بحجم O ( n log n ) بواسطة جودريتش في عام 2014. [ 8 ] على الرغم من أن حجمها أصغر بكثير من حجم شبكات AKS، إلا أن عمقها O ( n log n ) يجعلها غير مناسبة للتنفيذ المتوازي.

شبكات الفرز المثلى

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

ن1234567891011121314151617
العمق [ 10 ]013355667788999910
الحجم، الحد الأعلى [ 11 ]01359121619252935394551566071
الحجم، الحد الأدنى (إن كان مختلفًا) [ 12 ]4347515560

بالنسبة للشبكات الأكبر حجماً، لا يُعرف حالياً العمق الأمثل ولا الحجم الأمثل. ترد الحدود المعروفة حتى الآن في الجدول أدناه:

ن181920212223242526272829303132
العمق، الحد الأعلى [ 10 ] [ 13 ] [ 14 ] [ 15 ]111111121212121313131314141414
العمق، الحد الأدنى [ 10 ]101010101010101010101010101010
الحجم، الحد الأعلى [ 14 ]77859199106114120130138147155164172180185
الحجم، الحد الأدنى [ 12 ]65707580859095100105110115120125130135

تم إدراج الشبكات الستة عشر الأولى ذات العمق الأمثل في كتاب كنوت فن برمجة الكمبيوتر ، [ 1 ] وكان الأمر كذلك منذ طبعة عام 1973؛ ومع ذلك، في حين تم إثبات مثالية الشبكات الثمانية الأولى بواسطة فلويد وكنوت في الستينيات، لم يتم إثبات هذه الخاصية للشبكات الست الأخيرة حتى عام 2014 [ 16 ] (حيث تم البت في الحالتين التاسعة والعاشرة في عام 1991 [ 9 ] ).

بالنسبة لعدد مدخلات يتراوح بين واحد واثني عشر مدخلاً، تُعرف شبكات الفرز الدنيا (أي ذات الحجم الأمثل)، وبالنسبة للقيم الأعلى، يمكن اشتقاق حدود دنيا لأحجامها S ( n ) استقرائيًا باستخدام مبرهنة فان فورهيس [ 1 ] (ص  240): S ( n ) ≥ S ( n -1) + ⌈log₂n⌉ . عُرفت الشبكات العشر الأولى المثلى منذ عام 1969، وعُرفت الشبكات الثماني الأولى منها بأنها مثلى منذ عمل فلويد وكنوث، ولكن لم يُحسم أمر مثالية الحالتين n = 9 و n = 10 إلا في عام 2014. [ 11 ] حُسم أمر مثالية أصغر شبكات الفرز المعروفة للحالتين n = 11 و n = 12 في عام 2020. [ 17 ] [ 1 ]

تم إنجاز بعض الأعمال في تصميم شبكة الفرز المثلى باستخدام الخوارزميات الجينية : يذكر د. كنوت أن أصغر شبكة فرز معروفة لـ n = 13 تم العثور عليها بواسطة هيوز جويل في عام 1995 "عن طريق محاكاة عملية تطورية للتربية الجينية" [ 1 ] (ص  226)، وأن شبكات الفرز ذات الحد الأدنى من العمق لـ n = 9 و n = 11 تم العثور عليها بواسطة لورين شويبرت في عام 2001 "باستخدام الأساليب الجينية" [ 1 ] (ص  229).

تعقيد اختبار شبكات الفرز

ما لم يكن P=NP ، فمن المرجح أن تظل مشكلة اختبار ما إذا كانت الشبكة المرشحة شبكة فرز صعبة بالنسبة للشبكات ذات الأحجام الكبيرة، نظرًا لأن المشكلة كاملة من نوع co-NP . [ 18 ]

مراجع

  1. 1 2 3 4 5 6 7 8 9 كنوت، دي إي (1997). فن برمجة الحاسوب، المجلد 3: الفرز والبحث (الطبعة الثانية  ). أديسون-ويسلي. الصفحات 219-247 . ISBN  978-0-201-89685-5.القسم 5.3.4: الشبكات للفرز.
  2. ↑ US 3029413 ، أوكونور، دانيال ج. ونيلسون ، ريموند ج.، "نظام فرز مع مفتاح فرز ذي n خط"، نُشر في 10 أبريل 1962 
  3. ↑ باتشر، ك. إي. (1968). شبكات الفرز وتطبيقاتها . وقائع المؤتمر المشترك الربيعي للحاسوب التابع لـ AFIPS. الصفحات 307-314 . 
  4. ↑ أوينز، جيه دي؛ هيوستن، إم؛ لوبك، دي؛ غرين، إس؛ ستون، جيه إي؛ فيليبس، جيه سي (2008). "الحوسبة باستخدام وحدات معالجة الرسومات". وقائع معهد مهندسي الكهرباء والإلكترونيات . 96 (5): 879-899 . doi : 10.1109/JPROC.2008.917757 . S2CID 17091128 . 
  5. 1 2 3 4 كورمين، توماس هـ . ليسرسون، تشارلز إي . ريفست، رونالد ل. (1990). مقدمة في الخوارزميات ( الطبعة الأولى). مطبعة معهد ماساتشوستس للتكنولوجيا وماكجرو هيل. رقم ISBN  0-262-03141-8.
  6. ↑ أجتاي، م .؛ كوملوس، ج .؛ سزيميريدي، إ. (1983). شبكة فرز من رتبة O(n log n) . STOC '83. وقائع الندوة السنوية الخامسة عشرة لجمعية ACM حول نظرية الحوسبة . الصفحات 1-9 . doi : 10.1145/800061.808726 . ISBN  0-89791-099-0.
  7. ↑ باترسون، م.س. (1990). "شبكات فرز محسّنة بعمق O (log N ) ". Algorithmica . 5 ( 1-4 ): 75-92 . doi : 10.1007/BF01840378 . S2CID 2064561 . 
  8. ↑ غودريتش، مايكل (مارس 2014). "فرز متعرج". وقائع الندوة السنوية السادسة والأربعين لجمعية آلات الحوسبة حول نظرية الحوسبة . الصفحات 684-693 . arXiv : 1403.2777 . doi : 10.1145/2591796.2591830 . ISBN  9781450327107. S2CID 947950 . 
  9. 1 2 باربيري، إيان (1991). "حد أدنى مثالي للعمق بمساعدة الحاسوب لشبكات الفرز ذات التسعة مدخلات" (ملف PDF) . نظرية الأنظمة الرياضية . 24 : 101-116 . CiteSeerX 10.1.1.712.219 . doi : 10.1007/bf02090393 . S2CID 7077160 .  
  10. 1 2 3 كوديش، مايكل؛ كروز-فيليبي، لويس؛ إيلرز، ثورستن؛ مولر، مايك؛ شنايدر-كامب، بيتر (2015). فرز الشبكات: إلى النهاية والعودة مرة أخرى . arXiv : 1507.01428 . Bibcode : 2015arXiv150701428C .
  11. 1 2 كوديش، مايكل؛ كروز-فيليبي، لويس؛ فرانك، مايكل؛ شنايدر-كامب، بيتر (2014). استخدام 25 مقارنًا هو الأمثل عند فرز تسعة مدخلات (و29 لعشرة) . وقائع المؤتمر الدولي للأدوات مع الذكاء الاصطناعي (ICTAI). الصفحات 186-193 . arXiv : 1405.5754 . Bibcode : 2014arXiv1405.5754C . 
  12. 1 2 حصل عليها فان فورهيس ليما والقيمة S (11) = 35
  13. ↑ إيلرز، ثورستن (فبراير 2017). "دمج التسلسلات شبه المصنفة ينتج عنه مصنف 24". رسائل معالجة المعلومات . 118 : 17-20 . doi : 10.1016/j.ipl.2016.08.005 .
  14. 1 2 دوبلير، بيرت. "فارزهنتر" . جيثب . تم الاسترجاع في 2 يناير 2022 .
  15. ↑ وانغ، تشنغو (2025). "شبكات فرز العمق 13 لـ 28 قناة". arXiv : 2511.04107 [ cs.DS ].
  16. ↑ بوندالا، د.؛ زافودني، ج. (2014). "شبكات الفرز الأمثل". نظرية اللغة والأتمتة وتطبيقاتها . سلسلة محاضرات في علوم الحاسوب. المجلد 8370. الصفحات 236-247 . arXiv : 1310.6271 . doi : 10.1007/978-3-319-04921-2_19 . ISBN   978-3-319-04920-5. S2CID 16860013 . 
  17. ↑ هاردر، يانيس (2020). "إجابة لمسألة فرز بوز-نيلسون لـ 11 و 12 قناة". arXiv : 2012.04400 [ cs.DS ].
  18. ↑ باربيري، إيان (1991). حول التعقيد الحسابي للتحقق الأمثل من شبكة الفرز . وقائع مؤتمر PARLE '91: البنى واللغات المتوازية في أوروبا، المجلد الأول: البنى والخوارزميات المتوازية، أيندهوفن، هولندا . الصفحات 252-269 .