cpp sort
1.16.0 — Taxonomics
سيكون من الرائع أن تهيمن طريقة أو اثنتين فقط من طرق الفرز على جميع الطرق الأخرى، بغض النظر عن التطبيق أو الكمبيوتر المستخدم. ولكن في الواقع، كل طريقة لها فضائلها الخاصة. [...] وهكذا نجد أن جميع الخوارزميات تقريبًا تستحق أن نتذكرها، نظرًا لوجود بعض التطبيقات التي تبين أنها الأفضل فيها. - دونالد كنوث، فن برمجة الكمبيوتر، المجلد 3
cpp-sort هي مكتبة فرز عامة لرؤوس C++ 14 فقط. وهو يدور حول واجهة فرز عامة رئيسية واحدة ويوفر العديد من الأدوات الصغيرة لاختيار و/أو تصميم خوارزميات الفرز. يجب أن يكون استخدام ميزات الفرز الأساسية أمرًا تافهًا بدرجة كافية:
# include < array >
# include < iostream >
# include < cpp-sort/sorters/smooth_sorter.h >
int main ()
{
std::array< int , 5 > arr = { 5 , 8 , 3 , 2 , 9 };
cppsort::smooth_sort (arr);
// prints 2 3 5 8 9
for ( int val: arr) {
std::cout << val << ' ' ;
}
}يوفر cpp-sort مجموعة كاملة من الميزات المتعلقة بالفرز. فيما يلي اللبنات الأساسية للمكتبة:
فيما يلي مثال أكثر اكتمالاً لما يمكن فعله بالمكتبة:
# include < algorithm >
# include < cassert >
# include < forward_list >
# include < functional >
# include < vector >
# include < cpp-sort/adapters.h >
# include < cpp-sort/sorters.h >
int main ()
{
struct wrapper { int value; };
std::forward_list<wrapper> li = { { 5 }, { 8 }, { 3 }, { 2 }, { 9 } };
std::vector<wrapper> vec = { { 5 }, { 8 }, { 3 }, { 2 }, { 9 } };
// When used, this sorter will use a pattern-defeating quicksort
// to sort random-access collections, and a mergesort otherwise
cppsort::hybrid_adapter<
cppsort::pdq_sorter,
cppsort::merge_sorter
> sorter;
// Sort li and vec in reverse order using their value member
sorter (li, std::greater<>{}, &wrapper::value);
sorter (vec, std::greater<>{}, &wrapper::value);
assert ( std::equal (
li. begin (), li. end (),
vec. begin (), vec. end (),
[]( const auto & lhs, const auto & rhs) { return lhs. value == rhs. value ; }
));
}حتى عند استخدام وظائف الفرز بدون الميزات الإضافية، فإنها لا تزال توفر بعض الضمانات المثيرة للاهتمام (الأفكار غالبًا ما تكون مأخوذة من Ranges TS):
iter_swap و iter_moveoperator()يمكنك قراءة المزيد حول جميع الأدوات المتاحة والعثور على بعض البرامج التعليمية حول استخدام وتوسيع cpp-sort في wiki.
تم إنشاء الرسم البياني التالي باستخدام برنامج نصي موجود في دليل المعايير. يُظهر الوقت اللازم heap_sort لفرز مليون عنصر دون تكييفها، ثم عندما يتم تكييفها إما باستخدام drop_merge_adapter أو split_adapter .
كما هو موضح أعلاه، فإن التفاف heap_sort مع أي من المحولات يجعلها قابلة للتكيف مع عدد الانقلابات بطريقة غير تدخلية. الخوارزميات المستخدمة لتكييفها لها إيجابيات وسلبيات مختلفة، والأمر متروك لك لاستخدام أي منهما.
هذا المعيار موجود في الغالب لإظهار الإمكانيات التي توفرها المكتبة. يمكنك العثور على المزيد من هذه المعايير المعلقة في صفحة الويكي المخصصة.
يتطلب cpp-sort دعم C++ 14، ويجب أن يعمل مع المترجمين التاليين:
/permissive- . بعض الميزات غير متوفرة.المترجمات المذكورة أعلاه هي تلك التي يستخدمها خط أنابيب CI، ويتم أيضًا اختبار المكتبة بأحدث الإصدارات من تلك المترجمات بشكل منتظم. جميع إصدارات المترجم الأخرى الموجودة بينهما لم يتم اختبارها، ولكن يجب أن تعمل أيضًا. لا تتردد في فتح قضية إذا لم يكن الأمر كذلك.
قد تختلف الميزات الموجودة في المكتبة اعتمادًا على إصدار C++ المستخدم وعلى ملحقات المترجم الممكّنة. تم توثيق هذه التغييرات في الويكي.
يحتوي المستودع الرئيسي على دعم إضافي للأدوات القياسية مثل CMake أو Conan. يمكنك قراءة المزيد عن تلك الموجودة في الويكي.
حصلت على سيارة جديدة. أنا فقط بحاجة إلى تجميعها معًا. من الأسهل سرقتهم قطعة قطعة. - جارود كينتز، 3.33 دولار
على الرغم من أن بعض أجزاء المكتبة عبارة عن أبحاث أصلية وبعضها الآخر يتوافق مع تطبيقات مخصصة وساذجة إلى حد ما لخوارزميات الفرز القياسية، فإن cpp-sort يعيد أيضًا استخدام قدر كبير من التعليمات البرمجية والأفكار من المشاريع مفتوحة المصدر، وغالبًا ما يتم تعديلها للتكامل بسلاسة في المكتبة. مكتبة. فيما يلي قائمة بالموارد الخارجية المستخدمة لإنشاء هذه المكتبة. آمل أن تكون التراخيص العديدة المختلفة متوافقة. إذا لم يكن الأمر كذلك، يرجى الاتصال بي (أو إرسال مشكلة) وسنرى ما يمكن فعله حيال ذلك:
بعض الخوارزميات المستخدمة بواسطة insertion_sorter و pdq_sorter تأتي من الفرز السريع الذي يهزم النمط من Orson Peters. بعض أجزاء المعايير تأتي من هناك أيضًا.
الخوارزمية المستخدمة بواسطة tim_sorter تأتي من تطبيق Goro Fuji (gfx) لـ Timsort.
الخوارزميات الثلاث التي يستخدمها spread_sorter تأتي من وحدة ستيفن روس Boost.Sort.
الخوارزمية المستخدمة بواسطة d_ary_spread_sorter تأتي من وحدة Boost.Heap الخاصة بـ Tim Blechmann.
الخوارزمية المستخدمة بواسطة spin_sorter تأتي من الخوارزمية التي تحمل نفس الاسم والتي تم تنفيذها في Boost.Sort. بواسطة فرانسيسكو خوسيه تابيا.
utility::as_function و utility::static_const والعديد من الخوارزميات المساعدة المحسنة للإسقاط تأتي من مكتبة Range v3 الخاصة بـ Eric Niebler. العديد من الأفكار مثل مكررات الوكيل ونقاط التخصيص والإسقاطات، بالإضافة إلى بعض وظائف المرافق الأخرى تأتي أيضًا من تلك المكتبة أو من المقالات ذات الصلة ومقترحات C++ القياسية.
الخوارزمية المستخدمة بواسطة ska_sorter تأتي من تنفيذ Malte Skarupke لخوارزمية ska_sort الخاصة به.
الخوارزمية المستخدمة بواسطة drop_merge_sorter تأتي من إعادة تنفيذ Adrian Wielgosik C++ لفرز الدمج المسقط الخاص بـ Emil Ernerfeldt.
تم تكييف العديد من الخوارزميات القياسية المحسنة مباشرة من نظيراتها في libc++، وتم تحسينها للتعامل مع كل من الإسقاطات ومكررات الوكيل.
تستخدم المكتبة داخليًا وظيفة inplace_merge التي تعمل مع التكرارات الأمامية. يستخدم تنفيذها خوارزمية دمج اقترحها Dudziński وDydek، ونفذها ألكسندر ستيبانوف وبول ماكجونز في كتابهم عناصر البرمجة .
يستخدم التحميل الزائد inplace_merge لمكررات الوصول العشوائي خوارزمية Symmerge التي اقترحها Pok-Son Kim وArne Kutzner في دمج الحد الأدنى الثابت للتخزين عن طريق المقارنات المتماثلة عندما لا تتوفر ذاكرة كافية لإجراء دمج خارج المكان.
تم تكييف تطبيق Dijkstra's Smoothsort الذي يستخدمه smooth_sorter مباشرةً من تطبيق Keith Schwarz للخوارزمية.
تم تكييف الخوارزمية المستخدمة بواسطة wiki_sorter من WikiSort الخاص بـ BonzaiThePenguin.
تم تكييف الخوارزمية المستخدمة بواسطة grail_sorter من GrailSort الخاص بـ Mrrl.
الخوارزمية المستخدمة بواسطة indirect_adapter مع التكرارات الأمامية أو ثنائية الاتجاه هي نسخة معدلة قليلاً من الخوارزمية المستقلة لماثيو بنتلي.
يأتي تنفيذ التحميل الزائد للوصول العشوائي لـ nth_element الذي تستخدمه بعض الخوارزميات من مكتبة Miniselect الخاصة بـ Danila Kutenin ويستخدم خوارزمية AdaptiveQuickselect الخاصة بـ Andrei Alexandrescu.
تأتي جميع شبكات الفرز المستخدمة بواسطة sorting_network_sorter من هذه القائمة التي يحتفظ بها Bert Dobbelaere. تحتوي الصفحة على إشارات إلى مصادر كافة شبكات الفرز التي تدرجها.
بعض التحسينات المستخدمة بواسطة sorting_network_sorter تأتي من هذه المناقشة على StackOverflow وهي مدعومة بالمقالة تطبيق شبكات الفرز لتجميع مكتبات الفرز المحسنة .
تعيد مجموعة الاختبار تطبيق خوارزميات الأرقام العشوائية الموجودة أصلاً في الأماكن التالية:
إن نصوص LaTeX المستخدمة لرسم شبكات الفرز هي إصدارات معدلة من sortingnetwork.tex ، وقد تم تعديلها قليلاً لتكون مستندة إلى 0 وترسم الشبكة من أعلى إلى أسفل.
تشتمل أدوات CMake المضمنة في المشاريع على نصوص برمجية من RWTH-HPC/CMake-codecov وCrascit/DownloadProject.
تستخدم بعض المعايير لوحة ألوان صديقة لعمى الألوان تم تطويرها بواسطة Thøger Rivera-Thorsen.
