وأكثر عن أنواع

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

هناك العشرات من الطرق المختلفة لترتيب عناصر البيانات بالترتيب. من بينها ، هناك من يعمل بسرعة ، على سبيل المثال ، يمكنهم فرز أي صفيف بيانات موجود في ذاكرة الوصول العشوائي للكمبيوتر في مدة أقصاها دقائق. وبشكل أكثر تحديداً ، يمكن القول أن الفرز السريع ينظم مليار رقم صحيح في كمبيوتر شخصي حديث جيد في أقل من مئة ثانية. إذا كنت تستخدم طرقًا بطيئة وبدائية ، على سبيل المثال ، فرز الفقاعات أو فرز التحديد ، لفرز عدد أكبر من العناصر ، فإن الوقت الذي تستغرقه معالجة البيانات هذه يمكن أن يتجاوز أي توقعات - مثل "المعالجة" قد تستغرق بالفعل عدة أيام ، أسابيع ، وحتى سنوات. هذا الاختلاف الكبير ناتج عن حقيقة أن وقت الفرز بالطرق السريعة يستغرق تقريبًا نسبيًا من N log N و البدائي - N ² . مع زيادة N ، يصبح الفرق بين القيمتين ملحوظًا للغاية. لذلك ، من المعقول استخدام الطرق البدائية فقط للعمل مع البيانات الصغيرة ، على سبيل المثال ، على أجهزة الكمبيوتر الحديثة ، وحتى عدة آلاف من العناصر. من الطبيعي أيضًا استخدامها لتدريس أساسيات البرمجة والتفكير المنطقي ، لأنها أبسط بكثير من الطرق السريعة.

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

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

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

من المحتمل أن يكون رمز الطريقة الأخيرة البطيئة ، وهي نوع الإدراج ، هو الأقصر بين جميع الرموز التي تنفذ عملية الفرز ، لذلك تستخدم هذه الطريقة أحيانًا بواسطة أنواع سريعة معقدة للحالات التي يكون فيها عدد العناصر التي سيتم فرزها صغيرًا (عدة عشرات). إنه يشبه إلى حد ما الفرز حسب الفقاعة ، حيث يتم هنا مقارنة العناصر المجاورة على التوالي. لكن الفرز حسب المدخل يبحث عن العنصر التالي للموضع الصحيح في الجزء الذي تم فرزه بالفعل من البيانات ، ولا يدفع فقط العنصر المتطرف إلى الموضع المتطرف. مع هذا النهج ، ذاكرة إضافية غير مطلوبة أيضًا. مثل فرز الفقاعات ، يكون فرز الإدراج سريعًا للغاية في البيانات المرتبة وأسرع في البيانات المرتبة جزئيًا. في الحالة الأخيرة ، أسرع بكثير من الفقاعة. عادة ما يكون الفرز حسب عمليات الإدخال أسرع إلى حد ما من الفرز حسب الاختيار. وعلى عكس الأخير ، فإنه ، مثل فرز الفقاعات ، مستقر. والأسوأ من ذلك كله ، أن فرز الإدراج يعمل مع البيانات بترتيب عكسي ، والذي يصبح في بعض الأحيان أبطأ من أبطأ. للاختبارات ، تم استخدام التنفيذ التالي. يمكن تسريعها قليلاً إذا كنت لا تستخدم بحثًا خطيًا ، ولكن بحثًا ثنائيًا ، على سبيل المثال ، باستخدام الدالة std :: bsearch. يمكن تحقيق تسارع كبير باستخدام هيكل نوع القائمة ، وإدراج عنصر سريع للغاية. يمكنك أيضًا ملاحظة أن هذا هو الفرز الأكثر طبيعية - فهو ، على سبيل المثال ، يستخدم بشكل حدسي عند لعب الورق.

يُعد فرز Shell هو أبسط الطرق السريعة وهو مناسب تمامًا للطلاب الذين بدأوا لتعلم البرمجة. انها ليست سوى بعض التعديلات من الفرز فقاعة. الفرق الوحيد بينهما هو أنه في فرز Shell ، يتم أخذ المسافة بين العناصر المقارنة متفاوتة من مرور إلى مرور ، من أكبر في التمري الأول ، إلى واحد في الأخير ، وبالتالي ، في هذه الممرات الأخيرة ، تتحول طريقة Shell إلى فرز بدائي بواسطة فقاعة. نشر دونالد شل خوارزمية الفرز الأساسية التي حصلت على اسمه في عام 1959. وبالتالي ، هذه هي واحدة من الفرز العالمية الأولى التي تعمل بسرعة. للمقارنة ، تم نشر خوارزمية الفرز السريع بعد عامين ، وأصبح الفرز أو الفرز الاستقرائي الشهير لـ تيم معروفًا في التسعينيات فقط. ترتبط العديد من المشكلات الرياضية المثيرة التي لم يتم حلها بفرز Shell ، وأهمها هو كيفية اختيار الاختلافات بين العناصر المقارنة بالشكل الأمثل. تم العثور على بعض تسلسل السجلات ، على سبيل المثال ، A102549 . تم العثور على هذه التسلسلات من خلال الحسابات الضخمة ، بحيث يكون لها طول قصير للغاية ، A102549 هو فقط 8 عناصر ، وهو ما يكفي فقط للبيانات التي تصل إلى حوالي 3000 عنصر. بالنسبة للبيانات الضخمة ، يلزم البحث بشكل عشوائي تقريبًا. أظهرت القيم المستخدمة القريبة من القوى 2 و e و 2.25 و 3. الأعداد الأولية القريبة من القوى 2 أسوأ النتائج ، أدنى بشكل ملحوظ من الأفضل. لكن تبين أن الخيارات الثلاثة الأخرى هي نفسها تقريبًا من حيث التأثير على الأداء وربما قريبة جدًا من المستوى الأمثل. علاوة على ذلك ، في هذه الحالات الثلاث ، لم يمنح استخدام الأعداد الأولية مزايا ملموسة. من الغريب أن التحيزات المقترحة على ويكيبيديا (القائمة على 2.25) بناءً على مراجع إلى الأعمال المقابلة لم تظهر أفضل النتائج في الاختبارات ، على الرغم من أن فروقها عن الأفضل كانت ضئيلة للغاية (لا تزيد عن 5-10٪). باستخدام A102549 كنقطة انطلاق أيضا لم تعطي أي نتائج ملحوظة. حاول ميخائيل أوباناسينكو أيضًا كشف عملية الفرز على شركة شل وحصلت على نتيجة مثيرة للاهتمام وهي أن عمليات النزوح التي تم اختيارها من خلال الصيغة s _{n + 1} = 10s _n / 3 تعطي تأثيرًا جيدًا للغاية وربما حتى قريبة من المثالية. نتائجي تؤكد هذا. في كثير من الحالات ، كانت هذه التحيزات هي التي أعطت أفضل نتيجة ، على الرغم من أن هذا لم يكن هو الحال دائمًا وكانت الفجوة من أقرب نتيجة صغيرة جدًا (حوالي 5٪). تستخدم الكود الخاص بي لتنفيذ عمليات تصنيف Shell الجداول الصغيرة ذات الإزاحة ، على الرغم من أنك إذا لم تستخدم الأرقام الأولية ، فيمكن حساب هذه الإزاحات للجداول على الفور تقريبًا ، كما حدث في تنفيذ أحد المتغيرات المحددة لهذا الفرز.

من المثير للاهتمام أننا إذا قمنا بإزاحة قريبة من القوى الثلاثة بطريقة مختلفة قليلاً واستخدام خوارزمية مختلفة قليلاً (انظر التنفيذ ) ، فسنحصل على أرقام 32 بت على سرعات قريبة من الأفضل ، ولكن على الأرقام الأطول وعلى الخطوط ، سنحصل على تباطؤ كبير ، أحيانًا أكثر من 100 ٪. نتائج أفضل الخوارزمية المستخدمة من قبل oms7 موجودة أيضًا في الجدول أدناه ، ولكن على الرغم من أنها تظهر نتائج جيدة بالترتيب ، إلا أنها متأخرة بشكل كبير عن الزعماء من حيث القيم المطلقة.

هل ستكون هناك طريقة للعثور على أفضل الإزاحات؟ ربما ، لكنني أجرؤ على الإشارة إلى أنه لم يحن بعد. يتم استخدام الفرز Shell في kernel Linux ، وفي مكتبة C واحدة على الأقل يتم استخدام الرمز الخاص به لوظيفة qsort () القياسية. لقد تم إثبات نظريًا أن سرعة الفرز المثالية من قِبل Shell أبطأ قليلاً من الطرق اللوغاريتمية السريعة "الحقيقية". في الواقع ، يتم وصف اعتماد متوسط ​​وقت معالجة البيانات على حجمها للفرز الأمثل لشل بواسطة المعادلة ∽ N (سجل N / log log N ) ² ، والتي حتى بالنسبة إلى N كبيرة جدًا فهي قريبة جدًا من الصيغة ∽ N log N النموذجية للطرق السريعة الأخرى. عادةً ما يكون فرز Shell في الغالب أسرع من الطرق الأسرع من الناحية النظرية بالترتيب ويبدأ فقط في الخضوع لها قليلاً عند معالجة المصفوفات الكبيرة إلى حد ما (بترتيب 10 ملايين عنصر). لا يحتاج هذا التصنيف مطلقًا إلى ذاكرة إضافية ويتصرف بثبات لمجموعة واسعة من الخيارات لملء البيانات ، مقارنة إيجابية مع الفرز السريع. طريقة شل لا تمتلك خاصية الاستقرار.

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

نعتبر أيضًا خوارزمية Lomuto المدمجة للغاية ، والتي تكون أحيانًا أسرع قليلاً (حوالي 1٪) من طريقة Hoare. ومع ذلك ، في الحالات الخاصة النموذجية ، على سبيل المثال ، في البيانات المرتبة أو العكسية أو الضارة ، تُظهر طريقة Lomuto البطء الشديد. بالإضافة إلى ذلك ، من بين الخيارات التي تم بحثها للفرز السريع ، اتضح أن هذا هو الأكثر جشعًا بالنسبة لحجم المكدس أثناء التشغيل العملي: عند فرز المصفوفات الصغيرة نسبيًا ، هذا النوع فقط لا يحتوي على ما يكفي من 8 ميجابايت للمكدس ، كان علي ضبط هذا الحجم من خلال ulimit أكثر. يؤدي مثل هذا الجشع في المجموعة إلى تباطؤ كبير عند معالجة البيانات الضخمة (عشرات الملايين من الخطوط) ، وأواجه صعوبة في الاتصال بطبيعتها. لا يمكنني إلا أن أذكر أنه من الأفضل عدم استخدام هذا الفرز من الفقرة التالية بمثل هذه البيانات.

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

في عام 2009 ، تم نشر خوارزمية سريعة الفرز ثنائية الاتجاه ، والتي أصبحت قياسية للغة جافا. تقلل هذه الخوارزمية من عدد التباديل بنسبة 20 ٪ مقارنة مع أفضل التباينات ، ولكن لا يتغير عدد المقارنات. مؤلفها هو فلاديمير ياروسلافسكي. إنها تعمل حقًا ، كقاعدة عامة ، أسرع من الأنواع السريعة الأخرى. لقد قمت بتحسينه قليلاً ، باستخدام الحقيقة المعروفة منذ زمن طويل وهي أنه في نظام x86 ، عادةً ما يكون التبادل أسرع من الواجب ، وبالنسبة لسلاسل C ++ يكون أسرع بكثير. جميع الفرز السريعة التي تم اعتبارها حتى الآن لا تملك خاصية الاستقرار.

هناك حاجة إلى ذاكرة إضافية للفرز السريع لتنظيم المكالمات العودية. ومع ذلك ، يمكن الاستعاضة عن هذه المكالمة الثانية بحلقة ، عن طريق تحسين العودية الذيل ، والتي من حيث السرعة قد لا تعطي أي مكاسب ، ولكن يقلل بشكل كبير من حجم البيانات الإضافية المستخدمة. لقد طبقت خيار فرز Hoar مع هذا التحسين. بالإضافة إلى ذلك ، في برامج النظام ، يمكنك التحقق من مؤشر الرصة وإذا كان يقترب من قيمة حرجة ، يمكنك ببساطة إعادة تعيين جميع المكالمات المتكررة والبدء في الفرز مرة أخرى - لهذه الحالة ، من الواضح أنك بحاجة إلى استخدام خيار الفرز السريع الذي لا يؤدي إلى إبطاء في البيانات المطلوبة تقريبًا ، على سبيل المثال ، النسخة المقترحة أعلاه من هوار. يمكن اعتبار مكافحة استخدام ذاكرة إضافية الفكرة الرئيسية للفرز السريع من مكتبة اللغة C القياسية في دول مجلس التعاون الخليجي. تخلّى عن العودية بشكل عام. بدلاً من ذلك ، يستخدمون محاكاة لها ، والذي يسمح لثالث للحد من الحمل على المكدس. تحولت الشفرة إلى حد كبير ، حوالي 150 سطرًا. حول هذا التصنيف ، لا يزال هناك القليل من المواد أدناه.

يمكن أن يكون فرز التجزئة سريعًا جدًا ، بالقرب من ∽ N. ومع ذلك ، في بعض الأحيان يمكن أن تعمل على الاعتماد من الدرجة الثانية. تعتمد سرعة طريقة الفرز هذه على المدخلات. إذا تم توزيع البيانات بالتساوي بواسطة دالة التجزئة على المصفوفة المساعدة ، فسنحصل على أسرع علاقة خطية. وإذا تم تجميع جميع البيانات بالقرب من عدة "مراكز كتلة" متباعدة أو عندما يكون هناك العديد من عناصر البيانات المتماثلة ، أي عندما يحدث الكثير من تصادمات التجزئة ، سنحصل على أسوأ أنواع الاعتماد على N ² . كما هو الحال مع فرز الشجرة ، لفرز التجزئة ، تحتاج إلى الكثير من البيانات الإضافية ، في قائمة الأكواد أدناه التي تحتاجها ، على سبيل المثال ، 12 بايت إضافية لكل عدد صحيح قابل للفرز (int32 ، x86-64). خاصية مثيرة للاهتمام لفرز التجزئة هي عدم وجود عمليات مقارنة بين عناصر البيانات ، مما يميز هذا الفرز عن جميع العناصر المذكورة أعلاه. بتعبير أدق ، هذه العمليات ضرورية فقط للتصادم. عند فرز البيانات حيث يتطابق المفتاح مع عنصر البيانات بالكامل ، يمكنك استخدام عداد إضافي لعدد العناصر المتطابقة ، ولكن هذا يعد تحسينًا مشكوكًا فيه. يمكنك أيضًا استخدام الشجرة الثنائية بدلاً من القائمة لتخزين بيانات تصادم التجزئة ، مما يؤدي إلى تسريع العمل لحالات فردية معينة عندما يكون هناك العديد من التصادمات ، ولكن بشكل عام ، عند استخدام الشجرة الثنائية ، يبطئ في كثير من الحالات وهذا على الرغم من حقيقة أن العنصر في هذه الحالة البيانات لتخزين ما يقرب من 100 بايت من المعلومات الإضافية. لقد طبقت ثلاثة خيارات لفرز التجزئة باستخدام شجرة ثنائية: أحدهما يستخدم شجرة غير مرتبة ، والآخران يستخدمان الأشجار القياسية من مكتبة std ويدعمان المكتبات. يعد تصنيف التجزئة غير مناسب عملياً لفرز سلاسل النص ، باستثناء تلك القصيرة جدًا ، نظرًا لأنه من المستحيل إنشاء دالة تجزئة جيدة لمثل هذه البيانات. لم أتمكن من تكييف تجزئة C ++ القياسية (unordered_multiset) للفرز: حاولت استخدام وظائف تجزئة رتيبة وترتيب العلاقات بدلاً من المساواة - لم ينجح هذا.

فرز الصفيف مشابه جدًا للفرز السابق. يتم استخدام صفيف إضافي أيضًا ، حيث يتم إدخال القيم بواسطة دالة التجزئة. في حالة حدوث تصادم ، من الضروري تحويل الجزء المستمر من العناصر المشغولة إلى الموضع الأيسر أو الأيمن ، لتحرير الموضع المشار إليه بواسطة دالة التجزئة للعنصر الجديد. للحصول على سرعة جيدة ، من الضروري أن تكون المصفوفة المساعدة عدة مرات (من 2-3) أكثر من المصفوفة الأصلية. مع زيادة حجم المصفوفة المساعدة ، تزداد السرعة فقط إلى حد معين ، اعتمادًا على البيانات المصنفة ووظيفة التجزئة المرتبطة بها ، ثم تنخفض (عادةً من 4-5). تكون سرعة التشغيل مماثلة لسرعة التجزئة ، ولكن في البيانات الجيدة أسرع قليلاً ، وفي البيانات السيئة تكون أبطأ بشكل ملحوظ. هذا النوع يحتاج أيضا إلى الكثير من الذاكرة الإضافية.إذا قصرنا عدد العناصر في المصفوفة المفروزة على ما يزيد قليلاً عن أربعة مليارات ، فإن المصفوفة المساعدة الثلاثية ستتطلب نفس القدر من البيانات الإضافية مثل الفرز باستخدام التجزئة ، وسيتطلب العنصر الثلاثي ثلاثة وعشرين بايت ، وهو أقل بشكل ملحوظ من الفرز حسب الشجرة ، أو أقل بكثير من التجزئة مع الأشجار. هذا الفرز أيضًا غير مناسب تقريبًا للعمل مع السلاسل. لا يوجد مقال في ويكيبيديا حول مثل هذه الخوارزمية ، ولكن هنا هو تنفيذي .

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

أحد الفرز الأسرع ، التي لا تستخدم المقارنات مطلقًا ، هو الفرز المعياري المعروف منذ القرن التاسع عشر.(نوع الجذر). فكرتها بسيطة للغاية - تحتاج إلى العمل مع مجموعات من بتات تمثيل البيانات (للاختبارات التي أجريتها مجموعات من 8 و 11 و 16 بت). يتم تصميم الجداول لكل مجموعة ، ثم يتم دمج النتائج بطريقة بسيطة نسبيًا. هناك طريقتان رئيسيتان لاستخدام الفرز bitwise. من الملائم أخذ الأرقام لفرز الأرقام من اليمين إلى اليسار (هذا هو الخيار LSD - Least Significant Digit) ولفرز السلاسل من اليسار إلى اليمين (هذا هو MSD - معظم الأرقام المميزة). غالبًا ما يكون الفرز في اتجاه البت أسرع من أي طريقة أخرى لترتيب البيانات. من المثير للدهشة ، أن دعم الفرز bitwise لا يزال غير مهم للغاية: إنه ليس في دفعة ولا في مكتبة C ++ القياسية ، حتى أنني لست على علم بإصداره لأي مكتبة معروفة للعمل مع أرقام أو سلاسل C ++. هذا النوع لديهبالطبع ، وعيوبها. إنه حساس للغاية لنوع البيانات للفرز ، على سبيل المثال ، يجب أن يكون لديك نسختك الخاصة من هذا الفرز للبيانات من كل حجم ، وتحتاج إلى عمل خيارات خاصة للأعداد الصحيحة غير الموقعة والموقعة ، وقد يتطلب دعم العمل بأرقام حقيقية جهدًا كبيرًا. عند استخدام الترتيب من البايت الأقل أهمية إلى الأكثر أهمية ، يتطلب متغيره عادة ذاكرة إضافية ، أكثر قليلاً من البيانات الأولية (هذا أقل بكثير من الترتيب حسب التجزئة أو المصفوفة ، وحتى أكثر من ذلك بواسطة شجرة). بالإضافة إلى ذلك ، هذا الخيار ذو فائدة قليلة لفرز الأوتار الطويلة. الرمز الخاص بي لهذا النوعتحتاج إلى عمل خيارات خاصة للأعداد الصحيحة غير الموقعة والموقعة ، وقد يتطلب دعم العمل بالأرقام الحقيقية الكثير من الجهد. عند استخدام الترتيب من البايت الأقل أهمية إلى الأكثر أهمية ، يتطلب متغيره عادة ذاكرة إضافية أكبر قليلاً من البيانات الأصلية (هذا أقل بكثير من الترتيب حسب التجزئة أو المصفوفة ، وحتى أكثر من ذلك بواسطة شجرة). بالإضافة إلى ذلك ، هذا الخيار ذو فائدة قليلة لفرز الأوتار الطويلة. الرمز الخاص بي لهذا النوعتحتاج إلى عمل خيارات خاصة للأعداد الصحيحة غير الموقعة والموقعة ، وقد يتطلب دعم العمل بالأرقام الحقيقية الكثير من الجهد. عند استخدام الترتيب من البايت الأقل أهمية إلى الأكثر أهمية ، يتطلب متغيره عادة ذاكرة إضافية أكبر قليلاً من البيانات الأصلية (هذا أقل بكثير من الترتيب حسب التجزئة أو المصفوفة ، وحتى أكثر من ذلك بواسطة شجرة). بالإضافة إلى ذلك ، هذا الخيار ذو فائدة قليلة لفرز الأوتار الطويلة. الرمز الخاص بي لهذا النوعهذا الخيار غير مناسب لفرز سلاسل طويلة. الرمز الخاص بي لهذا النوعهذا الخيار غير مناسب لفرز سلاسل طويلة. الرمز الخاص بي لهذا النوعهنا ، يعتمد على الكود من مقالة oms7 المذكورة. يعد خيار ترتيب البايت العكسي أكثر تنوعًا وهو مناسب تمامًا لفرز الأوتار. يمكن تنفيذ هذا الخيار دون استخدام ذاكرة إضافية (ثمن ذلك هو فقدان خاصية الثبات) ، كما هو الحال في وظيفة radixsort () لمكتبة bsd. الكود الخاص بيبالنسبة لهذا الخيار ، فإنه يستند أيضًا إلى الكود oms7 ، ويستخدم ذاكرة إضافية ، وبيانات مصدر أكبر قليلاً ، ويحتوي على خاصية الثبات ، لكنه غير مُحسَّن للسلاسل ، وبالتالي يُظهر خصائص أداء أسوأ بكثير من دالة مماثلة sradixsort () من مكتبة bsd المذكورة بالفعل . هذا الفرز يمكن أن يُظهر نتائج سيئة بشكل مدهش عند العمل مع مصفوفات عددية صغيرة ، يعمل بعدة أوامر بحجم أبطأ من الفقاعة الزوجية ، على الرغم من أننا نتحدث عن قيم صغيرة جدًا لا تزيد عن بضع ميلي ثانية ، وهذا الاختلاف ليس من السهل ملاحظته. هذا يرجع إلى حقيقة أنه يستخدم صفائف مساعدة ذات حجم صغير ، ولكن عند فرز البيانات ذات الحجم الصغير ، قد تكون هذه الأحجام الصغيرة أكبر من البيانات المصنفة نفسها.لتجنب التباطؤ ، يستخدم خيار "من اليسار إلى اليمين" فرز الإدراج بدلاً من الخيار الرئيسي في مثل هذه الحالات. في الختام ، تجدر الإشارة إلى أن هذا هو الفرز الشائع نسبياً الوحيد المعروف لي والذي يعمل دائمًا بشكل موثوق بسرعة ∽N ، لكن معامل التناسب هنا يعتمد على حجم عناصر البيانات وللأوتار أو الأعداد الطويلة يمكن أن يكون ملحوظًا.

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

علاوة على ذلك ، سننظر في بعض الفرز التي يمكن العثور عليها في المكتبات القياسية.

لنبدأ بالصيام من مكتبة C القياسية (qsort ، أحد أنواع دول مجلس التعاون الخليجي) ، لقد كتبت عنها بالفعل. لا يمكنني إلا أن أضيف هنا أن هذا الفرز وكذلك الفرز C الأخرى (على سبيل المثال ، ما يلي من مكتبة BSD) غير مناسب للعمل مع بيانات الكائن ، على وجه الخصوص ، سلاسل C ++ ، والتي تنتج عن حقيقة أن هذه البيانات ليست POD. امتلاك المصدر ، يمكن حل المشكلة بسهولة عن طريق استبدال عمليات memcpy بمهام منتظمة. قد تلاحظ أيضًا أنه في بعض مكتبات C القياسية ، قد لا يكون هذا الفرز سريعًا بالضرورة ، ويمكن استبداله بأخرى. في الإصدار الحالي لدول مجلس التعاون الخليجي ، هذا الفرز لديه خاصية الاستقرار. كانت هناك مفاجآت في بعض الأحيان مع عمليات التصنيف c المذكورة عند جمع البيانات ، على سبيل المثال ، عند العمل مع النوع std :: vector من خلال كائن وظيفي ، فإنها قد تخلق صعوبات - يمكنني أن أوصي باستخدامها مع بيانات الكائن بحذر. وفقًا للأشواط ، يكون هذا الفرز بطيئًا نسبيًا في بعض الأحيان: إنه أدنى بشكل ملحوظ من حيث السرعة في تطبيقات أخرى من الفرز السريع عند العمل مع الأرقام ، ولكن عند العمل باستخدام الأوتار الأفضل ، فإن الفرز باستخدام نقطتي تحكم يؤدي أحيانًا إلى الأمام ،ولكن على الخطوط الطويلة ، فإن qsort القياسية تتفوق عليها دائمًا. تم اكتشاف الشيء الأكثر إثارة عندما حاولت فرز مليار أعداد صحيحة بمساعدتها - اتضح أن ملء النوع 7 يؤدي إلى اعتماد وقت قريب من القانون التربيعي ، أي إلى "معالجة" محتملة تدوم حتى عدة سنوات (لم أنتظر النهاية وأوقفتها في 21 ساعة من التشغيل). باستخدام بيانات أقل ، يمكن لهذا الفرز تحديد نقاط الربط التي يعمل بها بسرعة.باستخدام بيانات أقل ، يمكن لهذا الفرز تحديد نقاط الربط التي يعمل بها بسرعة.باستخدام بيانات أقل ، يمكن لهذا الفرز تحديد نقاط الربط التي يعمل بها بسرعة.

يتم استخدام الفرز الاستقرائي في مكتبة C ++ القياسية ، على الرغم من أن الطريقة الدقيقة المستخدمة في std :: sort تعتمد على التنفيذ ، مع توفير المعلومات فقط على GCC. وفقًا للاشارات ، يعد هذا ثاني أسرع ترتيب بعد الفروق عند التعامل مع الأرقام ، وميزة فرز الفروق صغيرة (من 0 إلى 30٪ تقريبًا) ، ولكن مع فرز الفرز ، كل شيء أسوأ بكثير - يمكن أن يكون 3-4 مرات أقل من الزعماء . هذا هو في الواقع نوع سريع ، حيث يتم أخذ حالتين خاصتين في الاعتبار: 1) إذا أصبح عدد مرات التكرار أكبر من اللازم ، ثم التبديل إلى الفرز بواسطة كومة الذاكرة المؤقتة ؛ 2) إذا كان عدد عناصر الفرز صغيرًا ، فسيحدث التبديل إلى الفرز حسب عمليات الإدراج.

الفرز المستقر من مكتبة C ++ القياسية ( std :: stable_sort) ، كما يوحي الاسم ، له خاصية الاستقرار - فهو يحافظ على الترتيب النسبي بين العناصر التي لها نفس المفتاح. نادرًا ما تكون هذه الخاصية ضرورية ، على الرغم من أنني أكتب عنها لا أساس لها من الصحة ، إلا على أساس تجربتي الخاصة. يمكنه استخدام ذاكرة إضافية ، مما يجعله أسرع. والمثير للدهشة أن هذا الفرز يكون غالبًا أسرع من std :: sort.

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

تحتوي مكتبة BSD C على فرز bitwise ( radixsort) ونسخته المستقرة (sradixsort). لسوء الحظ ، لا يمكن استخدام كلا النوعين إلا في سلاسل C. كما سيتبين من بيانات الاختبار ، هذه هي أسرع طريقة لفرز الأوتار اليوم ، وبالتالي من المدهش أنه لا يوجد خيار قياسي لسلاسل C ++.

مكتبة BSD C لديها اكثر نوع دمج ( في تصنيف دمجي). يُعرف هذا الفرز بأنه أحد أسرع بيانات الوصول المتسلسل (الملفات ، القوائم) وربما يستخدم في مكتبة C ++ القياسية لفرز القوائم (std :: list و std :: forward_list). بالمناسبة ، كانت معروفة منذ عام 1948 وكان أحد مطوريها عالم رياضيات متخصص ومتخصص في أنظمة الكمبيوتر الأولى فون نيومان. من بين الطرق السريعة ، لا يتم تمييز هذا الفرز بأفضل الخصائص ، رغم أنه ، كقاعدة عامة ، يكون أسرع بعض الشيء من أساليب Shell. يتطلب ذاكرة إضافية ويتم تنفيذه عادةً بشكل مستدام.

بالإضافة إلى ذلك ، لا يزال هناك فرز بواسطة مجموعة(heapsort). عادةً ما يتم استخدام كومة الذاكرة المؤقتة لقائمة الانتظار الأمثل مع الأولويات ، ولكن يمكن أيضًا استخدامها للفرز. لا تتطلب أكوام الفرز ذاكرة إضافية ، لكن ليس لديها خاصية الاستقرار. في سرعة الأرقام ، تكون أبطأ بشكل ملحوظ (حتى 3-6 مرات) من أساليب Shell ، ولكن بالنسبة لخطوط الخطوط القصيرة ، فإنها تظهر نتائج جيدة للغاية ، وتجاوز (مع زيادة طول الخط ، وتزداد الميزة) طرق Shell.

فرز كومة الذاكرة المؤقتة يتوفر أيضًا في مكتبة C ++ القياسية. يتم هذا الفرز في عمليتين: بناء الكومة (std :: make_heap) ثم الفرز فعليًا ( std :: sort_heap). هنا ، بخلاف مكتبة bsd ، يعد الفرز مجرد واحدة من عمليات الكومة. عادةً ما يكون خيار الفرز هذا أسرع قليلاً من الخيار السابق (يعرض خيار bsd نتائج أفضل فقط على الأرقام القصيرة والخطوط الطويلة).

باستخدام مكتبة C ++ القياسية ، يمكنك فرز الشجرة الثنائية المتوازنة (std :: multiset) - ما عليك سوى ملء الشجرة ثم التنقل. يمكن اعتبار هذه الطريقة سريعة غير متكررة. تنشأ بعض المشاكل في حقيقة أن أداة تخصيص الذاكرة القياسية ملحوظة لكونها بطيئة ، لذلك للحصول على أفضل النتائج ، تحتاج إلى استخدام أداة التخصيص الخاصة بك ، والتي تزيد من حوالي 10-30٪. تجدر الإشارة أيضًا إلى أن هذه الطريقة تتطلب الكثير من الذاكرة الإضافية ، مع g ++ لكل عنصر من عناصر البيانات ، بالإضافة إلى ذلك ، ستحتاج أيضًا إلى تخزين 32 بايت (على بنية x 86-64) - سيكون من المثير للاهتمام محاولة تخزين هذه الشجرة كمجموعة ، أي بدون إضافية بايت. إذا كنت تستخدم دفعة :: container :: multiset ، فأنت تحتاج إلى ذاكرة أقل: 24 بايت إضافي فقط لكل عنصر بيانات. ومع ذلك ، مثل دفعة ،وأظهرت المكتبة القياسية مفاجأة واحدة غير سارة - في العملية التي تتطلب في بعض الأحيان ذاكرة أكثر مما كان ضرورياً. ربما هذا بسبب موازنة الأشجار الثنائية. رموز -هنا أن .

تحتوي مكتبة التقوية على spreadsort ، وهي خوارزمية تم اختراعها في القرن الحادي والعشرين. هذه هي أسرع طريقة متاحة اليوم في المكتبات المعروفة. يستخدم هذا التصنيف بعض الأفكار المعطاة تمامًا ، ومثلها ، يمكن أن يكون مزاجيًا تمامًا حول نوع الحجج. عادةً ما يظهر هذا الفرز نتائج قياسية ، وأحيانًا يكون أفضل بكثير من نتائج أقرب المنافسين. الاستثناء الوحيد هو فرز الخطوط C ، حيث يكون أدنى بكثير من الطرق bitwise من مكتبة bsd. عند فرز الخطوط الطويلة ، يمكن أن يكون أدنى من الطرق الأخرى ، على سبيل المثال ، الفرز الدوار أو الفرز السريع مع نقطتي ربط. أظهر الفرز المنتشر (دفعة v1.62) مشكلة سيئة للغاية- عند فرز صفائف السلسلة الصغيرة (حتى 1000 عنصر) ، فإنها تعمل مع الأخطاء.

هناك أيضًا خوارزمية pdqsort جديدة تعمل على تحسين ، كما ذكر المؤلف ، الفرز الاستبطاني. هذه الخوارزمية الجديدة ، التي لم يتم وصفها بعد على ويكيبيديا. نتائجها - على الرغم من أنها ليست سيئة ، ولكن ليست مؤثرة بشكل خاص. إنه أبطأ من std :: sort على أعداد صحيحة قصيرة ، ولكنه أسرع في الأعداد الصحيحة والأعداد الصحيحة الطويلة. في كلتا الحالتين ، والفرق هو ضئيل إلى حد ما. تم الحصول على أفضل النتائج لهذا الفرز لسلاسل C ++ طويلة - هنا هو أدنى ، على الرغم بشكل ملحوظ ، فقط للزعيم ، فرز الفرز.

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

بـ flat_stable_sort من مكتبة التعزيز نفسها. هذه خوارزمية جديدة قوية لم يتم وصفها بعد على ويكيبيديا. هذه هي الطريقة الأسرع بكثير ، لكنها أقل شأناً من معظم أساليب المكتبة السريعة الأخرى. يستخدم القليل جدًا من الذاكرة الإضافية (ومع ذلك ، فإنه يحتاج دائمًا إلى جدول ذي حجم ثابت يبلغ 8 كيلو بايت) وغالبًا ما يكون أسرع بشكل ملحوظ من طريقة Shell.

النظر في الجدولالوقت (بالمللي ثانية) لتشغيل هذه الخوارزميات على جهاز كمبيوتر مزود بذاكرة وصول عشوائي (RAM) تبلغ 8 جيجابايت مع معالج AMD Phenom ™ II X4 955 @ 3.214 ميغاهرتز. عمل الكمبيوتر لمدة عدة أشهر ، ويبلغ إجمالي حجم البيانات التي تم جمعها في ملفين json التي تم تحميلها مع الجداول 400 كيلوبايت تقريبًا. يتم تقديم التوقيت بمتوسط ​​عدد مرات التشغيل ؛ وبالنسبة للأحجام الصغيرة ، كانت هذه المسافات أكبر. يعمل العمل مع ذاكرة التخزين المؤقت بطريقة معقدة إلى حد ما على تغيير سرعة العمليات الحسابية ، وبالتالي فإن النتائج التي تم الحصول عليها تقريبية فقط في أحسن الأحوال (يمكنني افتراض أن أخطاء التوقيت يمكن أن تصل إلى 20٪). أعتقد أنه في أفضل المعالجات الحديثة لأجهزة الكمبيوتر الشخصية ، يمكن الحصول على النتيجة بمعدل أسرع مرتين إلى ثلاث مرات ، لكن تذكر أن العديد من المعالجات الحديثة تعمل عن طريق التبديل بين الترددات المختلفة والنتيجة التي حصلت عليها ،سيكون أكثر تقريبية.

هذا والجدول التالي تفاعلي. بالإضافة إلى القيم المطلقة للتوقيت ، يمكنك أيضًا رؤية قيمها بالنسبة إلى المتوسط ​​والمتوسط ​​والحد الأدنى والحد الأقصى. يمكنك تغيير الدقة في الشخصيات. يمكنك أيضًا الحصول على علاقات توقيت لأنواع مختلفة من الحشوات وأنواع البيانات. قد يوضح الأخير ، على سبيل المثال ، أن فرز سلاسل C أسرع بشكل ملحوظ من سلاسل C ++. من طرق الفرز ، يمكنك أيضًا تحديد وتجميع مجموعة متنوعة من المجموعات الفرعية. يمكنك ، بالطبع ، تعيين الفرز حسب أي عمود. لسوء الحظ ، لا أعرف كيفية استخدام Javascript في المقالة على لوحة الوصل ، لذلك لا تتوفر الجداول إلا بالرجوع إليها. وبالنسبة للحالة عندما imtqy.com سيتم طاقتها لتقديم المزيد من الروابط الخلفية ل أول و الثاني الجدول.

, , . , N , 1000, , . , ( ). , (deviation) .

:

• يمكن أن يتفوق أفضل أنواع الأصداف على البيانات التي تصل إلى 10 ملايين عنصر على فرز زمني وحتى بعض الأنواع السريعة ؛
• timsort قريب جدًا من السرعة qsort (clib) ، ويتجاوز أحيانًا بعض الشيء ، وأحيانًا العكس ؛
• غالبًا ما يتباطأ بشكل كبير ، ولا سيما الأشجار ، ولكن في ظل خلفية الفقاعة أو حتى الاختيار ، من الواضح أن هذه الطرق لا تزال سريعة. ومن المثير للاهتمام ، أن كلتا الطريقتين لهما غالبًا خصائص متشابهة للغاية - فكل منهما يبني الأشجار. من السهل ملاحظة أن التبعيات الخاصة بـ heapsort و treeort ، على الرغم من أنها ليست من الدرجة الثانية بوضوح ، من الواضح أنها ليست N log N ، ولكنها أسوأ من ذلك بكثير - مقارنة مع الفرز Shell ، والذي يتصرف بشكل أفضل مع زيادة حجم البيانات من heapsort أو treesort ، بينما أنها هي أبطأ من سجل N N. وبالتالي ، لا تتطابق التطبيقات العملية لفرز الكومة والأشجار مع المواصفات النظرية ؛
• تُظهر البيانات المتعلقة بفرز الأوتار أن قوانين التبعيات الزمنية هنا ليست مطابقة للأرقام ، حيث يتم فرض أطوال الأوتار التي تم فرزها بطريقة ما على هذه القوانين هنا. أنا ، للأسف ، لا أعرف الصيغ الخاصة بالفرز المعروفة التي من شأنها أن تعطي قوانين دقيقة للتبعيات عند العمل مع الأوتار ؛
• من المثير للاهتمام أن سرعة التعامل مع الأعداد الحقيقية تشبه الأعداد الصحيحة - وهذا نتيجة لحقيقة أنه في هندسة x86 الحديثة تم إجراء تحسينات فعالة للغاية للعمل مع المكدس ؛
• أظهر hash_sort نتائج متواضعة تمامًا ، وهذا ممكن نظرًا لحقيقة أنه بسبب استخدام ذاكرة إضافية ، ينخفض ​​أداء ذاكرة التخزين المؤقت للمعالج بشكل حاد. على بيانات عشوائية صغيرة (أقل من مائة ألف عنصر) ، يتفوق فرز التجزئة على أفضل الأنواع السريعة. يمكنك أيضًا ملاحظة أنه من الممكن حدوث ذلك مرة أخرى نظرًا للتخزين المؤقت ، فبعض نتائج هذا الفرز غريبة جدًا ، على سبيل المثال ، يتم فرز أعداد صحيحة 32 بت 10 ⁵ و 10 ⁶ و 10 ⁷ بت عند استخدام تعبئة مرتبة جزئيًا تقريبًا الوقت! نوع من الآثار الكمية تقريبا. :) أنا متأكد من أنه إذا قمت بالبحث ، فيمكنك العثور على نتائج أخرى صعبة تفسيرها.

سأضيف بعض الاستنتاجات حول بعض الحالات الخاصة:

• بعض أنواع حشوة البيانات تكشف نقاط الضعف في الأنواع السريعة. ومع ذلك ، فإن اختيار عنصر الدعم بطريقة معقدة يجعل من احتمال الوقوع في تسلسل سيء للفرز عملياً صفر. يمكنك أيضًا تحديد عنصر دعم في كل تمريرة بطرق مختلفة أو عشوائيًا. ربما يفعلون ذلك في qsort (clib). طريقة Hoare قيد النظر تعمل ببطء شديد فقط على تسلسلات مصممة خصيصًا ، والتي تصادفها الصدفة أثناء العمل العملي - هذه هي الحالة التي تنطوي على احتمال 2 ^{N -3} / ^N ، وهذا هو حدث مستحيل تقريبًا. على الرغم من أننا إذا أخذنا في الاعتبار التسلسلات التي لا تعمل بها طريقة Hoar بأسرع ما يمكن ، ولكن فقط مع تباطؤ كبير ، فهناك الكثير من هذه الحالات ، والتي ، مع ذلك ، تترك احتمال أن تكون حالة معالجة البيانات البطيئة بشكل غير مقبول غير مهمة من الناحية العملية ، وإن كان مزعجًا للغاية في اختلافها عن الصفر. كما أنه يكاد يكون من المستحيل الحصول على بيانات بطريق الخطأ ، حيث يعمل الفرز السريع باستخدام نقطتي تحكم ببطء ، وفقًا للقانون التربيعي. تظهر خيارات الفرز السريعة من Lomuto بدون عنصر دعم أو بدونه نتائج سيئة للغاية في جميع حالات التعبئة المحددة تقريبًا ؛
• في بعض الحالات الخاصة ، يعطي الفرز الأبطأ "الفقاعي" نتائج ممتازة ، وبعض أسرع الفرز السريع ، على العكس ، سيء جدًا ؛
• أظهر تصنيف التجزئة نتائج سيئة للغاية على حشوات النوعين 8 و 9 ، وذلك لأن التسلسل الرتيب مأخوذ من القيم المتتالية ، بدءًا من الأصغر ، ويتم أخذ 1٪ من الأرقام العشوائية من النطاق من الأدنى إلى الحد الأقصى للقيمة ، والذي يمل جميع 99٪ على التوالي من البيانات في عنصر التجزئة واحد. توضح هذه الحالة جيدًا المشكلات التي قد تنشأ عند استخدام هذا التصنيف أو الفرز مع صفيف به بيانات غير معروفة ؛
• يتصرف فرز الاختيار بشكل ثابت للغاية على جميع أنواع الحشوات ، كما أن عمليات فرز الكومة والأشجار مستقرة تمامًا ، دون أن تكون القمم والانخفاضات واضحة. هذا صحيح ، بالطبع ، لأنواع شل ، وكذلك معظم الطرق السريعة الأخرى من المكتبات القياسية.

حان الوقت للتحدث عن أنواع البيانات المستخدمة مع خوارزميات الفرز:

1. أعداد صحيحة موقعة 32 بت (int32_t) ، ولكن تم استخدام غير سالب فقط. كما تم أخذ البيانات العددية الأخرى غير السلبية فقط - وهذا لا يقلل من عمومية النتائج ، ولكن يجعل الحصول عليها لبعض الخوارزميات أسهل بكثير ؛
2. أعداد صحيحة ، 64 بت موقعة (int64_t) ؛
3. أعداد صحيحة ، موقعة 128 بت (__int128 - مدعومة من مجلس التعاون الخليجي على الأقل) ؛
4. هياكل خمسة أعداد صحيحة (int32_t) ، واحدة منها تستخدم كمفتاح (INT1P4). عند فرز هذه البيانات ، يبدأ عدد التباديل في التأثير على الوقت الحسابي بدرجة أكبر ؛ وبالتالي ، فإن الأساليب التي تحتوي على عدد أقل من التباديل تكتسب بعض المزايا ؛
5. أعداد حقيقية مثل الدقة المزدوجة ، مزدوجة (أرقام التعويم) ؛
6. تم أخذ سلاسل قصيرة C ++ و C. سلاسل من 1 إلى 16 (سلاسل قصيرة و c سلاسل قصيرة)؛
7. السلاسل C و C ++ بطول متوسط ​​، طوله من 1 إلى 256 (السلاسل والسلاسل c) ؛
8. الخطوط الطويلة C و C ++ ، التي يتراوح طولها من 1 إلى ²⁰ (هذا يزيد قليلاً عن مليون) ، ويتم تحديد الخطوط بحيث لا يتجاوز متوسط ​​طولها 512 ، لذلك تم اختيار الخطوط فقط لملء عشوائي ، وفي حالات أخرى ، تم أخذ الخطوط ببساطة أطوال من 1 إلى 512 (سلاسل طويلة و سلاسل طويلة).

وكذلك حول كيفية ملء مجموعة المصدر للفرز:

1. بالصدفة
2. تصاعدي بدقة (أمر) ؛
3. تنازلي صارم (ترتيب عكسي ، عكس) ؛
4. قيم عشوائية من المدى من 0 إلى 99 (تباين صغير ، تباين منخفض 100) ؛
5. تسلسل عشوائي من 0 و 1 (تباين صغير ، تباين منخفض 2) ؛
6. ثابت 0 (انتشار صغير ، اختلاف منخفض 1) ؛
7. التسلسل الذي يؤدي إلى إصدار qsort (Hoare) إلى التنفيذ الأبطأ. ومن الغريب أن هناك بالضبط 2 ^{N -3} هذه التسلسلات بين جميع متواليات الطول N ؛
8. تصاعدي بشدة ، مع إدراج أرقام عشوائية 1 ٪ (أمر جزئي) ؛
9. تنازلي صارم ، مع إدراج المتغيرات العشوائية 1 ٪ (عكس جزئيا).

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

دعونا نلقي نظرة على نتائج الاختبار ، حيث تعمل الفرز مع جميع سلاسل البيانات الممكنة. عدد هذه التسلسلات يساوي عامل طولها ، وبالتالي ، بالنسبة لتتابعات الطول 12 ، هناك 479'0101'600 متغير - جهاز كمبيوتر حديث جيد سيحسب عددهم في أقل من دقيقة. إذا أخذنا تسلسلات بطول 14 ، فسنحصل بالفعل على 87 "178" 291'200 بدائل لعدة ساعات من تشغيل الكمبيوتر. لذلك ، يوضح الجدول التالي متوسط ​​الوقت (في دورات المعالج التي تم الحصول عليها من خلال تعليمات RDTSC ) لفرز واحد عند فرز جميع التباديل حتى 12 فقط. في البيانات ، يتم أخذ الأنواع الرقمية السابقة والخيوط القصيرة. بالطبع ، يمكن للمرء أن يلاحظ أن التسلسل مع العناصر المكررة لا يعتبر. ومع ذلك ، أجرؤ على الإشارة إلى أن وجودهم لن يؤدي إلى تغيير النتائج نوعيًا ، ولكنه قد يؤدي إلى إبطاء استلامها بشكل كبير.

نتائج هذه البيانات الصغيرة ليست تمثيلية للغاية ، وخاصة بالنسبة لطرق الفرز المعقدة ، لكنها لا تزال تكمل فكرة سلوك الفرز. بعض الأنواع ، حسب علمي ، تستبدل الخوارزمية الرئيسية بخوارزمية أخرى عند العمل مع صفائف صغيرة - فهذه الأنواع منتشرة بسرعة مع نقطتي ربط و radix_msd (آخر استخدامين يدرجان). وتستخدم بعض عمليات الفرز (flat_stable و radix) جداول صغيرة ، ولكن مع أحجام بيانات صغيرة ، تبين أن هذه الجداول أكبر بكثير من البيانات نفسها ، مما يؤدي إلى إبطاء هذه الأساليب بدرجة كبيرة مقارنة بالآخرين ويؤدي إلى نتائج غريبة. يتم الحصول على نتائج غريبة أيضًا مع عمليات فرز bitwise الأخرى ومع تصنيفات الصفيف والتجزئة. يمكن تفسير هذه النتائج غير العادية بسهولة من خلال حقيقة أن وقت إعداد البيانات قبل الفرز لهذه الطرق للبيانات الصغيرة أطول من وقت الفرز نفسه. بطبيعة الحال ، عند قياس هذه الفترات الزمنية الصغيرة (النانوثانية) ، يكون تأثير الأخطاء المختلفة على القانون المعروض أعلى بكثير من الجدول السابق. لذلك ، تبين أن القوانين تقريبية للغاية ، وغالبًا ما تكون "ذات انحراف" عن القيم المبالغ فيها. يتم تفسير هذا الأخير جزئيًا من خلال حقيقة أنه عند العمل مع البيانات الصغيرة ، يصبح وقت الفرز نفسه قابلاً للمقارنة مع وقت استدعاء وظيفة الفرز والعديد من العمليات الإضافية اللازمة لقياس الوقت. يحاول البرنامج طرح النفقات العامة المسماة من الإخراج ، ولكن اتضح أنه يجب القيام به بدلاً من ذلك تقريبًا. مع كل هذا ، أجرؤ على افتراض أنه بمقارنة النتائج الخاصة بأنواع مختلفة من البيانات ومراعاة التعليقات المقدمة ، يمكنك أحيانًا تقديم افتراضات ليست بعيدة جدًا عن الدقة.

في الختام ، هناك جدول آخر يوضح مقدار طرق الاختبار المختلفة المطلوبة لفرز ذاكرة إضافية. من الواضح أن هذه القيمة تعتمد على النظام. في اختباراتي ، كما كتبت بالفعل ، هذا هو x86-64 ، دول مجلس التعاون الخليجي. الحرف T فيه يعني حجم الكتابة بالبايت (طول السلسلة غير مدرج في هذا الحجم: بالنسبة للخطوط C ، يكون حجم المؤشر ، بالنسبة لخطوط C ++ ، يكون حجم الواصف ، 32 بايت لـ x86-64 GCC) ، الحرف L هو الوسط طول الكتابة بالبايت (للأرقام ، هذا هو T ، وللأوتار ، يكون متوسط ​​طول السلسلة) ، يمكن أن تكون الحرف A 1 أو 0 - وهذا محاذاة للحد الفاصل 64 بت ، والحرف M هو محاذاة من مخصص الذاكرة القياسية (من المفترض محاذاة إلى حد 32 بايت). الرمز ^* يعني أنه تم الحصول على البيانات الخاصة بهذا النوع من الفرز فقط على أساس تحليل قراءة حقل VmRSS من / proc / PID / status (الحقل المذكور هو حجم برنامج العملية).


هناك ، بالطبع ، طرق فرز أخرى ، بدائية وسريعة. تحتوي مكتبة التعزيز على خوارزميات متوازية تتيح لك الاستفادة من وجود نوى المعالج الإضافية في النظام. يمكنك أيضًا استخدام دفعة الحاوية ذاتية الطلب :: container :: flat_multiset بدلاً من std :: multiset ، لكنها تعمل ببطء شديد.

أغتنم هذه الفرصة لأقول بعض التعليقات حول مكتبة التعزيز بشكل عام. أوصي بعدم المرور. حتى الميزات الموجودة في المكتبة القياسية في دفعة ، وكقاعدة عامة ، يتم تنفيذها بشكل أفضل ، وأحيانا (مثل التعبيرات العادية ، على سبيل المثال) أفضل بكثير. إذا كنا نتحدث عن الحاويات ، فعندئذ تكون أكبر حجمًا بشكل ملحوظ ، وتلك التي تتزامن مع الحاويات العادية تكون في بعض الأحيان أسرع إلى حد ما وغالبًا ما تحتوي على تحسينات صغيرة ولكنها لطيفة. يقوم Boost بالتحقق من الأنواع بشكل أكثر شمولًا ، مما قد يساعد في بعض الأحيان في الكشف عن الأخطاء المراوغة تقريبًا والتي عادةً ما لا تظهر على نفسها ، ولكن في بعض الحالات ، يمكن تنشيطها بشكل مفاجئ. تتضمن عيوب التعزيز غير قابل للقراءة تمامًا وغير المشروط تمامًا الرسائل الضخمة حول أخطاء الترجمة على العديد من الإنشاءات من هذه المكتبة - وهذا ، على الرغم من أنه بدرجة أقل ، ينطبق على المكتبة القياسية. حان الوقت لمطوري C ++ للقيام بشيء حيال ذلك.

يمكن أخذ جميع الملفات التي تحتوي على اختبارات وبعض المواد الأخرى ذات الصلة من مستودع التخزين الخاص بي. إذا كان شخص ما مهتمًا ببيانات المصدر الخام ، فيمكنك الحصول عليها هنا (1.4 ميغابايت). سأكون سعيدًا بأي تعليقات أو انتقادات أو إضافات.