الفرز الخارجي

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

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

نموذج

يمكن تحليل خوارزميات الفرز الخارجي في نموذج الذاكرة الخارجية . في هذا النموذج، تُقسّم ذاكرة التخزين المؤقت أو الذاكرة الداخلية بحجم $M والذاكرة الخارجية غير المحدودة إلى$ كتل بحجم $B$ ، ويُحدد زمن تشغيل الخوارزمية بعدد عمليات نقل البيانات بين الذاكرة الداخلية والخارجية. ومثل نظيراتها التي لا تعتمد على ذاكرة التخزين المؤقت ، تحقق خوارزميات الفرز الخارجي المثلى تقاربياً زمن تشغيل (باستخدام ترميز Big O ) قدره $O\left({\tfrac {N}{B}}\log _{\tfrac {M}{B}}{\tfrac {N}{B}}\right)$ .

فرز الدمج الخارجي

من الأمثلة على الفرز الخارجي خوارزمية فرز الدمج الخارجي ، التي تستخدم خوارزمية دمج متعددة الاتجاهات . تقوم هذه الخوارزمية بفرز أجزاء البيانات بحيث يتناسب كل جزء مع مساحة ذاكرة الوصول العشوائي (RAM)، ثم تدمج الأجزاء المفرزة معًا. ^{[ 1 ]}^{[ 2 ]}

تقوم الخوارزمية أولاً بفرز $M$ عنصرًا في كل مرة، ثم تعيد القوائم المرتبة إلى الذاكرة الخارجية. ${\tfrac {M}{B}}$ يتم دمج القوائم المرتبة باستخدام دالة الدمج ثنائية الاتجاه، مع تكرار العملية إذا لم تكن الذاكرة الرئيسية كافية للدمج بكفاءة في دورة واحدة. خلال دورة الدمج، يتم تخزين $B$ عنصرًا من كل قائمة مرتبة في الذاكرة الداخلية، ويتم إخراج أصغر قيمة بشكل متكرر.

على سبيل المثال، لفرز 900 ميجابايت من البيانات باستخدام 100 ميجابايت فقط من ذاكرة الوصول العشوائي (RAM):

اقرأ 100 ميجابايت من البيانات في الذاكرة الرئيسية وقم بفرزها باستخدام طريقة تقليدية، مثل الفرز السريع .
اكتب البيانات المصنفة على القرص.
كرر الخطوتين 1 و 2 حتى تصبح جميع البيانات في أجزاء مرتبة بحجم 100 ميجابايت (هناك 900 ميجابايت / 100 ميجابايت = 9 أجزاء)، والتي يجب الآن دمجها في ملف إخراج واحد.
اقرأ أول 10 ميجابايت (= 100 ميجابايت / (9 أجزاء + 1)) من كل جزء مُرتب إلى مخازن الإدخال في الذاكرة الرئيسية، وخصص الـ 10 ميجابايت المتبقية لمخزن الإخراج. (عمليًا، قد يُحسّن الأداءَ زيادةُ حجم مخزن الإخراج وتقليلُ حجم مخازن الإدخال قليلًا).
قم بإجراء عملية دمج تساعية الاتجاهات ، واحفظ النتيجة في مخزن الإخراج المؤقت. عند امتلاء مخزن الإخراج المؤقت، اكتب البيانات إلى الملف النهائي المُرتب، ثم أفرغه. عند إفراغ أي من مخازن الإدخال التسعة المؤقتة، املأه بالبيانات العشرة ميجابايت التالية من الجزء المُرتب المرتبط به والبالغ حجمه 100 ميجابايت، وذلك حتى لا تتوفر بيانات إضافية من ذلك الجزء.

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

تاريخياً، بدلاً من الفرز، تم استخدام خوارزمية اختيار الاستبدال في بعض الأحيان ^{[ 3 ]} لإجراء التوزيع الأولي، لإنتاج نصف عدد أجزاء الإخراج في المتوسط بطول مضاعف.

تذاكر إضافية

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

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

لذا، لفرز بيانات بحجم 50 جيجابايت في 100 ميجابايت من ذاكرة الوصول العشوائي، على سبيل المثال، فإن استخدام عملية دمج واحدة بـ 500 مسار ليس فعالاً: إذ لا يمكننا قراءة سوى 100 ميجابايت / 501 ≈ 200 كيلوبايت من كل جزء في المرة الواحدة، وبالتالي يُهدر 5/6 من وقت القرص في البحث. استخدام عمليتي دمج يحل المشكلة. عندها قد تبدو عملية الفرز كالتالي:

قم بتشغيل عملية فرز الأجزاء الأولية كما كان من قبل لإنشاء أجزاء مرتبة بحجم 500 × 100 ميجابايت.
قم بتشغيل عملية دمج أولى تجمع 25 × 100 ميجابايت من الأجزاء في كل مرة، مما ينتج عنه 20 × 2.5 جيجابايت من الأجزاء المصنفة.
قم بتشغيل عملية دمج ثانية لدمج الأجزاء المصنفة بحجم 20 × 2.5 جيجابايت في نتيجة واحدة مصنفة بحجم 50 جيجابايت

على الرغم من أن هذا يتطلب مرورًا إضافيًا على البيانات، إلا أن كل قراءة أصبحت الآن بطول 4 ميجابايت، وبالتالي يُقضى خُمس وقت القرص فقط في البحث. ويُعوّض التحسن في كفاءة نقل البيانات أثناء عمليات الدمج (من 16.6% إلى 80%، أي ما يقارب خمسة أضعاف ) زيادة عدد عمليات الدمج بأكثر من الضعف.

تشمل الاختلافات استخدام وسيط تخزين وسيط مثل القرص الصلب ذي الحالة الصلبة (SSD) في بعض المراحل؛ ولا يشترط أن تكون سعة التخزين المؤقتة السريعة كافية لاستيعاب مجموعة البيانات بأكملها، بل يكفي أن تكون أكبر بكثير من الذاكرة الرئيسية المتاحة. بتكرار المثال السابق باستخدام 1 جيجابايت من مساحة تخزين SSD مؤقتة، يمكن للمرحلة الأولى دمج 10 أجزاء مُرتبة بحجم 100 ميجابايت لكل منها، مقروءة من تلك المساحة المؤقتة، لكتابة 50 جزءًا مُرتبًا بحجم 1 جيجابايت لكل منها على القرص الصلب (HDD). يُساهم النطاق الترددي العالي ومعدل القراءة العشوائية لمحركات SSD في تسريع المرحلة الأولى، ويمكن أن تصل قراءات القرص الصلب في المرحلة الثانية إلى 2 ميجابايت، وهو حجم كبير بما يكفي لضمان عدم استهلاك عمليات البحث معظم وقت القراءة. كما يمكن استخدام محركات SSD كمخازن مؤقتة للقراءة في مرحلة الدمج، مما يسمح بإجراء عدد أقل من عمليات القراءة الأكبر حجمًا (20 ميجابايت في هذا المثال) من القرص الصلب. نظرًا لانخفاض تكلفة سعة SSD مقارنةً بذاكرة الوصول العشوائي (RAM)، تُعد محركات SSD أداة اقتصادية لفرز المدخلات الكبيرة ذات الذاكرة المحدودة للغاية.

على غرار عمليات الفرز داخل الذاكرة، تتطلب عمليات الفرز الخارجية الفعالة زمنًا قدره O ( n log n ): تتطلب مجموعات البيانات المتنامية أُسّيًا عددًا متزايدًا خطيًا من عمليات الفرز، تستغرق كل منها زمنًا قدره O(n). ^{[ 4 ]} في ظل افتراضات معقولة، يمكن فرز ما لا يقل عن 500 جيجابايت من البيانات المخزنة على القرص الصلب باستخدام 1 جيجابايت من الذاكرة الرئيسية قبل أن تصبح عملية الفرز الثالثة مفيدة، ويمكن فرز كميات أكبر بكثير من البيانات قبل أن تصبح عملية الفرز الرابعة مفيدة. ^{[ 5 ]}

يُعدّ حجم الذاكرة الرئيسية عاملاً هاماً. فمضاعفة الذاكرة المخصصة للفرز تُقلّل عدد أجزاء البيانات وعدد عمليات القراءة لكل جزء إلى النصف، مما يُقلّل عدد عمليات البحث المطلوبة بنحو ثلاثة أرباع. كما أن نسبة ذاكرة الوصول العشوائي (RAM) إلى مساحة التخزين على الخوادم تجعل من المُلائم إجراء عمليات فرز ضخمة على مجموعة من الأجهزة ^{[ 6 ]} بدلاً من جهاز واحد مع عمليات فرز متعددة. وتُساهم وسائط التخزين ذات الأداء العالي للقراءة العشوائية، مثل محركات الأقراص الصلبة (SSD)، في زيادة كمية البيانات التي يُمكن فرزها قبل أن تُحسّن عمليات الفرز الإضافية الأداء.

فرز التوزيع الخارجي

تُشابه خوارزمية فرز التوزيع الخارجي خوارزمية الفرز السريع . وتجد الخوارزمية تقريبًا ${\tfrac {M}{B}}$ تستخدم هذه العملية المحاور لتقسيم العناصر $N$ إلى مصفوفات فرعية متساوية الحجم تقريبًا، بحيث يكون كل عنصر أصغر من العنصر الذي يليه، ثم تُكرر العملية حتى تصبح أحجام المصفوفات الفرعية أقل من حجم الكتلة . عندما تصبح المصفوفات الفرعية أقل من حجم الكتلة، يمكن إجراء الفرز بسرعة لأن جميع عمليات القراءة والكتابة تتم في الذاكرة المؤقتة ، بينما يتطلب نموذج الذاكرة الخارجية $O(1)$ العمليات.

ومع ذلك، فإن العثور على ذلك بالضبط ${\tfrac {M}{B}}$ لن تكون نقاط الارتكاز سريعة بما يكفي لجعل فرز التوزيع الخارجي مثاليًا تقاربًا . بدلًا من ذلك، نجد عددًا أقل قليلًا من نقاط الارتكاز. لإيجاد هذه النقاط، تقسم الخوارزمية عناصر الإدخال $N$ إلى ${\tfrac {N}{M}}$ قطع، ويأخذ كل ${\sqrt {\tfrac {M}{16B}}}$ العناصر، ويستخدم بشكل متكرر خوارزمية وسيط الوسائط لإيجاد ${\sqrt {\tfrac {M}{B}}}$ المحاور. ^{[ 7 ]}

توجد ازدواجية ، أو تشابه أساسي، بين الخوارزميات القائمة على الدمج والخوارزميات القائمة على التوزيع. ^{[ 8 ]}

أداء

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

استخدام التوازي
- يمكن استخدام عدة أقراص صلبة بالتوازي لتحسين سرعة القراءة والكتابة المتسلسلة. وهذا يُعد تحسينًا فعالًا من حيث التكلفة: إذ يستخدم جهاز فائز في اختبار فرز البيانات (Penny Sort) ضمن فئة الأجهزة متوسطة المواصفات ستة أقراص صلبة. ^{[ 9 ]}
- يمكن لبرامج الفرز استخدام خيوط متعددة لتسريع العملية على أجهزة الكمبيوتر الحديثة متعددة النوى.
- يمكن للبرامج استخدام الإدخال/الإخراج غير المتزامن بحيث يمكن فرز أو دمج مجموعة واحدة من البيانات بينما تتم قراءة مجموعات أخرى من القرص أو كتابتها إليه.
- يمكن لأجهزة متعددة متصلة بوصلات شبكة سريعة أن تقوم كل منها بفرز جزء من مجموعة بيانات ضخمة بالتوازي. ^{[ 10 ]}
زيادة سرعة الأجهزة
- يمكن أن يؤدي استخدام المزيد من ذاكرة الوصول العشوائي (RAM) للفرز إلى تقليل عدد عمليات البحث على القرص وتجنب الحاجة إلى المزيد من عمليات المرور.
- يمكن للذاكرة الخارجية السريعة مثل محركات الأقراص الصلبة أن تسرع عمليات الفرز، إما إذا كانت البيانات صغيرة بما يكفي لتناسب محركات الأقراص الصلبة بالكامل أو، في حالات نادرة، لتسريع فرز أجزاء بحجم محركات الأقراص الصلبة في عملية فرز من ثلاث مراحل.
- تؤثر عوامل أخرى عديدة على أقصى سرعة فرز للأجهزة، منها: سرعة المعالج وعدد أنويته، وزمن استجابة الوصول إلى ذاكرة الوصول العشوائي، وعرض نطاق الإدخال/الإخراج، وسرعة قراءة/كتابة القرص، وزمن البحث في القرص، وغيرها. ويُعدّ "موازنة" الأجهزة لتقليل الاختناقات جزءًا أساسيًا من تصميم نظام فرز فعّال.
- يمكن أن تكون الكفاءة في التكلفة والسرعة المطلقة أمراً بالغ الأهمية، خاصة في بيئات المجموعات حيث تسمح تكاليف العقد المنخفضة بشراء المزيد من العقد.
زيادة سرعة البرمجيات
- يستخدم بعض المشاركين في مسابقة Sort Benchmark شكلاً معدلاً من خوارزمية الفرز الجذري في المرحلة الأولى من الفرز: حيث يفصلون البيانات إلى عدة "مجموعات" بناءً على بداية قيمتها. وتتميز بيانات مسابقة Sort Benchmark بأنها عشوائية، مما يجعلها مناسبة تماماً لهذا النوع من التحسين.
- يمكن لضغط ملفات الإدخال والملفات الوسيطة والإخراج أن يقلل من الوقت المستغرق في عمليات الإدخال/الإخراج، ولكنه غير مسموح به في معيار الفرز.
- لأن برنامج Sort Benchmark يقوم بفرز السجلات الطويلة (100 بايت) باستخدام مفاتيح قصيرة (10 بايت)، فإن برامج الفرز تقوم أحيانًا بإعادة ترتيب المفاتيح بشكل منفصل عن القيم لتقليل حجم إدخال/إخراج الذاكرة.

انظر أيضاً

مراجع

↑ دونالد كنوث ، فن برمجة الحاسوب ، المجلد 3: الفرز والبحث ، الطبعة الثانية. أديسون-ويسلي، 1998، رقم ISBN 0-201-89685-0، القسم 5.4: الفرز الخارجي، الصفحات 248-379.
↑ إليس هورويتز وسارتاج ساهني ، أساسيات هياكل البيانات ، إتش. فريمان وشركاه، رقم ISBN 0-7167-8042-9.
↑ دونالد كنوث ، فن برمجة الحاسوب ، المجلد 3: الفرز والبحث ، الطبعة الثانية. أديسون-ويسلي، 1998، رقم ISBN 0-201-89685-0، القسم 5.4: الفرز الخارجي، الصفحات 254 وما بعدها.
↑ إحدى طرق فهم ذلك هي أنه بافتراض حجم ذاكرة ثابت (مثلاً 1 جيجابايت) وحجم قراءة أدنى (مثلاً 2 ميجابايت)، يمكن لكل عملية دمج دمج عدد معين من عمليات التشغيل (مثلاً 500) في عملية واحدة، مما يخلق حالة فرق تسد مشابهة لفرز الدمج في الذاكرة. حجم كل عملية فرز في الذاكرة الرئيسية وعدد الطرق في كل عملية دمج لهما حد أعلى ثابت، لذا فهما لا يؤثران على تعقيد الخوارزمية (Big-O).
على سبيل المثال، لنفترض وجود 500 جيجابايت من البيانات المراد فرزها،وذاكرة تخزين مؤقتة بسعة 1 جيجابايت، وقرص واحدبسرعة نقل بيانات 200 ميجابايت/ثانيةوزمن بحث 20 مللي ثانية. ستستخدم مرحلة دمج واحدة لـ 500 مسار مخازن مؤقتة بسعة 2ميجابايت لكل منها، وستحتاج إلى إجراء 250 ألفعملية بحث أثناء قراءة ثم كتابة 500جيجابايت. سيستغرق ذلك 5000 ثانية للبحث و5000ثانية للنقل. إن إجراء عمليتي دمج كما هو موضح أعلاه من شأنه أن يقلل زمن البحث بشكل كبير، ولكنه سيضيف 5000 ثانية إضافيةلزمن نقل البيانات، لذا فهذه هي نقطة التعادل تقريبًا بين الفرز على مرحلتين والفرز على ثلاث مراحل.
↑ كريس نيبرغ، ميهول شاه، الصفحة الرئيسية لمعيار الفرز (روابط لأمثلة على الفرز المتوازي)
↑ أغاروال، ألوك؛ فيتر، جيفري (1988). "تعقيد المدخلات/المخرجات في الفرز والمشاكل ذات الصلة" (ملف PDF) . مجلة اتصالات رابطة مكائن الحوسبة . 31 (9): 1116-1127 . doi : 10.1145/48529.48535 .
↑ جيه إس فيتر ، الخوارزميات وهياكل البيانات للذاكرة الخارجية ، سلسلة أسس واتجاهات في علوم الحاسوب النظرية، دار النشر ناو، هانوفر، ماساتشوستس، 2008، رقم ISBN 978-1-60198-106-6.
↑ نيكولاس أسكيتيس، أوزسورت 2.0: فرز ما يصل إلى 252 جيجابايت مقابل بنس واحد
↑ راسموسن وآخرون، تريتون سورت

روابط خارجية

الفرز الخارجي في لغة C#

[1] دونالد كنوث ، فن برمجة الحاسوب ، المجلد 3: الفرز والبحث ، الطبعة الثانية. أديسون-ويسلي، 1998، رقم ISBN 0-201-89685-0، القسم 5.4: الفرز الخارجي، الصفحات 248-379.

[2] إليس هورويتز وسارتاج ساهني ، أساسيات هياكل البيانات ، إتش. فريمان وشركاه، رقم ISBN 0-7167-8042-9.

[3] دونالد كنوث ، فن برمجة الحاسوب ، المجلد 3: الفرز والبحث ، الطبعة الثانية. أديسون-ويسلي، 1998، رقم ISBN 0-201-89685-0، القسم 5.4: الفرز الخارجي، الصفحات 254 وما بعدها.

[4] إحدى طرق فهم ذلك هي أنه بافتراض حجم ذاكرة ثابت (مثلاً 1 جيجابايت) وحجم قراءة أدنى (مثلاً 2 ميجابايت)، يمكن لكل عملية دمج دمج عدد معين من عمليات التشغيل (مثلاً 500) في عملية واحدة، مما يخلق حالة فرق تسد مشابهة لفرز الدمج في الذاكرة. حجم كل عملية فرز في الذاكرة الرئيسية وعدد الطرق في كل عملية دمج لهما حد أعلى ثابت، لذا فهما لا يؤثران على تعقيد الخوارزمية (Big-O).

[5] على سبيل المثال، لنفترض وجود 500 جيجابايت من البيانات المراد فرزها،وذاكرة تخزين مؤقتة بسعة 1 جيجابايت، وقرص واحدبسرعة نقل بيانات 200 ميجابايت/ثانيةوزمن بحث 20 مللي ثانية. ستستخدم مرحلة دمج واحدة لـ 500 مسار مخازن مؤقتة بسعة 2ميجابايت لكل منها، وستحتاج إلى إجراء 250 ألفعملية بحث أثناء قراءة ثم كتابة 500جيجابايت. سيستغرق ذلك 5000 ثانية للبحث و5000ثانية للنقل. إن إجراء عمليتي دمج كما هو موضح أعلاه من شأنه أن يقلل زمن البحث بشكل كبير، ولكنه سيضيف 5000 ثانية إضافيةلزمن نقل البيانات، لذا فهذه هي نقطة التعادل تقريبًا بين الفرز على مرحلتين والفرز على ثلاث مراحل.

[6] كريس نيبرغ، ميهول شاه، الصفحة الرئيسية لمعيار الفرز (روابط لأمثلة على الفرز المتوازي)

[Aggarwal88-7] أغاروال، ألوك؛ فيتر، جيفري (1988). "تعقيد المدخلات/المخرجات في الفرز والمشاكل ذات الصلة" (ملف PDF) . مجلة اتصالات رابطة مكائن الحوسبة . 31 (9): 1116-1127 . doi : 10.1145/48529.48535 .

[8] جيه إس فيتر ، الخوارزميات وهياكل البيانات للذاكرة الخارجية ، سلسلة أسس واتجاهات في علوم الحاسوب النظرية، دار النشر ناو، هانوفر، ماساتشوستس، 2008، رقم ISBN 978-1-60198-106-6.

[9] نيكولاس أسكيتيس، أوزسورت 2.0: فرز ما يصل إلى 252 جيجابايت مقابل بنس واحد

[10] راسموسن وآخرون، تريتون سورت

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]