لماذا التحول المفاجئ إلى الإستراتيجية من أعلى إلى أسفل في std::list::sort()?

في Visual Studio 2015 (VS2015)، قامت Microsoft بتبديل استراتيجية الفرز الخاصة بـ std::list::sort() من أسلوب Merge Sort التقليدي من أسفل إلى أعلى إلى أسلوب من أعلى إلى أسفل. ألغى هذا التغيير استخدام مجموعة داخلية من القوائم واعتمد التكرارات لتتبع حدود التشغيل المصنفة داخل القائمة الأصلية.

أسباب التغيير

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

تنفيذ النهج من أعلى إلى أسفل

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

اعتبارات الأداء

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