"5 سنتات" للحديث عن أنواع

في متابعة للموضوع ، أريد مشاركة الكود الخاص بي ، والذي يتفوق على std::sort() من الإصدارات الحالية من مكتبة GNU C ++ و (تقريبًا ، لا توجد بيانات دقيقة) يكرر نتيجة "Sort Alexandrescu" مع CppCon 2019 .

شروط المهمة

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

يؤدي

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

• حسب عدد المقارنات والتحركات (يتم قياسها عن طريق استبدال فئة C++ لحساب المقارنات والواجبات).
• بواسطة حجم رمز الجهاز (يستغرق مساحة صغيرة في ذاكرة التخزين المؤقت).
• بواسطة حجم الكود المصدري وشفافيته.
• في التسلسل العشوائي الطويل ، يميل الربح إلى 3-5٪ ، اعتمادًا على SORT_THRESHOLD .
• ما يصل إلى 1.5-2-3 مرات أسرع مع البيانات المطلوبة أو المطلوبة في الغالب.
• خسارة طفيفة فقط على تسلسلات قصيرة جدا في ترتيب عكسي.

من المحتمل جدًا أن يكون هذا الخيار أسرع قليلاً و / أو أبطأ قليلاً من الغالبية العظمى من الأنواع ، ولكن معرفة هذا هو حرفيًا عملاق لا أستطيع تحمله.

من المثير للاهتمام أن يقارن شخص ما هذا الخيار مع الخيارات الحالية في Tarantool و PostgreSQL و SQLite و MySQL. آمل ألا يتمكن kaamos من المرور عبر SysBench .

كيف يتم الكسندريسكو؟

في أول تعليق من RPG18 ، كان هناك رابط لأداء حديث قدمه Andrei Alexandrescu بعنوان "تم العثور على السرعة في عقول الناس" ، حيث يقود إلى فكرة مشابهة إلى حد ما ، لكنه يقترب من الاقتراب من النهائي.

بدا الأداء طويلاً بالنسبة لي (إذا كان olegbunin قد أعطى 90 دقيقة مرة واحدة على الأقل ...) ، ولكن الأرقام ليست كافية. على وجه الخصوص ، أريد أن أرى سلوك الفرز مع زيادة N ، لأن الزيادة في عتبة إكمال QuickSort تؤدي إلى تسارع بأحجام كبيرة وتباطؤ إلى أحجام صغيرة ، إلخ.

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

الجانب الأيديولوجي

الجانب النظري والإيديولوجي لـ "الخوارزمية" بسيط للغاية:

1. بالنسبة للتسلسلات غير القصيرة ، نستخدم QuickSort بكل التحسينات المقبولة:
   
   • لا بشكل متكرر باستخدام المكدس الداخلي للمواضع على المؤشرات.
   • كعنصر داعم ، نستخدم وسيط العناصر الأولى والمتوسطة والأخيرة.
   • لا نقوم بتصنيف الأجزاء الصغيرة ، بل نتركها لشركة ShellSort.
   • بعد الانقسام ، نضع دائمًا الجزء الأكبر على المكدس ؛ ونتيجة لذلك ، لا يمكن أن تكون المجموعة أكثر عمقًا من Log2(N) .
2. إضافة بيانات الفرز باستخدام ShellSort:
   
   • الحد الأدنى لعدد يمر.
   • ترتبط الخطوة في أول تمرير مع الحد الأقصى لحجم القطعة غير المصنفة.
   • مجموع اثنين فقط من التمريرات مع الخطوات 8 و (حتما) 1.
3. يتيح لك استخدام ShellSort زيادة عتبة الخروج بأمان نسبيًا لـ QuckSort. نتيجة لذلك ، لدينا مجموعة من أفضل خيارات QuickSort مع توفير نتيجة خروج مبكر والفرز المسبق بشكل أسرع قليلاً.

تجدر الإشارة إلى أنه بناءً على بنية المعالج وشروط التطبيق ، يمكنك زيادة الكسب على التتابعات الطويلة بنسبة تصل إلى 10-15٪ عن طريق اختيار SORT_THRESHOLD خلال 128-256. ومع ذلك ، يؤدي هذا إلى إبطاء معالجة التتابعات بترتيب عكسي وقربها.
ومع ذلك ، تعتبر هذه مكافأة جيدة إذا فهمت أن الترتيب العكسي غير مرجح في بياناتك ، أو إذا كان يمكنك اكتشاف مثل هذه الحالات بسعر رخيص وتنفيذ فرع باستخدام SORT_THRESHOLD صغير.

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